Тривиально идеальный граф
Граф, в котором каждый связный индуцированный подграф имеет универсальную вершину
Построение тривиально совершенного графа из вложенных интервалов и из отношения достижимости в дереве

В теории графов тривиально совершенный граф — это граф со свойством, что в каждом из его индуцированных подграфов размер максимального независимого множества равен числу максимальных клик . [1] Тривиально совершенные графы были впервые изучены (Wolk 1962, 1965), но были названы Golumbic (1978); Golumbic пишет, что «название было выбрано, поскольку тривиально показать, что такой граф совершенен ». Тривиально совершенные графы также известны как графы сравнимости деревьев , [2] древовидные графы сравнимости , [3] и квазипороговые графы . [4]

Эквивалентные характеристики

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

  • Они являются графами сравнимости теоретико -порядковых деревьев . То есть, пусть T — частичный порядок , такой что для каждого t ∈ T множество { s ∈ T  : s < t } вполне упорядочено отношением < , а также T обладает минимальным элементом r . Тогда граф сравнимости T является тривиально совершенным, и каждый тривиально совершенный граф может быть сформирован таким образом. [5]
  • Это графы, которые не имеют графа путей P4 или графа циклов C4 в качестве индуцированных подграфов . [6]
  • Это графы, в которых каждый связный индуцированный подграф содержит универсальную вершину . [7]
  • Это графики, которые можно представить как графики интервалов для набора вложенных интервалов . Набор интервалов является вложенным, если для каждых двух интервалов в наборе либо два не пересекаются, либо один содержит другой. [8]
  • Это графы, которые являются как хордовыми , так и кографами . [9] Это следует из характеристики хордовых графов как графов без индуцированных циклов длины больше трех, а кографов как графов без индуцированных путей на четырех вершинах ( P 4 ).
  • Это графы, которые одновременно являются кографами и интервальными графами. [9]
  • Это графы, которые могут быть сформированы, начиная с графов с одной вершиной, с помощью двух операций: несвязного объединения двух меньших тривиально совершенных графов и добавления новой вершины, смежной со всеми вершинами меньшего тривиально совершенного графа. [10] Эти операции соответствуют в базовом лесу формированию нового леса путем несвязного объединения двух меньших лесов и формированию дерева путем соединения нового корневого узла с корнями всех деревьев в лесу.
  • Это графы, в которых для каждого ребра uv окрестности u и v (включая сами u и v ) являются вложенными: одна окрестность должна быть подмножеством другой. [11 ]
  • Это графы перестановок, определенные из перестановок, сортируемых стеком . [12]
  • Это графы со свойством, что в каждом из его индуцированных подграфов число кликовых покрытий равно числу максимальных клик . [13]
  • Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов число клик равно псевдочислу Гранди. [13]
  • Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов хроматическое число равно псевдочислу Гранди. [13]

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

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

Графики ветряных мельниц тривиально идеальны.

Признание

Чу (2008) описывает простой алгоритм линейного времени для распознавания тривиально совершенных графов, основанный на лексикографическом поиске в ширину . Всякий раз, когда алгоритм LexBFS удаляет вершину v из первого набора в своей очереди, алгоритм проверяет, что все оставшиеся соседи v принадлежат тому же набору; если нет, то один из запрещенных индуцированных подграфов может быть построен из v . Если эта проверка успешна для каждого v , то граф тривиально совершенен. Алгоритм также можно модифицировать для проверки того, является ли граф дополнительным графом тривиально совершенного графа, за линейное время.

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

Примечания

  1. ^ Брандштедт, Le & Spinrad (1999), определение 2.6.2, стр.34; Голуббик (1978).
  2. ^ Волк (1962); Волк (1965).
  3. ^ Доннелли и Айзек (1999).
  4. ^ Янь, Чэнь и Чан (1996).
  5. ^ Брандштедт, Ле и Спинрад (1999), теорема 6.6.1, с. 99; Голумбик (1978), следствие 4.
  6. ^ Brandstädt, Le & Spinrad (1999), теорема 6.6.1, стр. 99; Golumbic (1978), теорема 2. Wolk (1962) и Wolk (1965) доказали это для графов сравнимости корневых лесов.
  7. ^ Волк (1962).
  8. ^ Брандштедт, Le & Spinrad (1999), стр. 51.
  9. ^ ab Brandstädt, Le & Spinrad (1999), стр. 248; Ян, Чен и Чанг (1996), теорема 3.
  10. ^ Ян, Чэнь и Чан (1996); Гурски (2006).
  11. ^ Ян, Чен и Чан (1996), теорема 3.
  12. ^ Ротем (1981).
  13. ^ abc Рубио-Монтьель (2015).
  14. ^ Брандштедт, Ле и Спинрад (1999), теорема 6.6.3, с. 100; Голумбик (1978), следствие 5.
  15. ^ Шаран (2002).
  16. ^ Цай (1996).
  17. ^ Настос и Гао (2010).

Ссылки

  • Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: Обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
  • Cai, L. (1996), «Распознаваемость задач модификации графов для наследственных свойств с фиксированными параметрами», Information Processing Letters , 58 (4): 171– 176, doi :10.1016/0020-0190(96)00050-6.
  • Чу, Фрэнк Пок Мэн (2008), «Простой алгоритм на основе LBFS с линейным временем сертификации для распознавания тривиально совершенных графов и их дополнений», Information Processing Letters , 107 (1): 7– 12, doi :10.1016/j.ipl.2007.12.009.
  • Доннелли, Сэм; Айзек, Гарт (1999), «Гамильтоновы мощности в пороговых и древовидных графах сравнимости», Дискретная математика , 202 ( 1–3 ): 33–44 , doi : 10.1016/S0012-365X(98)00346-X
  • Golumbic, Martin Charles (1978), «Тривиально совершенные графы», Discrete Mathematics , 24 (1): 105– 107, doi :10.1016/0012-365X(78)90178-4.
  • Гурски, Франк (2006), «Характеристики для ко-графов, определяемых ограниченными операциями NLC-ширины или кликовой ширины», Дискретная математика , 306 (2): 271– 277, doi :10.1016/j.disc.2005.11.014.
  • Nastos, James; Gao, Yong (2010), "Новая стратегия ветвления для задач модификации параметризованных графов", в Wu, Weili ; Daescu, Ovidiu (ред.), Combinatory Optimization and Applications – 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, 18–20 декабря 2010 г., Proceedings, Часть II , Lecture Notes in Computer Science, т. 6509, Springer, стр.  332–346 , arXiv : 1006.3020 , doi :10.1007/978-3-642-17461-2_27
  • Ротем, Д. (1981), «Сортируемые стеком перестановки», Дискретная математика , 33 (2): 185– 196, doi :10.1016/0012-365X(81)90165-5, MR  0599081.
  • Рубио-Монтьель, К. (2015), «Новая характеристика тривиально совершенных графов», Электронный журнал теории графов и приложений , 3 (1): 22– 26, doi : 10.5614/ejgta.2015.3.1.3.
  • Шаран, Родед (2002), «Проблемы модификации графов и их применение в геномных исследованиях», докторская диссертация, Тель-Авивский университет.
  • Волк, Э.С. (1962), «Граф сравнимости дерева», Труды Американского математического общества , 13 (5-е изд.): 789– 795, doi : 10.1090/S0002-9939-1962-0172273-0.
  • Волк, Э.С. (1965), «Заметка о графе сравнимости дерева», Труды Американского математического общества , 16 (1-е изд.): 17–20 , doi : 10.1090/S0002-9939-1965-0172274-5.
  • Ян, Джинг-Хо; Чен, Джер-Джонг; Чанг, Джерард Дж. (1996), «Квазипогороговые графики», Дискретная прикладная математика , 69 (3): 247– 255, doi :10.1016/0166-218X(96)00094-7.
  • «Тривиально совершенные графы», Информационная система по классам графов и их включениям
Взято с "https://en.wikipedia.org/w/index.php?title=Trivially_perfect_graph&oldid=1265819642"