Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.
Вопросы о рёберных графах гиперграфов часто являются обобщениями вопросов о рёберных графах обычных графов. Например, гиперграф, все рёбра которого имеют размер k, называется k-униформным (2-униформный гиперграф — это обычный граф). В теории гиперграфов часто естественно требовать k-униформность. Любой обычный граф является рёберным графом некоего гиперграфа, но если зафиксировать размер ребра k (число точек множества, принадлежащего ребру), не всякий граф является рёберным графом какого-либо k-униформного графа. Основная задача — описать рёберные графы для каждого .
Гиперграф называется линейным''', если любая пара гиперрёбер имеет в пересечении максимум одну вершину. Любой граф является рёберным графом не только некоторого гиперграфа, но и некоторого линейного гиперграфа.
Рёберные графы k-униформных гиперграфов, k≥3 Байнеке описал рёберные графы обычных графов путём перечисления 9 запрещённых порождённых подграфов (смотрите статью о рёберных графах). Никакого описания посредством запрещённых порождённых подграфов не известно для рёберных графов k-униформных гиперграфов для любого и Ловас показал, что не существует такого описания в виде конечного списка для k = 3.
Краус описал рёберные графы обычных графов в терминах покрытия кликами (Смотрите Рёберный граф). Глобальное описание краусовского типа для рёберных графов k-униформных гиперграфов для любого дано Бержем.
Рёберные графы k-униформных линейных гиперграфов для k≥3 Глобальное описание краусовского типа для рёберных графов k-униформных линейных гиперграфов для любого дано Найком, Рао, Шрикханде и Сингхи. В то же время они нашли конечное число запрещённых порождённых подграфов для линейных 3-униформных гиперграфов с минимальной степенью вершины не меньше 69. Метельский и Тышкевич и Якобсон, Кезди, Лехель улучшили эту границу до 19, а Скумс, Суздаль и Тышкевич сократили это значение до 16. Метельский и Тышкевич также доказали, что для k > 3 не существует подобного списка для линейных k-униформных гиперграфов, какое бы ограничение на степень не накладывали.
Сложность поиска описания линейных k-униформных гиперграфов заключается в том, что имеется бесконечно много запрещённых порождённых подграфов. Чтобы дать пример, для m > 0 возьмём цепочку из m графов-алмазов, так чтобы алмазы имели общие вершины второго порядка, и добавим некоторые висячие вершины, как показано на рисунке, чтобы получить одно из семейств минимальных запрещённых подграфов.
Имеется ряд интересных описаний для рёберных графов линейных k-униформных гиперграфов, данных разными авторами; ;; ; , при ограничениях на минимальную степень вершин или минимальную степень рёбер. Минимальная степень ребра для описания рёберных графов k-униформных линейных гиперграфов для любого , не меньшая в работе Найка, Рао, Шрикханде и Сигхи, уменьшена до в работах Якобсона, Кезди, Лехела и Зверовича.
Сложность распознавания рёберных графов линейных k-униформных гиперграфов без ограничений на минимальную степень (или минимальную степень рёбер) неизвестна. Для k'' = 3 и минимальной степени по меньшей мере 19 распознавания возможно за полиномиальное время). Скумс, Суздаль и Тышкевич уменьшили минимальную степень до 10.
Есть много нерешённых задач и гипотез в работах Найка и др., Якобсона и др., Метельского и др. и Зверовича.
Примечания
Литература
. Переведено с французского
. На венгерском
Категория:Семейства графов