Тривиально совершенный граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Построение тривиально совершенного графа из вложенных интервалов и из отношения достижимости в дереве

Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик[1][2]. Тривиально совершенные графы первым изучал Волк[3][4], но название дал Голумбик[2]. Голумбик писал, что «это название было выбрано ввиду тривиальности доказательства, что такие графы являются совершенными.» Тривиально совершенные графы известны также как графы сравнимости деревьев[3][4], древовидные графы сравнимости[5] и квазипороговые графы[6].

Эквивалентные описания[править | править код]

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

  • Они являются графами сравнимости деревьев из теории порядков[англ.]. То есть пусть 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].
  • Они являются графами перестановки, определёнными из сортируемых в стеке перестановок[англ.][15].
  • Они являются графами со свойством, что в каждом его порождённом подграфе число кликового покрытия равно числу максимальных клик[16].
  • Они являются графами со свойством, что в каждом его порождённом подграфе кликовое число равно псевдочислу Гранди[16].
  • Они являются графами со свойством, что хроматическое число каждого его порождённого подграфа равно псевдочислу Гранди[16].

Связанные классы графов[править | править код]

Из эквивалентных описаний тривиально совершенных графов следует, что любой тривиально совершенный граф является также кографом, хордальным, птолемеевым, интервальным и совершенным графом.

Пороговые графы — это в точности те графы, которые являются одновременно тривиально совершенными и являются дополнением тривиально совершенных графов (тривиально совершенных кографов)[17][18].

Мельницы являются тривиально совершенными.

Распознавание[править | править код]

Чу[19] описывает простой алгоритм линейного времени для распознавания тривиально совершенных графов, основанный на лексикографическом поиске в ширину. Когда алгоритм LexBFS удаляет вершину v из первого множества в очереди, алгоритм проверяет, что все оставшиеся соседи вершины v принадлежат тому же множеству. Если нет, один из запрещённых порождённых подграфов может быть построен из v. Если проверка успешна для всех v, то граф тривиально совершенен. Алгоритм можно модифицировать для проверки за линейное время, является ли граф дополнением тривиально совершенного графа.

Определение, получается ли граф общего вида после удаления k рёбер тривиально совершенным графом, является NP-полной задачей[20], фиксированно-параметрически разрешимой[21], и она может быть решена за время O(2,45k(m+n))[22].

Примечания[править | править код]

  1. ↑ Brandstädt, Le, Spinrad, 1999, с. 34 определение 2.6.2.
  2. ↑ 1 2 Golumbic, 1978.
  3. ↑ 1 2 3 Wolk, 1962.
  4. ↑ 1 2 Wolk, 1965.
  5. ↑ Donnelly, Isaak, 1999.
  6. ↑ 1 2 Yan, Chen, Chang, 1996.
  7. ↑ 1 2 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. ↑ 1 2 Brandstädt, Le, Spinrad, 1999, с. 248.
  13. ↑ 1 2 3 Yan, Chen, Chang, 1996, с. теорема 3.
  14. ↑ Gurski, 2006.
  15. ↑ Rotem, 1981.
  16. ↑ 1 2 3 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. — ISBN 0-89871-432-X.
  • Cai L. Fixed-parameter tractability of graph modification problems for hereditary properties // Information Processing Letters. — 1996. — Т. 58, вып. 4. — С. 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 // Information Processing Letters. — 2008. — Т. 107, вып. 1. — С. 7–12. — doi:10.1016/j.ipl.2007.12.009.
  • Sam Donnelly, Garth Isaak. Hamiltonian powers in threshold and arborescent comparability graphs // Discrete Mathematics. — 1999. — Т. 202, вып. 1—3. — С. 33–44. — doi:10.1016/S0012-365X(98)00346-X.
  • Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вып. 1. — С. 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 // Discrete Mathematics. — 2006. — Т. 306, вып. 2. — С. 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. — С. 332–346.
  • Rotem D. Stack sortable permutations // Discrete Mathematics. — 1981. — Т. 33, вып. 2. — С. 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. — С. 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.
  • Wolk E. S. The comparability graph of a tree // Proceedings of the American Mathematical Society. — 1962. — Т. 13, вып. 5. — С. 789–795. — doi:10.1090/S0002-9939-1962-0172273-0.
  • Wolk E. S. A note on the comparability graph of a tree // Proceedings of the American Mathematical Society. — 1965. — Т. 16. — С. 17–20. — doi:10.1090/S0002-9939-1965-0172274-5.
  • Jing-Ho Yan, Jer-Jeong Chen, Gerard J. Chang. Quasi-threshold graphs // Discrete Applied Mathematics. — 1996. — Т. 69, вып. 3. — С. 247–255. — doi:10.1016/0166-218X(96)00094-7.

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Тривиально_совершенный_граф&oldid=135095137