Кограф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Граф Турана T(13,4) як приклад кографа

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

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

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

Визначення та опис[ред. | ред. код]

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

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

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

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

Кодерева[ред. | ред. код]

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

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

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

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

Обчислювальні властивості[ред. | ред. код]

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

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

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

Примітки[ред. | ред. код]

  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 // Information Processing Letters. — 1998. — Т. 65 (30 квітня). — С. 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 (30 квітня). — С. 253—277.
  • D. G. Corneil, H. Lerchs, L. Stewart Burlingham. Complement reducible graphs // Discrete Applied Mathematics. — 1981. — Т. 3, вип. 3 (30 квітня). — С. 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 (30 квітня). — С. 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 (30 квітня). — С. 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 (30 квітня). — С. 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. — 30 квітня.
  • Michel Habib, Christophe Paul. A simple linear time algorithm for cograph recognition // Discrete Applied Mathematics. — 2005. — Т. 145, вип. 2 (30 квітня). — С. 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 (30 квітня). — С. 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. — 30 квітня.
  • D. Seinsche. On a property of the class of n-colorable graphs // Journal of Combinatorial Theory, Series B. — 1974. — Т. 16, вип. 2 (30 квітня). — С. 191—193. — DOI:10.1016/0095-8956(74)90063-X.
  • D. P. Sumner. Dacey graphs // J. Austral. Math. Soc.. — 1974. — Т. 18, вип. 04 (30 квітня). — С. 492—502. — DOI:10.1017/S1446788700029232.

Посилання[ред. | ред. код]

  • cograph graphs. Information System on Graph Class Inclusions. Архів оригіналу за 24 Лютого 2021. Процитовано 13 Грудня 2020.
  • Weisstein, Eric W. Cograph(англ.) на сайті Wolfram MathWorld.
Отримано з https://uk.wikipedia.org/w/index.php?title=Кограф&oldid=35422960