Тривиально совершенный граф
В теории графов тривиально совершенный граф — это граф, у которого в каждом из его порожденных подграфов размер максимального независимого множества равен числу максимальных клик . [ 1 ] Тривиально совершенные графы были впервые изучены (Wolk 1962 , 1965 ), но названы Голумбиком (1978) ; Голумбик пишет, что «название было выбрано потому, что тривиально показать, что такой граф совершенен ». Тривиально совершенные графы также известны как графы сравнимости деревьев . [ 2 ] древовидные графы сравнимости , [ 3 ] и квазипороговые графики . [ 4 ]
Эквивалентные характеристики
[ редактировать ]Тривиально совершенные графы имеют несколько других эквивалентных характеристик:
- Это графы сравнимости деревьев теоретико-порядковых . То есть, пусть T является частичным порядком таким, что для каждого t ∈ T множество { s ∈ T : s < t } по хорошо упорядочено отношению < , а также T обладает минимальным элементом r . Тогда граф сравнимости T тривиально совершенен, и таким образом можно сформировать любой тривиально совершенный граф. [ 5 ]
- Это графы, которые не имеют P4 графа путей или C4 в графа циклов качестве индуцированных подграфов . [ 6 ]
- Это графы, в которых каждый связный индуцированный подграф содержит универсальную вершину . [ 7 ]
- Это графики, которые можно представить как графики интервалов для набора вложенных интервалов . Набор интервалов является вложенным, если для каждых двух интервалов в наборе они либо не пересекаются, либо один содержит другой. [ 8 ]
- Это графы, которые одновременно являются хордальными и кографами . [ 9 ] Это следует из характеристики хордальных графов как графов без индуцированных циклов длины больше трёх, а кографов как графов без индуцированных путей на четырёх вершинах ( P 4 ).
- Это графы, которые одновременно являются кографами и интервальными графами. [ 9 ]
- Это графы, которые можно сформировать, начиная с одновершинных графов, двумя операциями: дизъюнктным объединением двух меньших тривиально совершенных графов и добавлением новой вершины, смежной со всеми вершинами меньшего тривиально совершенного графа. [ 10 ] Эти операции в базовом лесу соответствуют формированию нового леса путем непересекающегося объединения двух меньших лесов и формированию дерева путем соединения нового корневого узла с корнями всех деревьев в лесу.
- Это графы, в которых для каждого ребра u и uv окрестности v включая ( ) вложены: одна окрестность должна сами u и v быть подмножеством другой. [ 11 ]
- Это графы перестановок, определенные из перестановок, сортируемых стеком . [ 12 ]
- Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов число кликовых покрытий равно числу максимальных клик . [ 13 ]
- Это графы со свойством, что в каждом из его индуцированных подграфов кликовое число равно псевдочислу Гранди . [ 13 ]
- Это графы со свойством, что в каждом из его индуцированных подграфов хроматическое число равно псевдочислу Гранди . [ 13 ]
Связанные классы графов
[ редактировать ]Из эквивалентных характеристик тривиально совершенных графов следует, что каждый тривиально совершенный граф является также кографом , хордальным графом , птолемеевым графом , интервальным графом и совершенным графом .
Пороговые графы — это в точности графы, которые одновременно являются тривиально совершенными и являются дополнениями к тривиально совершенным графам (котривиально совершенным графам). [ 14 ]
Графы ветряных мельниц тривиально совершенны.
Признание
[ редактировать ]Чу (2008) описывает простой алгоритм с линейным временем для распознавания тривиально совершенных графов, основанный на лексикографическом поиске в ширину . Всякий раз, когда алгоритм LexBFS удаляет вершину v из первого набора в своей очереди, алгоритм проверяет, что все оставшиеся соседи вершины v принадлежат тому же множеству; в противном случае один из запрещенных индуцированных подграфов может быть построен из v . Если эта проверка успешна для каждого v , то граф тривиально совершенен. Алгоритм также можно модифицировать, чтобы за линейное время проверять, является ли граф графом -дополнением тривиально совершенного графа.
Определение того, является ли общий граф удаленным на k ребер от тривиально совершенного графа NP-полным , [ 15 ] управляемый с фиксированными параметрами [ 16 ] и решается за O (2.45 к ( m + n )) время. [ 17 ]
Примечания
[ редактировать ]- ^ Брандштедт, Le & Spinrad (1999) , определение 2.6.2, стр.34; Голуббик (1978) .
- ^ Облако (1962) ; Облако (1965) .
- ^ Доннелли и Исаак (1999) .
- ^ Ян, Чен и Чанг (1996) .
- ^ Брандштедт, Ле и Спинрад (1999) , теорема 6.6.1, с. 99; Голумбик (1978) , следствие 4.
- ^ Брандштедт, Ле и Спинрад (1999) , теорема 6.6.1, с. 99; Голумбик (1978) , теорема 2. Волк (1962) и Волк (1965) доказали это для графов сравнимости корневых лесов.
- ^ Волк (1962) .
- ^ Брандштедт, Le & Spinrad (1999) , стр. 51.
- ^ Перейти обратно: а б Брандштедт, Le & Spinrad (1999) , с. 248; Ян, Чен и Чанг (1996) , теорема 3.
- ^ Ян, Чен и Чанг (1996) ; Гурски (2006) .
- ^ Ян, Чен и Чанг (1996) , теорема 3.
- ^ Ротем (1981) .
- ^ Перейти обратно: а б с Рубио-Монтьель (2015) .
- ^ Брандштедт, Ле и Спинрад (1999) , теорема 6.6.3, с. 100; Голумбик (1978) , следствие 5.
- ^ Шаран (2002) .
- ^ Закон (1996) .
- ^ Настос и Гао (2010) .
Ссылки
[ редактировать ]- Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-Х .
- Цай, Л. (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), «Гамильтоновы степени в пороговых и древесных графах сравнимости», Discrete Mathematics , 202 (1–3): 33–44, doi : 10.1016/S0012-365X(98)00346-X
- Голумбик, Мартин Чарльз (1978), «Тривиально совершенные графики», Discrete Mathematics , 24 (1): 105–107, doi : 10.1016/0012-365X(78)90178-4 .
- Гурски, Франк (2006), «Характеристики кографов, определяемых ограниченными операциями NLC-ширины или кликовой ширины», Discrete Mathematics , 306 (2): 271–277, doi : 10.1016/j.disc.2005.11.014 .
- Настос, Джеймс; Гао, Юн (2010), «Новая стратегия ветвления для задач модификации параметризованных графов», в Ву, Вейли; Даеску, Овидиу (ред.), Комбинаторная оптимизация и приложения – 4-я Международная конференция, COCOA 2010, Каилуа-Кона, Гавайи, США, 18–20 декабря 2010 г., Материалы, Часть II , Конспекты лекций по информатике, том. 6509, Springer, стр. 332–346, arXiv : 1006.3020 , doi : 10.1007/978-3-642-17461-2_27.
- Ротем, Д. (1981), «Перестановки, сортируемые стеком», Discrete Mathematics , 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), «График сопоставимости дерева», Proceedings of the American Mathematical Society , 13 (5-е изд.): 789–795, doi : 10.1090/S0002-9939-1962-0172273-0 .
- Волк, ES (1965), «Заметки о графе сравнимости дерева», Proceedings of the American Mathematical Society , 16 (1-е изд.): 17–20, doi : 10.1090/S0002-9939-1965-0172274-5 .
- Ян, Цзин-Хо; Чен, Джер-Джонг; Чанг, Джерард Дж. (1996), «Квазипороговые графики», Discrete Applied Mathematics , 69 (3): 247–255, doi : 10.1016/0166-218X(96)00094-7 .