Кограф

T Граф Турана ( 13,4), пример кографа

В теории графов , кограф или приводимый к дополнению граф , или P ₄ граф, свободный от , — это граф , который может быть сгенерирован из одновершинного графа K ₁ путем дополнения и непересекающегося объединения . То есть семейство кографов — это наименьший класс графов, включающий K ₁ и замкнутый относительно дополнения и непересекающегося объединения.

Кографы были открыты независимо несколькими авторами с 1970-х годов; ранние ссылки включают Юнга (1978) , Лерха (1971) , Зейнше (1974) и Самнера (1974) . Их еще называют D*-графами . наследственные графы Дейси (по мотивам соответствующей работы Джеймса К. Дейси-младшего по ортомодулярным решеткам ), и графы с 2-четностью . Они имеют простую структурную декомпозицию, включающую операции непересекающегося объединения и дополнения графов , которые могут быть кратко представлены помеченным деревом и использоваться алгоритмически для эффективного решения многих проблем, таких как поиск максимальной клики, которые сложны для более общих классов графов.

Особые случаи кографов включают полные графы , полные двудольные графы , кластерные графы и пороговые графы . Кографы, в свою очередь, являются частными случаями дистанционно -наследственных графов , графов перестановок , графов сравнимости и совершенных графов .

Определение

Рекурсивное построение

Любой кограф можно построить по следующим правилам:

1. любой одновершинный граф является кографом;
2. если $G$ является кографом, как и его дополнение, ${\overline {G}}$;
3. если $G$ и $H$ являются кографами, как и их непересекающийся союз, $G\cup H$.

Кографы можно определить как графы, которые можно построить с помощью этих операций, начиная с одновершинных графов. Альтернативно, вместо использования операции дополнения можно использовать операцию соединения, котораясостоит из образования непересекающегося союза $G\cup H$ а затем добавляем ребро между каждой парой вершин из $G$ и вершина из $H$.

Другие характеристики

Можно дать несколько альтернативных характеристик кографов. Среди них:

• Кограф — это граф, который не содержит пути P ₄ на 4 вершинах (и, следовательно, длины 3) в качестве индуцированного подграфа . То есть граф является кографом тогда и только тогда, когда для любых четырех вершин $v_{1},v_{2},v_{3},v_{4}$, если $\{v_{1},v_{2}\},\{v_{2},v_{3}\}$ и $\{v_{3},v_{4}\}$ являются ребрами графа, то хотя бы одно из $\{v_{1},v_{3}\},\{v_{1},v_{4}\}$ или $\{v_{2},v_{4}\}$ это тоже край.
• Кограф — это граф, все индуцированные подграфы которого обладают тем свойством, что любая максимальная клика пересекает любое максимальное независимое множество в одной вершине.
• Кограф — это граф, в котором каждый нетривиальный индуцированный подграф имеет по крайней мере две вершины с одинаковыми окрестностями.
• Кограф — это граф, в котором каждый связный индуцированный подграф имеет несвязное дополнение.
• Кограф — это граф, все связные индуцированные подграфы которого имеют диаметр не более 2.
• Кограф — это граф, в котором каждая компонента связности является дистанционно наследственным графом с диаметром не более 2.
• Кограф — это граф с кликовой шириной не более 2.
• Кограф — это граф сравнимости последовательно -параллельного частичного порядка .
• Кограф — это граф перестановок перестановки сепарабельной .
• Кограф — это граф, все минимальные хордальные пополнения которого являются тривиально совершенными графами .
• Кограф — это наследственно хорошо окрашенный граф , граф, в котором каждая жадная раскраска каждого индуцированного подграфа использует оптимальное количество цветов.
• Граф является кографом тогда и только тогда, когда каждый порядок вершин графа является совершенным порядком , поскольку отсутствие P ₄ означает, что ни в каком порядке вершин не будет препятствий для идеального порядка.

Кодеревья

Кодерево и соответствующий кограф. Каждое ребро ( u , v ) в кографе имеет цвет, соответствующий цвету наименее общего предка u и v в кодереве.

Кодерево — это дерево, в котором внутренние узлы помечены числами 0 и 1. Каждое кодерево T определяет кограф G , имеющий листья T в качестве вершин, и в котором поддерево с корнем в каждом узле T соответствует индуцированному подграфу в G определяется набором листьев, спускающихся из этого узла:

• Поддерево, состоящее из одного листового узла, соответствует индуцированному подграфу с одной вершиной.
• Поддерево с корнем в узле с меткой 0 соответствует объединению подграфов, определенных дочерними элементами этого узла.
• Поддерево с корнем в узле с меткой 1 соответствует объединению подграфов, определенных дочерними элементами этого узла; то есть мы формируем объединение и добавляем ребро между всеми двумя вершинами, соответствующими листьям в разных поддеревьях. Альтернативно, соединение набора графов можно рассматривать как образованное путем дополнения каждого графа, формирования объединения дополнений и последующего дополнения полученного объединения.

Эквивалентный способ описания кографа, образованного из кодерева, состоит в том, что две вершины соединены ребром тогда и только тогда, когда самый низкий общий предок соответствующих листьев помечен цифрой 1. И наоборот, каждый кограф может быть представлен таким образом кодеревом. . Если мы требуем, чтобы метки на любом корневом пути этого дерева чередовались между 0 и 1, это представление будет уникальным.

Вычислительные свойства

Кографы могут быть распознаны за линейное время, а представление кодерева построено с использованием модульной декомпозиции . уточнение раздела , ЛексБФС , или разделенное разложение . После того как представление кодерева построено, многие знакомые проблемы с графами можно решить с помощью простых восходящих вычислений над кодеревьями.

Например, чтобы найти максимальную клику в кографе, вычислите в порядке снизу вверх максимальную клику в каждом подграфе, представленном поддеревом кодерева. Для узла с меткой 0 максимальная клика — это максимальная среди клик, вычисленных для дочерних элементов этого узла. Для узла с номером 1 максимальная клика представляет собой объединение клик, вычисленных для дочерних узлов этого узла, и имеет размер, равный сумме размеров дочерних клик. Таким образом, поочередно максимизируя и суммируя значения, хранящиеся в каждом узле кодерева, мы можем вычислить максимальный размер клики, а поочередно максимизируя и объединяя, мы можем построить саму максимальную клику. Подобные вычисления дерева снизу вверх позволяют вычислить максимальное независимое множество , число раскраски вершин , максимальное покрытие клики и гамильтоновость (то есть существование гамильтонова цикла ) за линейное время из представления кодерева кографа. Поскольку кографы имеют ограниченную ширину клики, теорему Курселя можно использовать для проверки любого свойства монадической логики графов второго порядка (MSO ₁ ) на кографах в линейное время.

Проблема проверки того, находится ли данный граф на расстоянии k вершин и/или t ребер от кографа, решается с помощью фиксированных параметров . Решение о том, можно ли удалить граф с k -ребрами в кограф, можно решить за O ^* (2.415 ^к ) время, и k -ребро отредактировано до кографа в O ^* (4.612 ^к ). Если самый большой индуцированный подграф кографа графа можно найти, удалив k вершин из графа, его можно найти за O ^* (3.30 ^к ) время.

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

Если H — индуцированный подграф кографа G , то H сам является кографом; кодерево для H может быть сформировано путем удаления некоторых листьев из кодерева для G и последующего подавления узлов, имеющих только один дочерний элемент. следует Из теоремы Краскала о дереве , что отношение индуцированного подграфа является хорошим квазиупорядочением кографов. Таким образом, если подсемейство кографов (например, плоские кографы) замкнуто относительно индуцированных операций над подграфами, то оно имеет конечное число запрещенных индуцированных подграфов . С вычислительной точки зрения это означает, что проверка принадлежности к такому подсемейству может выполняться за линейное время, используя восходящие вычисления на кодереве данного графа, чтобы проверить, содержит ли он какой-либо из этих запрещенных подграфов. Однако, когда размеры двух кографов оба переменны, проверка того, является ли один из них индуцированным подграфом другого, является NP-полной .

Кографы играют ключевую роль в алгоритмах распознавания однократно читаемых функций .

Некоторые проблемы со счетом также становятся решаемыми, если входные данные ограничены кографом. Например, существуют алгоритмы с полиномиальным временем для подсчета количества клик или количества максимальных клик в кографе.

Перечисление

Количество связных кографов с n вершинами для n = 1, 2, 3,... равно:

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... (последовательность A000669 в OEIS )

При n > 1 существует одинаковое количество несвязных кографов, поскольку для каждого кографа ровно один из него или граф его дополнений связен .

Связанные семейства графов

Подклассы

Каждый полный граф K _n является кографом с кодеревом, состоящим из одного 1-узла и n листьев. Аналогично, каждый полный двудольный граф K _{a , b} является кографом. Его кодерево имеет корни в 1-узле, который имеет двух дочерних элементов 0-узла: один с дочерними элементами листа, а другой с дочерними элементами b- листа.Граф Турана может быть образован путем объединения семейства независимых множеств одинакового размера; таким образом, это также кограф с кодеревом, укорененным в 1-узле, который имеет дочерний 0-узел для каждого независимого набора.

Каждый пороговый граф также является кографом. Пороговый граф может быть сформирован путем многократного добавления одной вершины, связанной либо со всеми предыдущими вершинами, либо ни с одной из них; каждая такая операция является одной из операций несвязного объединения или соединения, с помощью которых может быть сформировано кодерево.

Суперклассы

Характеризация кографов тем свойством, что каждая клика и максимальное независимое множество имеют непустое пересечение, является более сильной версией определяющего свойства сильно совершенных графов , в которых каждый индуцированный подграф содержит независимый набор, пересекающий все максимальные клики. В кографе каждое максимальное независимое множество пересекает все максимальные клики. Таким образом, каждый кограф сильно совершенен.

Тот факт, что кографы свободны от P4 _, означает, что они совершенно упорядочиваемы . Фактически, каждый порядок вершин кографа является идеальным порядком, что дополнительно означает, что нахождение максимальной клики и минимальная раскраска могут быть найдены за линейное время с любой жадной раскраской и без необходимости разложения кодерева.

Каждый кограф является дистанционно наследственным графом , что означает, что каждый индуцированный путь в кографе является кратчайшим путем . Среди дистанционно-наследственных графов можно охарактеризовать кографы как имеющие диаметр не более двух в каждой компоненте связности.Каждый кограф также является графом сравнимости последовательно -параллельного частичного порядка , полученным заменой операций несвязного объединения и соединения, с помощью которых кограф был построен, операциями несвязного объединения и порядковой суммы на частичных порядках.Поскольку сильно совершенные графы, идеально упорядочиваемые графы, дистанционно-наследственные графы и графы сравнимости являются совершенными графами , кографы также совершенны.

Ссылки

• Берге, К. ; Дюше, П. (1984), «Сильно совершенные графы», Темы о совершенных графах , Математические исследования Северной Голландии, том. 88, Амстердам: Северная Голландия, стр. 57–61, номер документа : 10.1016/S0304-0208(08)72922-0 , MR   0778749 .
• Бозе, Просенджит ; Басс, Джонатан; Любив, Анна (1998), «Сопоставление шаблонов для перестановок», Information Processing Letters , 65 (5): 277–283, doi : 10.1016/S0020-0190(97)00209-3 , MR   1620935 .
• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми П. (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  978-0-89871-432-6 .
• Берлет, М.; Ури, Дж.П. (1984), «Графы четности», Темы о совершенных графах , Анналы дискретной математики, том. 21, стр. 253–277 .
• Бретчер, А.; Корней, Д.Г. ; Хабиб, М.; Пол, К. (2008), «Простой алгоритм распознавания кографов LexBFS с линейным временем», SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296, CiteSeerX   10.1.1.188.5016 , doi : 10.1137/060664690 .
• Кай, Л. (1996), «Разрешимость задач модификации графов для наследственных свойств с фиксированными параметрами», Information Processing Letters , 58 (4): 171–176, doi : 10.1016/0020-0190(96)00050-6 .
• Кристен, Клод А.; Селков, Стэнли М. (1979), «Некоторые идеальные свойства раскраски графов», Журнал комбинаторной теории , серия B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR   0539075 .
• Корней, Д.Г. ; Лерхс, Х.; Стюарт Берлингэм, Л. (1981), «Дополнительные приводимые графы», Discrete Applied Mathematics , 3 (3): 163–174, doi : 10.1016/0166-218X(81)90013-5 , MR   0619603 .
• Корней, Д.Г. ; Перл, Ю.; Стюарт, Л.К. (1985), «Алгоритм линейного распознавания кографов», SIAM Journal on Computing , 14 (4): 926–934, doi : 10.1137/0214065 , MR   0807891 .
• Курсель, Б.; Маковский, Дж. А.; Ротикс, У. (2000), «Задачи оптимизации, решаемые за линейное время, на графах ограниченной ширины клики», Теория вычислительных систем , 33 (2): 125–150, doi : 10.1007/s002249910009 , MR   1739644 , S2CID   15402031 , Zbl   1009.68102 .
• Курсель, Б. ; Олариу, С. (2000), «Верхние границы кликовой ширины графов» , Discrete Applied Mathematics , 101 (1–3): 77–144, doi : 10.1016/S0166-218X(99)00184-5 , MR   1743732 .
• Дамашке, Питер (1990), «Индуцированные подграфы и хороший квазиупорядочение», Journal of Graph Theory , 14 (4): 427–435, doi : 10.1002/jgt.3190140406 , MR   1067237 .
• Дамашке, Питер (1991), «Индуцированный изоморфизм субрафов для кографов NP-полный», в Мёринге, Рольфе Х. (редактор), Теоретико-графовые концепции в информатике: 16-й международный семинар WG '90 Берлин, Германия, 20 июня –22, 1990, Труды , Конспекты лекций по информатике, том. 484, Springer-Verlag, стр. 72–78, номер документа : 10.1007/3-540-53832-1_32 .
• Джоан, Эмерик; Пол, Кристоф (2012), «Разделенная декомпозиция и деревья с метками графов: характеристики и полностью динамические алгоритмы для полностью разложимых графов», Discrete Applied Mathematics , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016/j. дам.2011.05.007 , МР   2901084 , S2CID   6528410 .
• Голумбик, Мартин С .; Гурвич, Владимир (2011), «Функции однократного чтения» (PDF) , в Crama, Yves; Хаммер, Питер Л. (ред.), Булевы функции , Энциклопедия математики и ее приложений, том. 142, Издательство Кембриджского университета, Кембридж, стр. 519–560, doi : 10.1017/CBO9780511852008 , ISBN.  978-0-521-84751-3 , МР   2742439 .

• Хабиб, Мишель; Пол, Кристоф (2005), «Простой алгоритм распознавания кографов с линейным временем» (PDF) , Discrete Applied Mathematics , 145 (2): 183–197, doi : 10.1016/j.dam.2004.01.011 , MR   2113140 .
• Юнг, Х.А. (1978), «Об одном классе частично упорядоченных множеств и соответствующих графах сравнимости», Журнал комбинаторной теории , серия B, 24 (2): 125–133, doi : 10.1016/0095-8956(78)90013-8 , МР   0491356 .
• Лерхс, Х. (1971), О кликах и ядрах , Tech. Отчет, Отдел комп. наук, унив. Торонто .
• Лю, Юньлун Лю; Ван, Цзяньсинь; Го, Цзюн; Чен, Цзянер (2012), «Сложность и параметризованные алгоритмы редактирования кографов», Theoretical Computer Science , 461 : 45–54, doi : 10.1016/j.tcs.2011.11.040 .
• Настос, Джеймс; Гао, Юн (2010), «Новая стратегия ветвления для задач модификации параметризованных графов», в Ву, Вейли; Даеску, Овидиу (ред.), Комбинаторная оптимизация и приложения – 4-я Международная конференция, COCOA 2010, Каилуа-Кона, Гавайи, США, 18–20 декабря 2010 г., Материалы, Часть II , Конспекты лекций по информатике, том. 6509, Springer, стр. 332–346, arXiv : 1006.3020 , doi : 10.1007/978-3-642-17461-2_27.
• Парра, Андреас; Шеффлер, Петра (1997), «Характеристики и алгоритмические применения вложений хордальных графов», 4-й семинар Твенте по графам и комбинаторной оптимизации (Энсхеде, 1995), Дискретная прикладная математика , 79 (1–3): 171–188, doi : 10.1016 /S0166-218X(97)00041-3 , МР   1478250 .
• Зейнше, Д. (1974), «Об одном свойстве класса n -раскрашиваемых графов», Журнал комбинаторной теории , серия B, 16 (2): 191–193, doi : 10.1016/0095-8956(74)90063 -Х , МР   0337679 .
• Самнер, Д. П. (1974), «Графики Дейси», Журнал Австралийского математического общества , 18 (4): 492–502, doi : 10.1017/S1446788700029232 , MR   0382082 .

Внешние ссылки

• «Кографы-графы» , Информационная система по включению классов графов
• Вайсштейн, Эрик В. , «Кограф» , MathWorld