Характеризация запрещёнными графами

Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе.

Запрещённые графы

В теории графов многие важные семейства графов могут быть описаны конечным числом индивидуальных графов, которые не принадлежат семейству, и исключаются все графы из семейства, которые содержат любой из этих запрещённых графов в качестве (порождённого) подграфа или минора. В качестве прототипа явления служит теорема Понтрягина — Куратовского, которая утверждает, что граф планарен (граф, который можно нарисовать на плоскости без пересечений) тогда и только тогда, когда граф не содержит любой из двух запрещённых подграфов, полный граф K₅ и полный двудольный граф K_3,3.

В различных семействах природа запрещённого меняется. В общем случае структура G является членом семейства ${\displaystyle {\mathcal {F}}}$ тогда и только тогда, когда запрещённая структура не содержится в G. Запрещённая подструктура может быть одной из:

• подграфы, меньшие графы, получаемые из подмножества вершин и рёбер большего графа,
• порождённые подграфы, меньшие графы, получаемые выбором подмножества вершин и включением всех рёбер, у которых обе вершины принадлежат этому подмножеству,
• гомеоморфных подграфов (называемых также топологическими минорами), меньших графов, получаемых из подграфов заменой путей с вершинами степени два на рёбра,
• миноров графа, меньших графов, полученных из подграфов путём произвольного стягивания рёбер.

Множество структур, которым запрещено принадлежать данному семейству графов, можно также назвать препятствующим множеством семейства.

Характеризация запрещёнными графами может быть использована в алгоритмах для проверки, принадлежит ли граф данному семейству. Во многих случаях можно проверить за полиномиальное время, содержит ли данный граф какой-либо член препятствующего множества, а потому, принадлежит ли граф семейству, определяемому препятствующим множеством.

Чтобы семейство имело характеризацию запрещёнными графами с определённым типом подструктур, семейство должно быть замкнуто по подструктурам. То есть любая подструктура (данного типа) графа в семействе должна быть другим графом в семействе. Эквивалентно, если граф не входит в семейство, все большие графы, содержащие его в качестве подструктуры, должны быть также исключены из семейства. Если это верно, всегда существует препятствующее множество (множество графов, не принадлежащих семейству, но все меньшие подструктуры принадлежат семейству). Однако, при некоторых представлениях, что понимать под подструктурой, это препятствующее множество может оказаться бесконечным. Теорема Робертсона – Сеймура доказывает, что в определённых случаях миноров графа, семейство, замкнутое по минорам, всегда имеет конечное препятствующее множество.

Список характеризаций запрещёнными графами (для графов и гиперграфов)

Семейство	Запрещённые графы	Зависимость	Связь
Леса	петли, пары параллельных рёбер и циклы любой длины	подграф	Определение
	петля (для мультиграфов) или треугольник K3 (для простых графов)	минор графа	Определение
Графы без клешней	звезда K1,3	порождённый подграф	Определение
Графы сравнимости		порождённый подграф
Графы без треугольников	треугольник K3	порождённый подграф	Определение
Планарные графы	K5 и K3,3	гомеоморфный подграф	теорема Понтрягина — Куратовского
	K5 и K3,3	минор графа	теорема Вагнера
Внешнепланарные графы	K4 и K2,3	минор графа	Дистель, 4. Планарные графы, с. 115, упр. 23[1]
Внешние 1-планарные графы	пять запрещённых миноров	минор графа	Ауэр, Бахмайер и др.[2]
Графы с фиксировнным родом	конечное препятствующее множество (уже для тороидальных графов размером не меньше 250815)	минор графа	Дистель, 12. Миноры, деревья и полный предпорядок, с. 387, упр. 53[1]
Верхушечный граф	конечное препятствующее множество	минор графа	[3]
Графы, допускающие вложение без зацеплений	Петерсеново семейство графов	минор графа	[4]
Двудольные графы	нечётные циклы	подграф	[5]
Хордальные графы	циклы длины 4 или более	порождённый подграф	[6]
Совершенные графы	нечетные циклы длины 5 и более и их дополнения	порождённый подграф	[7]
Рёберные графы для графов	девять запрещённых подграфов (перечислены здесь)	порождённый подграф	[8]
Объединения графов-кактусов	алмаз, образованный удалением ребра из полного графа K4	минор графа	[9]
Лестницы	K2,3 и его двойственный граф	гомеоморфный подграф	[10]
Циркулярные графы дуг Хелли		порождённый подграф	[11]
Расщепляемые графы	${\displaystyle C_{4},C_{5},{\bar {C_{4}}}(=K_{2}+K_{2})}$	порождённый подграф	[12]
Параллельно-последовательные графы (древесная ширина ${\displaystyle \leqslant 2}$, ширина ветвей ${\displaystyle \leqslant 2}$)	K4	минор графа	Дистель, 7. Экстремальная теория графов, с. 203, упр. 31[1]
Древесная ширина ${\displaystyle \leqslant 3}$	K5, октаэдр, пятиугольная призма, граф Вагнера	минор графа	[13]
Древесная ширина ${\displaystyle <3}$	K4	минор графа	Дистель, 12. Миноры, деревья и полный предпорядок, с. 370, пр. 12.6.2[1]
Ширина ветвей ${\displaystyle \leqslant 3}$	K5, октаэдр, куб, граф Вагнера	минор графа	[14]
Дополнительно сводимые графы (кографы)	Граф P4	порождённый подграф	[15]
Тривиально совершенные графы	Граф P4 и цикл C4	порождённый подграф	[16]
Пороговые графы	Граф P4, цикл C4 и дополнение C4	порождённый подграф	[16]
Рёберные графы 3-однородных линейных гиперграфов	конечный список запрещённых порождённых подграфов с минимальной степенью, не меньшей 19	порождённый подграф	[17]
Рёберные графы k-однородные линейные гиперграфы, k > 3	конечный список запрещённых порождённых подграфов с минимальной степенью рёбер по меньшей мере 2k2 − 3k + 1	порождённый подграф	[18][19]
Основные теоремы
семейство, определённое порождённым наследственным свойством	(не обязательно конечное) препятствующее множество	порождённый подграф
семейство, определённое минорным наследственным свойством	конечное препятствующее множество	минор графа	Теорема Робертсона – Сеймура

См. также

• Гипотеза Эрдёша — Хайналя
• Задача о запрещённых подграфах^[en]
• Минор Матроида^[en]
• Задача Заранкиевича

Примечания

Эта страница в последний раз была отредактирована 10 декабря 2023 в 12:42.