Гиперграф D-интервала
В теории графов гиперграф d -интервалов — это разновидность гиперграфа, построенного с использованием интервалов действительных прямых . Параметр d является положительным целым числом . Вершинами вершин -интервального d гиперграфа являются точки d непересекающихся прямых (таким образом, несчетное количество ). Ребрами . графа являются d — наборы интервалов, по одному интервалу в каждой вещественной строке [1]
Самый простой случай — d = 1 . Множество вершин одноинтервального гиперграфа — это множество действительных чисел; каждое ребро в таком гиперграфе является интервалом вещественной прямой. Например, набор { [−2, −1], [0, 5], [3, 7] } определяет 1-интервальный гиперграф. Обратите внимание на отличие от графа интервалов : в графе интервалов вершинами являются интервалы ( конечное множество ); в 1-интервальном гиперграфе вершинами являются все точки вещественной прямой ( несчетное множество ).
Другой пример: в двухинтервальном гиперграфе множество вершин представляет собой непересекающееся объединение двух действительных линий, а каждое ребро представляет собой объединение двух интервалов: одного в строке №1 и одного в строке №2.
Следующие два понятия определены для d -интервальных гиперграфов, как и для конечных гиперграфов:
- Паросочетание — это набор непересекающихся ребер, т. е. набор непересекающихся d -интервалов. Например, в 1-интервальном гиперграфе {[−2, −1], [0, 5], [3, 7] } множество { [−2, −1], [0, 5] } является паросочетание размера 2, но набор { [0, 5], [3, 7] } не является паросочетанием, поскольку его элементы пересекаются. Наибольший размер соответствия в H обозначается ν ( H ) .
- Покрытие d или трансверсаль — это набор вершин, пересекающий каждое ребро, т. е. набор точек, пересекающий каждый - интервал. Например, в 1-интервальном гиперграфе {[−2, −1], [0, 5], [3, 7] } множество {−1.5, 4} является покрытием размера 2, но множество { −1.5, 1} не является покрытием, поскольку не пересекает ребро [3, 7] . Наименьший трансверсальный размер в H обозначается τ ( H ) .
ν ( H ) ≤ τ ( H ) верно для любого H. гиперграфа
Тибор Галлай доказал, что в 1-интервальном гиперграфе они равны: τ ( H ) = ν ( H ) . Это аналогично теореме Кенига для двудольных графов .
Габор Тардос [1] доказал, что в 2-интервальном гиперграфе τ ( H ) ≤ 2 ν ( H ) и он является тесным (т. е. каждый 2-интервальный гиперграф с паросочетанием размера m может быть покрыт 2 m точками).
Кайзер [2] доказал, что в d гиперграфе с -интервалами τ ( H ) ⩽ d ( d – 1) ν ( H ) , и более того, каждый гиперграф с d -интервалами с паросочетанием размера m может быть покрыт в d ( d − 1) m точек, ( d − 1) m точек на каждой строке.
Фрик и Зербиб [3] доказал красочную (« радужную ») версию этой теоремы.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Тардос, Габор (1 марта 1995 г.). «Трансверсали 2-интервалов, топологический подход» . Комбинаторика . 15 (1): 123–134. дои : 10.1007/bf01294464 . ISSN 0209-9683 .
- ^ Кайзер, Т. (1 сентября 1997 г.). «Трансверсали d-интервалов» . Дискретная и вычислительная геометрия . 18 (2): 195–203. дои : 10.1007/PL00009315 . ISSN 1432-0444 .
- ^ Фрик, Флориан; Зербиб, Шира (01.06.2019). «Цветные покрытия многогранников и пронзающие числа красочных d-интервалов» . Комбинаторика . 39 (3): 627–637. arXiv : 1710.07722 . дои : 10.1007/s00493-018-3891-1 . ISSN 1439-6912 .