Косе розбиття

Косе розбиття хордального графа. Верхня та нижня частини ліворуч не пов'язані між собою, а праворуч утворюють граф із незв'язним доповненням.

Косе розбиття́ графа — розбиття вершин графа на дві підмножини у вигляді незв'язного породженого підграфа та доповнення; відіграє важливу роль у теорії досконалих графів.

Визначення

Косе розбиття графа $G$ — це розбиття вершин графа на дві підмножини $X$ і $Y$, для яких породжений підграф $G[X]$ незв'язний, а породжений підграф $G[Y]$ є доповненням незв'язного графа (далі — «ко-незв'язного»). Еквівалентно косе розбиття графа $G$ можна описати як розбиття вершин графа $G$ на такі чотири підмножини $A$, $B$, $C$ і $D$, в яких відсутні ребра з $A$ в $B$, але присутні всі можливі ребра з $C$ в $D$. Для такого розбиття породжені підграфи $G[A\cup B]$ і $G[C\cup D]$ незв'язні і ко-незв'язні відповідно, тому можна взяти $X=A\cup B$ і $Y=C\cup D$.

Приклади

Будь-який шлях із чотирма і більше вершинами має косе розбиття, в якому ко-зв'язна множина $Y$ є одним зі внутрішніх ребер шляху, а незв'язна множина $X$ складається з обох вершин цього ребра. Однак, неможливе косе розбиття для циклів будь-якої довжини — несуттєво, які підмножини циклів вибрано як множину $X$, доповнення множини $Y$ матиме те саме число зв'язних компонент, так що неможливо і $X$ розкласти, і щоб $Y$ була ко-незв'язним.

Якщо граф має косе розбиття, то таке розбиття має і його доповнення. Наприклад, доповнення шляхів мають косі розбиття, а доповнення циклів — ні.

Особливі випадки

Якщо граф незв'язний, то, за винятком трьох простих випадків (порожній граф, граф з одним ребром і трьома вершинами або досконале парування на чотирьох вершинах), він має косе розбиття, в якому ко-незв'язний бік розбиття складається з кінцевих точок одного ребра, і незв'язний бік складається з решти вершин. З тієї ж причини, якщо доповнення графа незв'язне, то, за винятком відповідної множини з трьох випадків, він повинен мати косе розбиттяШаблон:Sfn.

Якщо граф має кліковий сепаратор (кліку, видалення якої робить решту вершин незв'язними) з більш ніж однією вершиною, розбиття на кліку і решту вершин утворює косе розбиття. Кліковий розріз з однією вершиною є шарніром. Якщо така вершина існує, то, за невеликим числом простих винятків, існує косе розбиття, в якому ко-незв'язна сторона складається з цієї вершини й одного з її сусідівШаблон:Sfn.

Зірковий розріз у графі $G$ — це вершинний сепаратор, у якому одна з вершин суміжна з усіма іншими вершинами сепаратора. Будь-який кліковий сепаратор є зірковим розрізом. Граф із зоряним розрізом (з більш ніж однією вершиною) обов'язково має косе розбиття, в якому ко-незв'язний підграф складається з вершин зіркового розрізу, а незв'язний підграф складається з решти вершинШаблон:Sfn.

Модуль (або однорідна множина) є нетривіальною підмножиною $H$ вершин графа $G$, таким, що для будь-якої вершини $v$, що не належить $H$, $v$ або суміжна всім вершинам у $H$, або жодній з них. Якщо граф $G$ має модуль $H$ і поза ним існують вершини, суміжні всім вершинам $H$, а інші вершини поза ним не суміжні жодній вершині з $H$, то $G$ має зірковий розріз, що складається з однієї вершини в модулі разом із її сусідами поза модулем. З іншого боку, якщо існує модуль, у якому одна з цих двох підмножин порожня, то граф незв'язний або ко-незв'язний, і знову (за винятком трьох простих випадків) він має косе розбиттяШаблон:Sfn.

Історія

Косі розбиття ввів [[Вацлав Хватал|ХваталШаблон:Sfn]] у зв'язку з досконалими графами. Хватал довів, що мінімально недосконалий граф не може мати зіркового розрізу. Зрозуміло, що незв'язні графи не можуть бути мінімально недосконалими, і було відомо також, що графи з кліковими сепараторами або модулями не можуть бути мінімально недосконалими. Шаблон:Нп на початку 1960-х років висловив гіпотезу, що досконалі графи повинні збігатися з графами Бержа, графами без породженого непарного циклу (довжиною п'ять або більше) або його доповнення, і (оскільки цикли та їх доповнення не мають косих розбиттів) ніякий граф, що не є мінімальним графом Бержа, не може мати косого розбиття. Зацікавлений цими результатами, Хватал висловив гіпотезу, що ніякий мінімальний недосконалий граф не може мати косого розбиття. Деякі автори довели окремі випадки цієї гіпотези, але вона залишається невирішеною вже довгий час.

Косі розбиття набули особливої важливості, коли Чудновська, Робертсон, Сеймур і ТомасШаблон:Sfn використали їх для доведення сильної теореми про досконалі графи, що графи Бержа це те саме, що й досконалі графи. Чудновська та її група не змогли довести гіпотезу Хватала безпосередньо, але довели слабший результат, що мінімальний контрприклад теоремі (якби такий існував) повинен мати збалансоване косе розбиття, в якому кожен породжений шлях з кінцем на одному боці розбиття та внутрішніми вершинами на іншому боці має парну довжину. Цей результат став ключовою лемою в їхньому доведенні, а повна версія леми Хватала випливає з їхньої теоремиШаблон:Sfn.

У структурній теорії графів

Косі розбиття утворюють ключову компоненту структурного розкладання досконалих графів, яке використали Чудновська, Робертсон, Сеймур і ТомасШаблон:Sfn як частину доведення сильної теореми про досконалі графи. Чудновська зі співавторами показала, що будь-який досконалий граф або належить до п'яти базових класів досконалих графів, або має один із чотирьох типів розкладів на простіші графи і одним з цих розкладів є косе розбиття.

Простий приклад структурного розкладу з використанням косих розбиттів дав СеймурШаблон:Sfn. Він зауважив, що будь-який граф порівнянності є повним, або двочастковим, або має косі розбиття. Дійсно, якщо будь-який елемент частково впорядкованої множини є або мінімальним елементом або максимальним елементом, то відповідний граф порівнянності двочастковий. Якщо впорядкування є повним, то відповідний граф порівнянності повний. Якщо жодна з цих умов не виконується, але будь-який елемент, який не є ні мінімальним, ні максимальним, порівнянний з усіма іншими елементами, то або розбиття на мінімальні і не мінімальні елементи (якщо є більше одного мінімального елемента), або розбиття на максимальні та не максимальні елементи (якщо є більше одного максимального елемента) формує зірковий розріз. У випадку, що залишився, існує елемент $x$ часткового порядку, який ні мінімальний, ні максимальний і порівняний не з усіма іншими елементами. У цьому випадку існує косе розбиття (доповнення зіркового розрізу), в якому ко-незв'язний бік складається з елементів, порівнянних з $x$ (за винятком самого $x$), а незв'язний бік складається з решти елементів.

Хордальні графи мають навіть простіші розклади схожого вигляду — вони або повні, або мають кліковий сепаратор. ГейвордШаблон:Sfn показав аналогічно, що будь-який зв'язний і ко-зв'язний слабкий хордальний граф (граф з породженим циклом довжини більше чотирьох або його доповненням) з чотирма або більше вершинами має зірковий розріз або його доповнення, звідки за лемою Хватала випливає, що будь-який такий граф досконалий.

Алгоритми та складність

Косе розбиття цього графа, якщо воно існує, можна знайти за поліноміальний час. Це спочатку показали Фігейредо, Кляйн, Кохаякава та РідШаблон:Sfn, але з дуже великим часом роботи $O(n^{101})$, де $n$ — число вершин вхідного графа. Кеннеді та РідШаблон:Sfn покращили час роботи до $O(n^{4}m)$. Тут $m$ — число ребер.

Задача перевірки, чи містить граф косе розбиття, в якому одна з частин ко-незв'язного боку незалежна, є NP-повною задачеюШаблон:Sfn. Перевірка, чи містить довільний граф збалансоване косе розбиття також є NP-повною задачею, але задача розв'язна за поліноміальний час для досконалих графівШаблон:Sfn.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття.