D-интервальный гиперграф - D-interval hypergraph

В теория графов, а 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]} не является сопоставлением, поскольку его элементы пересекаются. Самый большой подходящий размер в ЧАС обозначается ${ displaystyle nu (H)}$.
• А покрытие или поперечный - это набор вершин, пересекающий каждое ребро, т. е. набор точек, пересекающий каждое d-интервал. Например, в 1-интервальном гиперграфе {[−2, −1], [0, 5], [3, 7]} множество {−1.5, 4} является покрытием размера 2, но множество { −1.5, 1} не является покрытием, так как не пересекает ребро [3,7]. Наименьший поперечный размер в ЧАС обозначается ${ Displaystyle тау (Н)}$.

${ Displaystyle ню (Ч) Leq тау (Н)}$ верно для любого гиперграфа ЧАС.

Тибор Галлай доказал, что в 1-интервальном гиперграфе они равны: ${ Displaystyle Nu (H) = тау (H)}$. Это аналогично Теорема Кёнига для двудольных графов.

Габор Тардос^[1] доказал, что в 2-интервальном гиперграфе ${ Displaystyle тау (H) Leq 2 Nu (H)}$, и он плотный (т.е. каждый 2-интервальный гиперграф с сопоставлением размера м, можно покрыть 2м точки).

Кайзер^[2] доказал, что в d-интервальный гиперграф, ${ Displaystyle тау (H) Leq d (d-1) Nu (H)}$, и более того, каждый d-интервальный гиперграф с сопоставлением размеров м, может быть покрыт на d(d − 1)м точки, (d − 1)м точки на каждой строке.

Фрик и Зербиб^[3] доказал красочную («радужную») версию этой теоремы.

Рекомендации