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