Кограф

В теорії графів кограф, або додатково звідний граф, чи граф, вільний від P₄, — це граф, який можна отримати з графа з єдиною вершиною K₁ операціями доповнення та об'єднання графів. Таким чином, сімейство кографів — це найменший клас графів, що містить K₁ і замкнутий відносно доповнення та об'єднання.

Кографи відкривали незалежно кілька авторів, починаючи від 1970-х років. Найраніші згадки можна знайти у ЯнгаШаблон:Sfn, ЛерчсаШаблон:Sfn, ЗайншеШаблон:Sfn і Шаблон:Нп. Ці графи називали D*-графамиШаблон:Sfn, спадковими графами Дейсі (після роботи Джеймса Дейсі (James C. Dacey, Jr.) про Шаблон:Нп. Див. роботу СамнераШаблон:Sfn) та графи з двома нащадками Барлета і УріШаблон:Sfn.

В книзі Брандштедта, Лі і ШпінрадаШаблон:Sfn кографи розглянуто детальніше, включно з фактами, наведеними тут.

Визначення та опис

Будь-який кограф можна побудувати, дотримуючись таких правил:

Будь-яка окрема вершина графа є кографом;
Якщо $G$ — кограф, то його доповнення $\overline{G}$ теж кограф;
Якщо $G$ і $H$ — кографи, то їх незв'язане об'єднання $G \cup H$ теж кограф.

Можна дати кілька інших описів кографів. Серед них:

Кограф — це граф, що не містить шляху P₄ з 4 вершинами (тобто довжини 3) як породженого підграфа. Таким чином, граф є кографом тоді й лише тоді, коли для будь-яких чотирьох вершин $v_{1}, v_{2}, v_{3}, v_{4}$ , якщо ${v_{1}, v_{2}}, {v_{2}, v_{3}}$ і ${v_{3}, v_{4}}$ — ребра графа, то хоча б одне з ${v_{1}, v_{3}}, {v_{1}, v_{4}}$ або ${v_{2}, v_{4}}$ теж є ребромШаблон:Sfn.
Кограф — це граф, усі породжені підграфи якого мають властивість, що будь-яка максимальна кліка перетинається з будь-якою максимальною незалежною множиною в єдиній вершині.
Кограф — це граф, у якому будь-який нетривіальний породжений підграф має принаймні дві вершини з однаковими околами.
Кограф — це граф, у якому будь-який зв'язний породжений підграф має незв'язне доповнення.
Кограф — це граф, у всіх зв'язних породжених підграфів якого діаметр не перевищує 2.
Кограф — це граф, у якому будь-яка компонента зв'язності є дистанційно-успадковуваним графом з діаметром, що не перевищує 2.
Кограф — це граф, клікова ширина якого не перевершує 2Шаблон:Sfn.
Кограф — це граф порівнянності послідовно-паралельного часткового порядку Шаблон:Sfn.
Кограф — це граф перестановки Шаблон:Нп Шаблон:Sfn.

Всі повні графи, повні двочасткові графи, порогові графи і графи Турана є кографами. Будь-який кограф є дистанційно-успадковуваним досконалим графом порівнянності.

Кодерева

Кодерево — це дерево, в якому внутрішні вершини позначені числами 0 і 1. Будь-яке кодерево T визначає кограф G, який має вершинами листя кодерева T, а дерево, що має корінь у вершині T, відповідає породженому підграфу в G, визначеному множиною листків-нащадків цієї вершини:

Піддерево, що складається з єдиного листка відповідає породженому підграфу з єдиною вершиною.
Піддерево, що має коренем вершину з міткою 0 відповідає об'єднанню підграфів, утворених нащадками вершини.
Піддерево, що має коренем вершину з міткою 1 відповідає з'єднанню підграфів, утворених нащадками вершини. Тобто, формуємо об'єднання і додаємо ребро між будь-якими двома вершинами, що відповідають двом листкам, розташованим у різних піддеревах. Можна також розглядати з'єднання як доповнення всіх графів, утворених об'єднанням доповнень, з подальшою побудовою доповнення отриманого об'єднання.

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

Обчислювальні властивості

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

Наприклад, щоб знайти максимальну кліку в кографі, обчислюємо, проходячи знизу вгору, максимальну кліку в кожному підграфі, поданому піддеревом кодерева. Для кожної вершини з міткою 0 максимальна кліка — це максимальна кліка, отримана у нащадків вершини. Для вершини з міткою 1 максимальна кліка буде об'єднанням клік, обчислених для нащадків вершини, а розмір цієї кліки дорівнює сумі розмірів клік. Таким чином, поперемінно беручи максимальний розмір і підсумовуючи значення для кожної вершини кодерева, ми обчислимо максимальний розмір кліки, а поперемінно вибираючи максимальну кліку і об'єднуючи, побудуємо саму максимальну кліку. Схожий підхід проходу знизу вгору дозволяє отримати максимальну незалежну множину, хроматичне число, максимальне клікове покриття та існування гамільтонового шляху за лінійний час. Можна також використовувати кодерева для визначення за лінійний час чи є два кографи ізоморфними.

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

Примітки

Шаблон:Reflist

Література

Посилання

Кограф

Зміст

Визначення та опис

Кодерева

Обчислювальні властивості

Примітки

Література

Посилання

Навігаційне меню

Кограф

Визначення та опис

Кодерева

Обчислювальні властивості

Примітки

Література

Посилання

Навігаційне меню

Пошук