Кограф

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

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

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

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

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

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

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

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

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

Кодерева

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

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

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

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

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

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

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

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

Примітки

Література

  • Prosenjit Bose, Jonathan Buss, Anna Lubiw. Pattern matching for permutations // Information Processing Letters.  1998. Т. 65 (23 січня). С. 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. — ISBN 978-0-89871-432-6.
  • M. Burlet, J. P. Uhry. Topics on Perfect Graphs.  1984. Т. 21 (23 січня). С. 253—277.
  • D. G. Corneil, H. Lerchs, L. Stewart Burlingham. Complement reducible graphs // Discrete Applied Mathematics.  1981. Т. 3, вип. 3 (23 січня). С. 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 (23 січня). С. 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 (23 січня). С. 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 (23 січня). С. 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. — 23 січня.
  • Michel Habib, Christophe Paul. A simple linear time algorithm for cograph recognition // Discrete Applied Mathematics.  2005. Т. 145, вип. 2 (23 січня). С. 183—197. DOI:10.1016/j.dam.2004.01.011.
  • H. A. Jung. On a class of posets and the corresponding comparability graphs // Journal of Combinatorial Theory, Series B.  1978. Т. 24, вип. 2 (23 січня). С. 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. — 23 січня.
  • D. Seinsche. On a property of the class of n-colorable graphs // Journal of Combinatorial Theory, Series B.  1974. Т. 16, вип. 2 (23 січня). С. 191—193. DOI:10.1016/0095-8956(74)90063-X.
  • D. P. Sumner. Dacey graphs // J. Austral. Math. Soc..  1974. Т. 18, вип. 04 (23 січня). С. 492—502. DOI:10.1017/S1446788700029232.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.