Кограф

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

Граф Турана T(13,4) як приклад кографа

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

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

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

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

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

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

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

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

Кодерева

Кодерева і відповідні кографи. Кожне ребро (u, v) в кографі має відповідний колір найближчого спільного предка вершин u і v в кодереві.

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

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

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

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

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

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

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

Примітки

1. Jung, 1978.
2. Lerchs, 1971.
3. Seinsche, 1974.
4. Sumner, 1974.
5. Burlet, Uhry, 1984.
6. Brandstädt, Le, Spinrad, 1999.
7. Corneil, Lerchs, Burlingham, 1981.
8. Courcelle, Olariu, 2000.
9. Bose, Buss, Lubiw, 1998.
10. Corneil, Perl, Stewart, 1985.
11. Habib, Paul, 2005.
12. Gioan, Paul, 2008.
13. Damaschke, 1990.

Література

• Prosenjit Bose, Jonathan Buss, Anna Lubiw. Pattern matching for permutations // . — 1998. — Т. 65 (5 липня). — С. 277—283. — DOI:10.1016/S0020-0190(97)00209-3.
• Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — .
• M. Burlet, J. P. Uhry. Topics on Perfect Graphs. — 1984. — Т. 21 (5 липня). — С. 253—277.
• D. G. Corneil, H. Lerchs, L. Stewart Burlingham. Complement reducible graphs // Discrete Applied Mathematics. — 1981. — Т. 3, вип. 3 (5 липня). — С. 163—174. — DOI:10.1016/0166-218X(81)90013-5.
• D. G. Corneil, Y. Perl, L. K. Stewart. A linear recognition algorithm for cographs // SIAM Journal on Computing. — 1985. — Т. 14, вип. 4 (5 липня). — С. 926—934. — DOI:10.1137/0214065.
• B. Courcelle, S. Olariu. Upper bounds to the clique width of graphs // Discrete Applied Mathematics. — 2000. — Т. 101, вип. 1—3 (5 липня). — С. 77—144. — DOI:10.1016/S0166-218X(99)00184-5.
• Peter Damaschke. Induced subgraphs and well-quasi-ordering // Journal of Graph Theory. — 1990. — Т. 14, вип. 4 (5 липня). — С. 427—435. — DOI:10.1002/jgt.3190140406.
• Emeric Gioan, Christophe Paul. Split decomposition and graph-labelled trees: characterizations and fully-dynamic[sic] algorithms for totally decomposable graphs. — 2008. — 5 липня.
• Michel Habib, Christophe Paul. A simple linear time algorithm for cograph recognition // Discrete Applied Mathematics. — 2005. — Т. 145, вип. 2 (5 липня). — С. 183—197. — DOI:10.1016/j.dam.2004.01.011. з джерела 20 Січня 2022. Процитовано 13 Грудня 2020.
• H. A. Jung. On a class of posets and the corresponding comparability graphs // Journal of Combinatorial Theory, Series B. — 1978. — Т. 24, вип. 2 (5 липня). — С. 125—133. — DOI:10.1016/0095-8956(78)90013-8.
• H. Lerchs. On cliques and kernels. — Tech. Report, Dept. of Comp. Sci., Univ. of Toronto, 1971. — 5 липня.
• D. Seinsche. On a property of the class of n-colorable graphs // Journal of Combinatorial Theory, Series B. — 1974. — Т. 16, вип. 2 (5 липня). — С. 191—193. — DOI:10.1016/0095-8956(74)90063-X.
• D. P. Sumner. Dacey graphs // J. Austral. Math. Soc.. — 1974. — Т. 18, вип. 04 (5 липня). — С. 492—502. — DOI:10.1017/S1446788700029232.

Посилання

• . Information System on Graph Class Inclusions. Архів оригіналу за 24 Лютого 2021. Процитовано 13 Грудня 2020.
• Weisstein, Eric W. Cograph(англ.) на сайті Wolfram MathWorld.