Характериза́ція заборо́неними гра́фами — це метод опису сімейства графів або гіперграфів вказанням підструктур, яким заборонено з'являтися всередині будь-якого графа сімейства.
Заборонені графи У теорії графів багато важливих сімейств графів можна описати скінченним числом графів, які не належать сімейству, виключивши із сімейства всі графи, які містять будь-який з цих заборонених графів як (породжений) підграф або мінор. Прототипом явища є теорема Понтрягіна — Куратовського, яка стверджує, що граф планарний (граф, який можна намалювати на площині без перетинів) тоді й лише тоді, коли він не містить будь-якого з двох заборонених підграфів: повного графа K5 і повного двочасткового графа K3,3.
У різних сімействах природа забороненого змінюється. В загальному випадку структура G є членом сімейства тоді й лише тоді, коли заборонена структура не міститься в G. Заборонена підструктура може бути однією з:
підграфи — менші графи, одержувані з підмножини вершин і ребер більшого графа, породжені підграфи — менші графи, одержувані вибором підмножини вершин і включенням всіх ребер, у яких обидві вершини належать цій підмножині, гомеоморфні підграфи (звані також топологічними мінорами) — менші графи, одержувані з підграфів заміною шляхів з вершинами степеня два ребрами, мінорів графа — менших графів, отримуваних з підграфів довільним стягуванням ребер.
Множину структур, яким заборонено належати даному сімейству графів, можна також назвати перешкоджальною множиною сімейства.
Характеризація забороненими графами можна використати в алгоритмах для перевірки, чи належить граф до даного сімейства. У багатьох випадках можна перевірити за поліноміальний час, чи містить даний граф який-небудь член перешкоджальної множини, а тому, чи належить граф до сімейства, визначеного перешкоджальною множиною.
Щоб сімейство мало характеризацію забороненими графами з певним типом підструктур, воно має бути замкнутим за підструктурами. Тобто будь-яка підструктура (даного типу) графа в сімействі повинна бути іншим графом у сімействі. Еквівалентно, якщо граф не входить у сімейство, всі більші графи, які містять його як підструктуру, мають бути виключені із сімейства. Якщо це так, завжди існує перешкоджальна множина (множина графів, які не належать сімейству, але всі менші їх підструктури належать сімейству). Проте, при деяких поданнях, що розуміти під підструктурою, ця перешкоджальна множина може виявитися нескінченною. Теорема Робертсона — Сеймура доводить, що в певних випадках мінорів графа, сімейство, замкнуте за мінорами, завжди має скінченну перешкоджальну множину.
Список характеризацій забороненими графами (для графів і гіперграфів) СімействоЗаборонені графиЗалежністьЗв'язокЛісипетлі, пари паралельних ребер і цикли будь-якої довжинипідграфвизначенняпетля (для мультиграфів) або трикутник K3 (для простих графів)мінор графавизначенняГрафи без клешеньзірка K1,3породжений підграфвизначенняГрафи порівнянностіпороджений підграфГрафи без трикутниківтрикутник K3породжений підграфвизначенняПланарні графиK5 і K3,3гомеоморфний підграфтеорема Понтрягіна — КуратовськогоK5 і K3,3мінор графатеорема ВагнераЗовніпланарні графиK4 і K2,3мінор графаДістель. стор. 107Зовнішні 1-планарні графип'ять заборонених мінорівмінор графаАвер, Бахмаєр та ін..Графи з фіксованим родомскінченна перешкоджальна множинамінор графаДістель стор. 275Верхівковий графскінченна перешкоджальна множинамінор графа.Графи, що допускають вкладення без зачепленьпетерсенове сімейство графівмінор графа.Двочасткові графинепарні циклипідграфХордальні графицикли довжини 4 або більшепороджений підграф.Досконалі графинепарні цикли довжини 5 і більше та їх доповненняпороджений підграф.Реберні графи для графівдев'ять заборонених підграфів (перелічені тут)породжений підграф.Об'єднання графів-кактусівалмаз, утворений видаленням ребра з повного графа K4мінор графа.ДрабиниK2,3 і його двоїстий графгомеоморфний підграф.Циркулярні графи дуг Гелліпороджений підграфРозщепні графипороджений підграфПаралельно-послідовні графи (деревна ширина ≤ 2, ширина галуження ≤ 2)K4мінор графаДістель стор. 327Деревна ширина ≤ 3K5, октаедр, п'ятикутна призма, граф Вагнерамінор графа.Ширина галуження ≤ 3K5, октаедр, куб, граф Вагнерамінор графа.Додатково звідні графи (кографи)Граф P4породжений підграфТривіально досконалі графиГраф P4 і цикл C4породжений підграфПорогові графиГраф P4, цикл C4 і доповнення C4породжений підграфРеберні графи 3-однорідних лінійних гіперграфівскінченний список заборонених породжених підграфів з мінімальним степенем, не меншим від 19породжений підграфРеберні графи k-однорідні лінійні гіперграфи, k > 3скінченний список заборонених породжених підграфів з мінімальним степенем ребер принаймні 2k2 − 3k + 1породжений підграфОсновні теоремиСімейство, визначене породженою успадкованою властивістю(не обов'язково скінченна) перешкоджальна множинапороджений підграфСімейство, визначене мінорною успадкованою властивістюскінченна перешкоджальна множинамінор графатеорема Робертсона — Сеймура
Див. також Гіпотеза Ердеша — Гайналя
Задача Заранкевича
Примітки