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

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

Эквивалентные характеристики [ править ]

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

  • Они являются сопоставимость графики из порядка теоретико-деревьев . То есть, пусть T будет частичным порядком, таким, что для каждого t ∈ T множество { s ∈ T  : s < t } хорошо упорядочено отношением <, а также T имеет минимальный элемент r . Тогда граф сравнимости T тривиально совершенен, и каждый тривиально совершенный граф может быть сформирован таким образом. [5]
  • Это графы, которые не имеют графа путей P 4 или графа циклов C 4 как индуцированных подграфов . [6]
  • Это графы, в которых каждый связный индуцированный подграф содержит универсальную вершину . [7]
  • Это графики, которые можно представить как интервальные графики для набора вложенных интервалов . Набор интервалов является вложенным, если для каждых двух интервалов в наборе либо они не пересекаются, либо один содержит другой. [8]
  • Это графики, которые одновременно являются хордовыми и кографами . [9] Это следует из характеристики хордовых графов как графов без индуцированных циклов длины больше трех, а кографов как графов без индуцированных путей на четырех вершинах ( P 4 ).
  • Это графики, которые одновременно являются кографами и интервальными графиками. [9]
  • Это графы, которые могут быть сформированы, начиная с одновершинных графов, двумя операциями: несвязным объединением двух меньших тривиально совершенных графов и добавлением новой вершины, смежной со всеми вершинами меньшего тривиально совершенного графа. [10] Эти операции соответствуют в нижележащем лесу формированию нового леса путем несвязанного объединения двух меньших лесов и формированию дерева путем подключения нового корневого узла к корням всех деревьев в лесу.
  • Они являются графами , в которых для каждого ребро уф , в окрестностях из 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. ^ Brandstädt, Le & Spinrad (1999) , определение 2.6.2, стр. 34; Голумбик (1978) .
  2. ^ Wolk (1962) ; Волк (1965) .
  3. Перейти ↑ Donnelly & Isaak (1999) .
  4. ↑ Ян, Чен и Чанг (1996) .
  5. ^ Brandstädt, Le & Спинрад (1999) , теорема 6.6.1, стр. 99; Голумбик (1978) , следствие 4.
  6. ^ Brandstädt, Le & Спинрад (1999) , теорема 6.6.1, стр. 99; Голумбик (1978) , теорема 2. Волк (1962) и Волк (1965) доказали это для графов сравнимости корневых лесов.
  7. ^ Wolk (1962) .
  8. ^ Brandstädt, Le & Spinrad (1999) , стр. 51.
  9. ^ a b Brandstädt, Le & Spinrad (1999) , стр. 248; Ян, Чен и Чанг (1996) , теорема 3.
  10. ↑ Ян, Чен и Чанг (1996) ; Гурски (2006) .
  11. ^ Ян, Чен и Чанг (1996) , теорема 3.
  12. Перейти ↑ Rotem (1981) .
  13. ^ a b c Рубио-Монтьель (2015) .
  14. ^ Brandstädt, Le & Спинрад (1999) , теорема 6.6.3, стр. 100; Голумбик (1978) , следствие 5.
  15. Перейти ↑ Sharan (2002) .
  16. Перейти ↑ Cai (1996) .
  17. ^ Nastos и Гао (2010) .

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

  • Брандштадт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
  • Цай, Л. (1996), "Управляемость с фиксированными параметрами задач модификации графов для наследственных свойств", Письма об обработке информации , 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
  • Голумбик, Мартин Чарльз (1978), «Тривиально совершенные графы», Дискретная математика , 24 (1): 105–107, DOI : 10.1016 / 0012-365X (78) 90178-4 CS1 maint: обескураженный параметр ( ссылка ).
  • Гурски, Франк (2006), "Характеристики копрафов, определяемых ограниченными операциями ширины NLC или ширины клики", Дискретная математика , 306 (2): 271–277, doi : 10.1016 / j.disc.2005.11.014.
  • Настос, Джеймс; Гао, Юн (2010), «Новая стратегия ветвления для задач модификации параметризованного графа», Лекционные заметки по информатике , 6509 : 332–346, arXiv : 1006.3020.
  • Ротем, Д. (1981), "Перестановки, сортируемые стеком", Дискретная математика , 33 (2): 185–196, DOI : 10.1016 / 0012-365X (81) 90165-5 , MR  0599081.
  • Рубио-Монтьель, C. (2015), "Новая характеристика тривиальным совершенных графов", Электронный журнал Теория и приложения Graph , 3 (1): 22-26, DOI : 10,5614 / ejgta.2015.3.1.3.
  • Шаран, Родед (2002), «Проблемы модификации графов и их приложения в геномных исследованиях», докторская диссертация, Тель-Авивский университет..
  • Wolk, Е. С. (1962), "Сопоставимость график дерева", Труды Американского математического общества , (5 -е изд.) 13 : 789-795, DOI : 10,1090 / S0002-9939-1962-0172273-0.
  • Волк, ES (1965), «Заметка о графе сопоставимости дерева», Труды Американского математического общества (1-е изд.), 16 : 17–20, DOI : 10.1090 / S0002-9939-1965-0172274-5.
  • Ян, Цзин-Хо; Чен, Джер-Чжон; Чанг, Джерард Дж (1996), "Квази-пороговые графы", Дискретная прикладная математика , 69 (3): 247-255, DOI : 10.1016 / 0166-218X (96) 00094-7.

Внешние ссылки [ править ]

  • «Тривиально совершенные графы» , Информационная система по классам графов и их включениям.