Тривиально совершенный граф - Trivially perfect graph
В теория графов, а тривиально совершенный граф является графом со свойством, что в каждом из его индуцированные подграфы размер максимальный независимый набор равно количеству максимальные клики.[1] Тривиально совершенные графы впервые были изучены (Wolk1962, 1965 ), но были названы Голумбик (1978); Голумбик пишет, что «это имя было выбрано, поскольку показать, что такой граф является идеально. "Тривиально совершенные графы также известны как графики сопоставимости деревьев,[2] древовидные графики сопоставимости,[3] и квазипороговые графы.[4]
Эквивалентные характеристики
Тривиально совершенные графы имеют несколько других эквивалентных характеристик:
- Они графики сопоставимости из теоретико-порядковые деревья. То есть пусть Т быть частичный заказ так что для каждого т ∈ Т, набор {s ∈ Т : s < т} является хорошо организованный соотношением <, а также Т обладает минимальным элементом р. Тогда график сопоставимости Т тривиально совершенен, и каждый тривиально совершенный граф может быть сформирован таким образом.[5]
- Это графики, не имеющие п4 граф путей или C4 график цикла в качестве индуцированные подграфы.[6]
- Это графы, в которых каждое связное индуцированный подграф содержит универсальная вершина.[7]
- Это графики, которые можно представить как интервальные графики для набора вложенных интервалы. Набор интервалов является вложенным, если для каждых двух интервалов в наборе либо они не пересекаются, либо один содержит другой.[8]
- Это графики, которые оба хордовый и кографы.[9] Это следует из характеристики хордовых графов как графов без индуцированных циклов длины больше трех, а кографов как графов без индуцированные пути на четырех вершинах (п4).
- Это графики, которые одновременно являются кографами и интервальными графиками.[9]
- Это графы, которые могут быть сформированы, начиная с одновершинных графов, двумя операциями: несвязным объединением двух меньших тривиально совершенных графов и добавлением новой вершины, смежной со всеми вершинами меньшего тривиально совершенного графа.[10] Эти операции соответствуют в нижележащем лесу формированию нового леса путем несвязанного объединения двух меньших лесов и формированию дерева путем соединения нового корневого узла с корнями всех деревьев в лесу.
- Это графы, в которых для каждого ребра УФ, то окрестности из ты и v (включая ты и v сами) вложены: одна окрестность должна быть подмножеством другой.[11]
- Они графы перестановок определяется из перестановки с сортировкой по стеку.[12]
- Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов номер обложки клики равно количеству максимальные клики.[13]
- Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов номер клики равно псевдо-Гранди число.[13]
- Это графы, обладающие тем свойством, что в каждом из его индуцированных подграфов хроматическое число равно псевдо-Гранди число.[13]
Связанные классы графов
Из эквивалентных характеризаций тривиально совершенных графов следует, что каждый тривиально совершенный граф также является cograph, а хордовый граф, а Граф Птолемея, интервальный график, а идеальный график.
В графики пороговых значений - это в точности графы, которые сами по себе тривиально совершенны, и являются дополнениями к тривиально совершенным графам (ко-тривиально совершенные графы).[14]
Графики ветряных мельниц тривиально совершенны.
Признание
Чу (2008) описывает простой линейное время алгоритм распознавания тривиально совершенных графов, основанный на лексикографический поиск в ширину. Когда алгоритм LexBFS удаляет вершину v из первого набора в своей очереди, алгоритм проверяет, что все остальные соседи v принадлежат к одному набору; в противном случае один из запрещенных индуцированных подграфов может быть построен из v. Если эта проверка успешна для каждого v, то граф тривиально совершенен. Алгоритм также можно изменить, чтобы проверить, является ли график дополнительный граф тривиально совершенного графа за линейное время.
Определение того, является ли общий граф k удаление ребер вне тривиально совершенного графа является NP-полным,[15] управляемый с фиксированными параметрами[16] и решается за O (2.45k(м + п)) время.[17]
Примечания
- ^ Brandstädt, Le & Spinrad (1999), определение 2.6.2, стр.34; Голумбик (1978).
- ^ Волк (1962); Волк (1965).
- ^ Доннелли и Исаак (1999).
- ^ Ян, Чен и Чанг (1996).
- ^ Brandstädt, Le & Spinrad (1999), теорема 6.6.1, с. 99; Голумбик (1978), следствие 4.
- ^ Brandstädt, Le & Spinrad (1999), теорема 6.6.1, с. 99; Голумбик (1978), теорема 2. Волк (1962) и Волк (1965) доказал это для графов сопоставимости корневых лесов.
- ^ Волк (1962).
- ^ Brandstädt, Le & Spinrad (1999), п. 51.
- ^ а б Brandstädt, Le & Spinrad (1999), п. 248; Ян, Чен и Чанг (1996), теорема 3.
- ^ Ян, Чен и Чанг (1996); Гурский (2006).
- ^ Ян, Чен и Чанг (1996), теорема 3.
- ^ Ротем (1981).
- ^ а б c Рубио-Монтьель (2015).
- ^ Brandstädt, Le & Spinrad (1999), теорема 6.6.3, с. 100; Голумбик (1978), следствие 5.
- ^ Шаран (2002).
- ^ Цай (1996).
- ^ Настос и Гао (2010).
Рекомендации
- Брандштадт, Андреас; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор, Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
- Цай, Л. (1996), "Управляемость с фиксированными параметрами задач модификации графов для наследственных свойств", Письма об обработке информации, 58 (4): 171–176, Дои:10.1016/0020-0190(96)00050-6.
- Чу, Фрэнк Пок Ман (2008), «Простой алгоритм на основе LBFS, подтверждающий линейное время, для распознавания тривиально совершенных графов и их дополнений», Письма об обработке информации, 107 (1): 7–12, Дои:10.1016 / j.ipl.2007.12.009.
- Доннелли, Сэм; Исаак, Гарт (1999), "Гамильтоновы степени в пороговых и древовидных графах сопоставимости", Дискретная математика, 202 (1–3): 33–44, Дои:10.1016 / S0012-365X (98) 00346-X
- Голумбик, Мартин Чарльз (1978), "Тривиально совершенные графы", Дискретная математика, 24 (1): 105–107, Дои:10.1016 / 0012-365X (78) 90178-4.
- Гурски, Франк (2006), "Характеристики ко-графов, определяемые ограниченными операциями ширины NLC или ширины клики", Дискретная математика, 306 (2): 271–277, Дои:10.1016 / j.disc.2005.11.014.
- Настос, Джеймс; Гао, Юн (2010), "Новая стратегия ветвления для задач модификации параметризованного графа", Конспект лекций по информатике, 6509: 332–346, arXiv:1006.3020.
- Ротем, Д. (1981), "Перестановки, сортируемые стеком", Дискретная математика, 33 (2): 185–196, Дои:10.1016 / 0012-365X (81) 90165-5, МИСТЕР 0599081.
- Рубио-Монтьель, К. (2015), "Новая характеризация тривиально совершенных графов", Электронный журнал теории графов и приложений, 3 (1): 22–26, Дои:10.5614 / ejgta.2015.3.1.3.
- Шаран, Родед (2002), "Проблемы модификации графов и их приложения к геномным исследованиям", Кандидатская диссертация, Тель-Авивский университет.
- Волк, Э. С. (1962), "Граф сравнимости дерева", Труды Американского математического общества (5-е изд.), 13: 789–795, Дои:10.1090 / S0002-9939-1962-0172273-0.
- Wolk, E. S. (1965), "Заметка о графе сравнимости дерева", Труды Американского математического общества (1-е изд.), 16: 17–20, Дои:10.1090 / S0002-9939-1965-0172274-5.
- Ян, Цзин-Хо; Чен, Джер-Чжон; Чанг, Джерард Дж. (1996), "Квазипороговые графы", Дискретная прикладная математика, 69 (3): 247–255, Дои:10.1016 / 0166-218X (96) 00094-7.