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

Trivially perfect graph
Построение тривиально совершенного графа из вложенных интервалов и из отношения достижимости в дереве

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

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

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

Связанные классы графов

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

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

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

Признание

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

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

Примечания

Рекомендации

  • Брандштадт, Андреас; Ле, Ван Банг; Спинрад, Джереми (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.

внешняя ссылка