Характеристика запрещенного графа - Forbidden graph characterization
В теории графов, разделе математики, многие важные семейства графов могут быть описаны конечным набором отдельных графов, которые не принадлежат к семейству, и дополнительно исключить все графы из семейства, которые содержат любой из этих запрещенных графов как (индуцированные) подграф или второстепенный. Прототипным примером этого явления является теорема Куратовского , которая утверждает, что граф является плоским (может быть нарисован без пересечений на плоскости) тогда и только тогда, когда он не содержит ни одного из двух запрещенных графов, полного графа K 5 и полного двудольного графа. граф К 3,3 . Для теоремы Куратовского понятие включения - это понятие гомеоморфизма графов , в котором подразделение одного графа появляется как подграф другого. Таким образом, каждый граф либо имеет планарный рисунок (в этом случае он принадлежит к семейству плоских графов), либо имеет подразделение одного из этих двух графов в качестве подграфа (в этом случае он не принадлежит к планарным графам).
Определение
В более общем смысле, характеристика запрещенного графа - это метод определения семейства структур графа или гиперграфа путем определения подструктур, существование которых запрещено в любом графе в семействе. Разные семьи различаются по характеру того, что запрещено . В общем, структура G является членом семейства тогда и только тогда , когда запрещенная субструктура не содержится в G . Запрещено подструктура может быть один из:
- подграфы , меньшие графы, полученные из подмножеств вершин и ребер большего графа,
- индуцированные подграфы , меньшие графы, полученные путем выбора подмножества вершин и использования всех ребер с обеими конечными точками в этом подмножестве,
- гомеоморфные подграфы (также называемые топологическими минорами ), меньшие графы, полученные из подграфов путем сворачивания путей из вершин степени два в отдельные ребра, или
- миноры графов , меньшие графы, полученные из подграфов произвольным сжатием ребер .
Множество структур, которым запрещено принадлежать к данному семейству графов, также можно назвать множеством препятствий для этого семейства.
Запрещенные характеристики графов могут использоваться в алгоритмах для проверки принадлежности графа к данному семейству. Во многих случаях можно проверить за полиномиальное время , содержит ли данный граф какие-либо элементы набора препятствий и, следовательно, принадлежит ли он семейству, определенному этим множеством препятствий.
Чтобы семейство имело характеристику запрещенного графа с определенным типом подструктуры, семейство должно быть замкнуто под подструктурами. То есть каждая подструктура (данного типа) графа в семействе должна быть другим графом в семействе. Точно так же, если граф не является частью семейства, все более крупные графы, содержащие его в качестве подструктуры, также должны быть исключены из семейства. Когда это так, всегда существует набор препятствий (набор графов, которые не входят в семейство, но все меньшие подструктуры которых принадлежат этому семейству). Однако для некоторых представлений о том, что такое подструктура, этот набор препятствий может быть бесконечным. Теорема Робертсона – Сеймура доказывает, что в частном случае миноров графа замкнутое относительно миноров семейство всегда имеет конечное множество препятствий.
Список запрещенных характеризаций для графов и гиперграфов
| Семья | Препятствия | Связь | Справка |
|---|---|---|---|
| Леса | петли, пары параллельных ребер и циклы любой длины | подграф | Определение |
| петля (для мультиграфов) или треугольник K 3 (для простых графов) | граф минор | Определение | |
| Графы без клешней | звезда К 1,3 | индуцированный подграф | Определение |
| Графики сопоставимости | индуцированный подграф | ||
| Графики без треугольников | треугольник К 3 | индуцированный подграф | Определение |
| Планарные графики | К 5 и К 3,3 | гомеоморфный подграф | Теорема Куратовского |
| К 5 и К 3,3 | граф минор | Теорема Вагнера | |
| Внешнепланарные графы | К 4 и К 2,3 | граф минор | Дистель (2000) , стр. 107 |
| Внешние 1-плоские графы | шесть запрещенных несовершеннолетних | граф минор | Auer et al. (2013) |
| Графики фиксированного рода | конечное множество препятствий | граф минор | Дистель (2000) , стр. 275 |
| Графики вершины | конечное множество препятствий | граф минор | |
| Бесконечно встраиваемые графы | Семья Петерсен | граф минор | |
| Двудольные графы | нечетные циклы | подграф | |
| Хордовые графы | циклы длиной 4 и более | индуцированный подграф | |
| Совершенные графики | циклы нечетной длины 5 и более или их дополнения | индуцированный подграф | |
| Линейный график графиков | девять запрещенных подграфов (перечислены здесь ) | индуцированный подграф | |
| График объединение из кактуса графиков | ромбовидный граф с четырьмя вершинами, образованный удалением ребра из полного графа K 4 | граф минор | |
| Лестничные графики | K 2,3 и его двойственный граф | гомеоморфный подграф | |
| Разделить графики | индуцированный подграф | ||
| 2-подключенные последовательно-параллельные ( ширина дерева ≤ 2, ширина ответвления ≤ 2) | К 4 | граф минор | Дистель (2000) , стр. 327 |
| Ширина дерева ≤ 3 | K 5 , октаэдр , пятиугольная призма , граф Вагнера | граф минор | |
| Ширина ответвления ≤ 3 | K 5 , октаэдр , куб , граф Вагнера | граф минор | |
| Дополняемо-приводимые графы (кографы) | 4-вершинный путь P 4 | индуцированный подграф | |
| Тривиально совершенные графы | 4-вершинный путь P 4 и 4-вершинный цикл C 4 | индуцированный подграф | |
| Графики пороговых значений | 4-вершинный путь P 4 , 4-вершинный цикл C 4 и дополнение к C 4 | индуцированный подграф | |
| Линейный график 3-однородных линейных гиперграфов | конечный список запрещенных индуцированных подграфов минимальной степени не менее 19 | индуцированный подграф | |
| Линейный график k -однородных линейных гиперграфов, k > 3 | конечный список запрещенных индуцированных подграфов с минимальной степенью ребра не менее 2 k 2 - 3 k + 1 | индуцированный подграф | |
| Графы ΔY-сводимые к одной вершине | конечный список не менее 68 миллиардов различных (1,2,3) -кликовых сумм | граф минор | |
| Общие теоремы | |||
| Семья, определяемая индуцированно-наследственным свойством | множество препятствий, возможно, не конечное | индуцированный подграф | |
| Семья, определяемая несовершеннолетним наследственным имуществом | конечное множество препятствий | граф минор | Теорема Робертсона – Сеймура. |
