Тривіально досконалі графи

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

Побудова тривіально досконалого графу зі вкладених інтервалів і з відношення досяжності в дереві

Еквівалентні описи

Тривіально досконалі графи мають кілька інших еквівалентних описів:

• Вони є графами порівнянності ^[en]. Тобто, нехай T — частковий порядок, такий, що для будь-якого t ∈ 'T' множина {s ∈ T : S < t} є цілком упорядкованою з відношенням < і T має найменший елемент r. Тоді граф порівнянності порядку T тривіально досконалий і будь-який тривіально досконалий граф можна сформувати таким способом.
• Вони є графами, що не містять шляху P₄ або циклу C₄ як породжених підграфів
• Вони є графами, в яких кожен зв'язний породжений підграф містить універсальну вершину.
• Вони є графами, які можна подати як інтервальні графи множини вкладених проміжків. Множина проміжків має властивість вкладеності, якщо для будь-яких двох проміжків із множини вони або не перетинаються, або один з них міститься в іншому.
• Вони є графами, які одночасно є хордальними графами і кографами. Це випливає з опису хордальних графів як графів без породжених циклів довжини чотири і більше і кографів як графів без породжених шляхів з чотирма вершинами (P₄).
• Це графи, які водночас є кографами й інтервальними графами.
• Вони є графами, які можна утворити, починаючи з графів з однією вершиною, за допомогою двох операцій — незв'язного об'єднання двох менших тривіально досконалих графів і додання нової вершини, суміжної всім вершинам меншого тривіально досконалого графу. Ці операції відповідають утворенню нового лісу незв'язним об'єднанням двох менших лісів і утворенню дерева з'єднанням нового кореня з коренями всіх дерев лісу.
• Вони є графами, в яких для будь-якого ребра uv околи вершин u і v (включно з самими u і v) вкладені — один окіл має бути околом іншого.
• Вони є графами перестановки, визначеними зі ^[en].
• Вони є графами з властивістю, що в кожному його породженому підграфі число клікового покриття дорівнює числу максимальних клік.
• Вони є графами з властивістю, що в кожному його породженому підграфі клікове число дорівнює псевдочислу Ґранді.
• Вони є графами з властивістю, що хроматичне число кожного його породженого підграфу дорівнює псевдочислу Ґранді.

Пов'язані класи графів

З еквівалентних описів тривіально досконалих графів випливає, що будь-який тривіально досконалий граф є також кографом, хордальним, птолемеєвим, інтервальним і досконалим графом.

Порогові графи — це точно ті графи, які є одночасно тривіально досконалими і є доповненням тривіально досконалих графів (тривіально досконалих кографів).

Вітряки є тривіально досконалими.

Розпізнавання

Чу описує простий алгоритм лінійного часу для розпізнавання тривіально досконалих графів, заснований на лексикографічному пошуку в ширину. Коли алгоритм LexBFS видаляє вершину v з першої множини в черзі, алгоритм перевіряє, що всі сусіди вершини v, що залишилися, належать тій самій множині. Якщо ні, один із заборонених породжених підграфів можна побудувати з v. Якщо перевірка успішна для всіх v, то граф тривіально досконалий. Алгоритм можна модифікувати для перевірки за лінійний час, чи є граф доповненням тривіально досконалого графу.

Визначення, чи стає граф загального вигляду після видалення k ребер тривіально досконалим графом, є NP-повною задачею, фіксовано-параметрично розв'язною, і її можна розв'язати за час O(2,45^k(m+n)).

Примітки

1. Brandstädt, Le, Spinrad, 1999, с. 34 визначення 2.6.2.
2. Golumbic, 1978.
3. Wolk, 1962.
4. Wolk, 1965.
5. Donnelly, Isaak, 1999.
6. Yan, Chen, Chang, 1996.
7. Brandstädt, Le, Spinrad, 1999, с. 99 теорема 6.6.1.
8. Golumbic, 1978, с. наслідок 4.
9. Golumbic, 1978, с. теорема 2.
10. Волк(Wolk, 1962)(Wolk, 1965) довів це для графів порівнянності кореневих лісів.
11. Brandstädt, Le, Spinrad, 1999, с. 51.
12. Brandstädt, Le, Spinrad, 1999, с. 248.
13. Yan, Chen, Chang, 1996, с. теорема 3.
14. Gurski, 2006.
15. Rotem, 1981.
16. Rubio-Montiel, (2015).
17. Brandstädt, Le, Spinrad, 1999, с. 100 теорема 6.6.3.
18. Golumbic, 1978, с. наслідок 5.
19. Chu, 2008.
20. Sharan, (2002).
21. Cai, (1996).
22. Nastos, Gao, 2010.

Література

• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — .
• Cai L. Fixed-parameter tractability of graph modification problems for hereditary properties // . — 1996. — Т. 58, вип. 4 (18 липня). — С. 171–176. — DOI:10.1016/0020-0190(96)00050-6.
• Frank Pok Man Chu. A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements // . — 2008. — Т. 107, вип. 1 (18 липня). — С. 7–12. — DOI:10.1016/j.ipl.2007.12.009.
• Sam Donnelly, Garth Isaak. Hamiltonian powers in threshold and arborescent comparability graphs // . — 1999. — Т. 202, вип. 1—3 (18 липня). — С. 33–44. — DOI:10.1016/S0012-365X(98)00346-X.
• Martin Charles Golumbic. Trivially perfect graphs // . — 1978. — Т. 24, вип. 1 (18 липня). — С. 105–107. — DOI:10.1016/0012-365X(78)90178-4.
• Frank Gurski. Characterizations for co-graphs defined by restricted NLC-width or clique-width operations // . — 2006. — Т. 306, вип. 2 (18 липня). — С. 271–277. — DOI:10.1016/j.disc.2005.11.014.
• James Nastos, Yong Gao. A Novel Branching Strategy for Parameterized Graph Modification Problems // Lecture Notes in Computer Science. — 2010. — Т. 6509 (18 липня). — С. 332–346.
• Rotem D. Stack sortable permutations // . — 1981. — Т. 33, вип. 2 (18 липня). — С. 185–196. — DOI:10.1016/0012-365X(81)90165-5.
• Rubio-Montiel C. A new characterization of trivially perfect graphs // Electronic Journal of Graph Theory and Applications. — 2015. — Т. 3, вип. 1 (18 липня). — С. 22–26. — DOI:10.5614/ejgta.2015.3.1.3.
• Roded Sharan. Graph modification problems and their applications to genomic research // PhD Thesis, Tel Aviv University. — 2002. — 18 липня.
• Wolk E. S. The comparability graph of a tree // . — 1962. — Т. 13, вип. 5 (18 липня). — С. 789–795. — DOI:10.1090/S0002-9939-1962-0172273-0.
• Wolk E. S. A note on the comparability graph of a tree // . — 1965. — Т. 16 (18 липня). — С. 17–20. — DOI:10.1090/S0002-9939-1965-0172274-5.
• Jing-Ho Yan, Jer-Jeong Chen, Gerard J. Chang. Quasi-threshold graphs // . — 1996. — Т. 69, вип. 3 (18 липня). — С. 247–255. — DOI:10.1016/0166-218X(96)00094-7.

Посилання

• , Information System on Graph Classes and their Inclusions, архів оригіналу за 26 серпня 2012, процитовано 24 червня 2021