Введение

Граф, образованный комплементацией и дизъюнктным объединением

В теории графов кограф, или комплементарно редуцируемый граф, или P4-свободный граф, — это граф, который может быть получен из графа с одной вершиной K1 посредством операций комплементации и дизъюнктного объединения. Иными словами, семейство кографов — это наименьший класс графов, включающий K1 и замкнутый относительно операций комплементации и дизъюнктного объединения. Кографы были открыты независимо несколькими авторами, начиная с 1970-х годов; ранние работы включают , , , и. Они также известны как D*-графы, наследственные графы Дейси (по аналогии с работами Джеймса С. Дейси-младшего по ортомодулярным решёткам) и 2-графы чётности. Они обладают простым структурным разложением, включающим операции дизъюнктного объединения и комплементации, которое может быть компактно представлено помеченным деревом и использоваться алгоритмически для эффективного решения многих задач, таких как поиск максимальной клики, которые сложны для более общих классов графов. Частными случаями кографов являются полные графы, полные двудольные графы, кластерные графы и пороговые графы. В свою очередь, кографы являются частными случаями дистанционно-наследственных графов, графов перестановок, графов сопоставимости и совершенных графов.

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

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

Кограф – это граф, не содержащий путь P4 на 4 вершинах (и, следовательно, длины 3) в качестве индуцированного подграфа. То есть, граф является кографом тогда и только тогда, когда для любых четырех вершин , если и являются ребрами графа, то хотя бы одно из или также является ребром. Кограф – это граф, все индуцированные подграфики которого обладают свойством, что любая максимальная клика пересекает любое максимальное независимое множество в единственной вершине. Кограф – это граф, в котором каждый нетривиальный индуцированный подграф имеет по крайней мере две вершины с одинаковыми окрестностями. Кограф – это граф, в котором каждый связный индуцированный подграф имеет несвязное дополнение. Кограф – это граф, все связные индуцированные подграфики которого имеют диаметр не более 2. Кограф – это граф, в котором каждая связная компонента является дистанционно наследственным графом с диаметром не более 2. Кограф – это граф с шириной клики, не превышающей 2. Кограф – это граф сопоставимости последовательно-параллельного частичного порядка. Кограф – это граф пермутаций отделимой перестановки. Кограф – это граф, все минимальные хордальные замыкания которого являются тривиально совершенными графами. Кограф – это наследственно хорошо раскрашиваемый граф, то есть граф, для которого каждое жадное раскрашивание каждого индуцированного подграфа использует оптимальное количество цветов. Граф является кографом тогда и только тогда, когда любой порядок вершин графа является совершенным порядком, поскольку отсутствие P4 означает, что в любом порядке вершин не возникнет препятствий для совершенного порядка.

Деревья

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

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

Кографы могут быть распознаны за линейное время, и представление кодерева может быть построено с использованием модульного разложения, уточнения разбиений, алгоритма LexBFS или раздельного разложения. После построения представления кодерева многие известные задачи теории графов могут быть решены с помощью простых вычислений снизу вверх на кодереве. Например, для нахождения максимальной клики в кографе вычислите в порядке снизу вверх максимальную клику в каждом подграфе, представленном поддеревом кодерева. Для узла с меткой 0 максимальная клика — это максимальная из клик, вычисленных для дочерних узлов этого узла. Для узла с меткой 1 максимальная клика — это объединение клик, вычисленных для дочерних узлов этого узла, и её размер равен сумме размеров клик дочерних узлов. Таким образом, попеременно максимизируя и суммируя значения, хранящиеся в каждом узле кодерева, можно вычислить максимальный размер клики, а попеременно максимизируя и находя объединения, можно построить саму максимальную клику. Аналогичные вычисления снизу вверх позволяют вычислить максимальное независимое множество, число раскраски вершин, максимальное покрытие кликами и наличие гамильтонова цикла (то есть существование гамильтонова цикла) за линейное время, используя представление кографа в виде дерева. Поскольку кографы имеют ограниченную ширину клики, теорему Курселя можно использовать для проверки любого свойства в монадической логике второго порядка графов (MSO1) на кографах за линейное время. Задача проверки, находится ли данный граф на расстоянии k вершин и/или t ребер от кографа, является параметрически разрешимой. Вопрос о том, можно ли удалить k ребер из графа, чтобы получить кограф, может быть решен за время O*(2.415k), а изменить k ребер в кограф — за время O*(4.612k). Если наибольший индуцированный кографный подграф графа можно найти, удалив k вершин из графа, то это можно сделать за время O*(3.30k). Два кографа изоморфны тогда и только тогда, когда их кодеревья (в канонической форме без двух смежных вершин с одинаковой меткой) изоморфны. Благодаря этой эквивалентности можно за линейное время определить, изоморфны ли два кографа, построив их кодеревья и применив тест изоморфизма для помеченных деревьев за линейное время. Если H является индуцированным подграфом кографа G, то H сам является кографом; кодерево для H может быть сформировано путем удаления некоторых листьев из кодерева для G, а затем подавления узлов, у которых есть только один дочерний узел. Из теоремы Крускала о деревьях следует, что отношение быть индуцированным подграфом является хорошим квазипорядком на кографах. Таким образом, если подсемейство кографов (например, планарные кографы) замкнуто относительно операций с индуцированными подграфами, то оно имеет конечное число запрещенных индуцированных подграфов. С вычислительной точки зрения это означает, что проверка принадлежности к такому подсемейству может быть выполнена за линейное время, используя вычисления снизу вверх на кодереве данного графа для проверки, содержит ли он какой-либо из этих запрещенных подграфов. Однако, когда размеры двух кографов переменные, проверка, является ли один из них индуцированным подграфом другого, является NP-полной задачей. Кографы играют ключевую роль в алгоритмах для распознавания функций, читаемых один раз. Некоторые задачи подсчета также становятся разрешимыми, когда вход ограничен кографом. Например, существуют алгоритмы полиномиального времени для подсчета количества клик или количества максимальных клик в кографе.

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

Количество связных кографов с n вершинами, для n = 1, 2, 3, …, равно:
1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, …
Для n > 1 существует такое же количество несвязных кографов, поскольку для каждого кографа связным является ровно один из него самого или его дополнения.

Подклассы

Каждый полный граф Kn является кографом, с кодеревом, состоящим из одного узла 1 и n листьев. Аналогично, каждый полный двудольный граф Ka,b является кографом. Его кодерево имеет корень в узле 1, который имеет два дочерних узла 0, один с a листьями и один с b листьями. Граф Турана может быть образован объединением семейства независимых множеств одинакового размера; таким образом, он также является кографом, с кодеревом, имеющим корень в узле 1, у которого для каждого независимого множества есть дочерний узел 0. Каждый пороговый граф также является кографом. Пороговый граф может быть образован путем последовательного добавления одной вершины, соединенной либо со всеми предыдущими вершинами, либо ни с одной из них; каждая такая операция соответствует операции непересекающегося объединения или объединения, посредством которых может быть построено кодерево.

Суперклассы

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