Тривіально досконалий граф
Тривіально досконалий граф — це граф із властивістю, що в кожному його породженому підграфі розмір найбільшої (за розміром) незалежної множини дорівнює числу найбільших клік[1][2]. Тривіально досконалі графи першим вивчав Волк[3][4], але назву дав Голумбік[2]. Голумбік писав, що «цю назву вибрано з огляду на тривіальність доведення, що такі графи є досконалими». Тривіально досконалі графи відомі також як графи порівнянності дерев[3][4], деревовидні графи порівнянності[5] і квазіпорогові графи[6].
Еквівалентні описи[ред. | ред. код]
Тривіально досконалі графи мають кілька інших еквівалентних описів:
- Вони є графами порівнянності дерев з теорії порядків[en]. Тобто, нехай T — частковий порядок, такий, що для будь-якого t ∈ 'T' множина {s ∈ T : S < t} є цілком упорядкованою з відношенням < і T має найменший елемент r. Тоді граф порівнянності порядку T тривіально досконалий і будь-який тривіально досконалий граф можна сформувати таким способом[7][8].
- Вони є графами, що не містять шляху P4 або циклу C4 як породжених підграфів[7][9][10]
- Вони є графами, в яких кожен зв'язний породжений підграф містить універсальну вершину[3].
- Вони є графами, які можна подати як інтервальні графи множини вкладених проміжків. Множина проміжків має властивість вкладеності, якщо для будь-яких двох проміжків із множини вони або не перетинаються, або один з них міститься в іншому[11].
- Вони є графами, які одночасно є хордальними графами і кографами[12][13]. Це випливає з опису хордальних графів як графів без породжених циклів довжини чотири і більше і кографів як графів без породжених шляхів з чотирма вершинами (P4).
- Це графи, які водночас є кографами й інтервальними графами[12][13].
- Вони є графами, які можна утворити, починаючи з графів з однією вершиною, за допомогою двох операцій — незв'язного об'єднання двох менших тривіально досконалих графів і додання нової вершини, суміжної всім вершинам меншого тривіально досконалого графу[6][14]. Ці операції відповідають утворенню нового лісу незв'язним об'єднанням двох менших лісів і утворенню дерева з'єднанням нового кореня з коренями всіх дерев лісу.
- Вони є графами, в яких для будь-якого ребра uv околи вершин u і v (включно з самими u і v) вкладені — один окіл має бути околом іншого[13].
- Вони є графами перестановки, визначеними зі сортованих у стеку перестановок[en][15].
- Вони є графами з властивістю, що в кожному його породженому підграфі число клікового покриття дорівнює числу максимальних клік[16].
- Вони є графами з властивістю, що в кожному його породженому підграфі клікове число дорівнює псевдочислу Ґранді[16].
- Вони є графами з властивістю, що хроматичне число кожного його породженого підграфу дорівнює псевдочислу Ґранді[16].
Пов'язані класи графів[ред. | ред. код]
З еквівалентних описів тривіально досконалих графів випливає, що будь-який тривіально досконалий граф є також кографом, хордальним, птолемеєвим, інтервальним і досконалим графом.
Порогові графи — це точно ті графи, які є одночасно тривіально досконалими і є доповненням тривіально досконалих графів (тривіально досконалих кографів)[17][18].
Вітряки є тривіально досконалими.
Розпізнавання[ред. | ред. код]
Чу[19] описує простий алгоритм лінійного часу для розпізнавання тривіально досконалих графів, заснований на лексикографічному пошуку в ширину. Коли алгоритм LexBFS видаляє вершину v з першої множини в черзі, алгоритм перевіряє, що всі сусіди вершини v, що залишилися, належать тій самій множині. Якщо ні, один із заборонених породжених підграфів можна побудувати з v. Якщо перевірка успішна для всіх v, то граф тривіально досконалий. Алгоритм можна модифікувати для перевірки за лінійний час, чи є граф доповненням тривіально досконалого графу.
Визначення, чи стає граф загального вигляду після видалення k ребер тривіально досконалим графом, є NP-повною задачею[20], фіксовано-параметрично розв'язною[21], і її можна розв'язати за час O(2,45k(m+n))[22].
Примітки[ред. | ред. код]
- ↑ Brandstädt, Le, Spinrad, 1999, с. 34 визначення 2.6.2.
- ↑ а б Golumbic, 1978.
- ↑ а б в Wolk, 1962.
- ↑ а б Wolk, 1965.
- ↑ Donnelly, Isaak, 1999.
- ↑ а б Yan, Chen, Chang, 1996.
- ↑ а б Brandstädt, Le, Spinrad, 1999, с. 99 теорема 6.6.1.
- ↑ Golumbic, 1978, с. наслідок 4.
- ↑ Golumbic, 1978, с. теорема 2.
- ↑ Волк(Wolk, 1962)(Wolk, 1965) довів це для графів порівнянності кореневих лісів.
- ↑ Brandstädt, Le, Spinrad, 1999, с. 51.
- ↑ а б Brandstädt, Le, Spinrad, 1999, с. 248.
- ↑ а б в Yan, Chen, Chang, 1996, с. теорема 3.
- ↑ Gurski, 2006.
- ↑ Rotem, 1981.
- ↑ а б в Помилка скрипту: Функції «harvard_core» не існує.
- ↑ Brandstädt, Le, Spinrad, 1999, с. 100 теорема 6.6.3.
- ↑ Golumbic, 1978, с. наслідок 5.
- ↑ Chu, 2008.
- ↑ Помилка скрипту: Функції «harvard_core» не існує.
- ↑ Помилка скрипту: Функції «harvard_core» не існує.
- ↑ Nastos, Gao, 2010.
Література[ред. | ред. код]
- Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X.
- Cai L. Fixed-parameter tractability of graph modification problems for hereditary properties // Information Processing Letters. — 1996. — Т. 58, вип. 4 (13 травня). — С. 171–176. — DOI:.
- Frank Pok Man Chu. A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements // Information Processing Letters. — 2008. — Т. 107, вип. 1 (13 травня). — С. 7–12. — DOI:.
- Sam Donnelly, Garth Isaak. Hamiltonian powers in threshold and arborescent comparability graphs // Discrete Mathematics. — 1999. — Т. 202, вип. 1—3 (13 травня). — С. 33–44. — DOI:.
- Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вип. 1 (13 травня). — С. 105–107. — DOI:.
- Frank Gurski. Characterizations for co-graphs defined by restricted NLC-width or clique-width operations // Discrete Mathematics. — 2006. — Т. 306, вип. 2 (13 травня). — С. 271–277. — DOI:.
- James Nastos, Yong Gao. A Novel Branching Strategy for Parameterized Graph Modification Problems // Lecture Notes in Computer Science. — 2010. — Т. 6509 (13 травня). — С. 332–346.
- Rotem D. Stack sortable permutations // Discrete Mathematics. — 1981. — Т. 33, вип. 2 (13 травня). — С. 185–196. — DOI:.
- Rubio-Montiel C. A new characterization of trivially perfect graphs // Electronic Journal of Graph Theory and Applications. — 2015. — Т. 3, вип. 1 (13 травня). — С. 22–26. — DOI:.
- Roded Sharan. Graph modification problems and their applications to genomic research // PhD Thesis, Tel Aviv University. — 2002. — 13 травня.
- Wolk E. S. The comparability graph of a tree // Proceedings of the American Mathematical Society. — 1962. — Т. 13, вип. 5 (13 травня). — С. 789–795. — DOI:.
- Wolk E. S. A note on the comparability graph of a tree // Proceedings of the American Mathematical Society. — 1965. — Т. 16 (13 травня). — С. 17–20. — DOI:.
- Jing-Ho Yan, Jer-Jeong Chen, Gerard J. Chang. Quasi-threshold graphs // Discrete Applied Mathematics. — 1996. — Т. 69, вип. 3 (13 травня). — С. 247–255. — DOI:.
Посилання[ред. | ред. код]
- Trivially perfect graphs, Information System on Graph Classes and their Inclusions, архів оригіналу за 26 серпня 2012, процитовано 24 червня 2021