В теории графов кограф , или приводимый к дополнению граф , или граф, свободный от P 4 , — это граф , который может быть сгенерирован из одновершинного графа K 1 путем дополнения и непересекающегося объединения . То есть семейство кографов — это наименьший класс графов, включающий K 1 и замкнутый относительно дополнения и непересекающегося объединения.
Кографы были открыты независимо несколькими авторами с 1970-х годов; ранние ссылки включают Юнга (1978), Лерха (1971), Зейнше (1974) и Самнера (1974). Их также называют D*-графами , [1] наследственными графами Дейси (в честь соответствующей работы Джеймса К. Дейси-младшего по ортомодулярным решеткам ), [2] и графами с 2-четностью . [3] Они имеют простую структурную декомпозицию, включающую операции непересекающегося объединения и дополнения графа , которые могут быть кратко представлены помеченным деревом и используются алгоритмически для эффективного решения многих проблем, таких как поиск максимальной клики , которые сложны для более общих классов графов.
Особые случаи кографов включают полные графы , полные двудольные графы , кластерные графы и пороговые графы . Кографы, в свою очередь, являются частными случаями дистанционно-наследственных графов , графов перестановок , графов сравнимости и совершенных графов .
Любой кограф можно построить по следующим правилам:
Кографы можно определить как графы, которые можно построить с помощью этих операций, начиная с одновершинных графов. [4] Альтернативно, вместо использования операции дополнения можно использовать операцию соединения, которая состоит из формирования непересекающегося объединения и последующего добавления ребра между каждой парой вершин из и вершиной из .
Можно дать несколько альтернативных характеристик кографов. Среди них:
Кодерево — это дерево, в котором внутренние узлы помечены числами 0 и 1. Каждое кодерево T определяет кограф G , имеющий листья T в качестве вершин, и в котором поддерево с корнем в каждом узле T соответствует индуцированному подграфу в G определяется набором листьев, спускающихся из этого узла:
Эквивалентный способ описания кографа, образованного из кодерева, состоит в том, что две вершины соединены ребром тогда и только тогда, когда самый низкий общий предок соответствующих листьев помечен цифрой 1. И наоборот, каждый кограф может быть представлен таким образом кодеревом. . Если мы требуем, чтобы метки на любом корневом пути этого дерева чередовались между 0 и 1, это представление будет уникальным. [4]
Кографы могут быть распознаны за линейное время, а представление кодерева построено с использованием модульной декомпозиции , [9] уточнения разделов , [10] LexBFS , [11] или расщепленной декомпозиции . [12] После того, как представление кодерева построено, многие знакомые проблемы с графами могут быть решены с помощью простых вычислений снизу вверх на кодеревьях.
Например, чтобы найти максимальную клику в кографе, вычислите в порядке снизу вверх максимальную клику в каждом подграфе, представленном поддеревом кодерева. Для узла с меткой 0 максимальная клика — это максимальная среди клик, вычисленных для дочерних элементов этого узла. Для узла с номером 1 максимальная клика представляет собой объединение клик, вычисленных для дочерних узлов этого узла, и имеет размер, равный сумме размеров дочерних клик. Таким образом, поочередно максимизируя и суммируя значения, хранящиеся в каждом узле кодерева, мы можем вычислить максимальный размер клики, а поочередно максимизируя и объединяя, мы можем построить саму максимальную клику. Подобные вычисления дерева снизу вверх позволяют вычислить максимальное независимое множество , число раскраски вершин , максимальное покрытие клики и гамильтоновость (то есть существование гамильтонова цикла ) за линейное время из представления кодерева кографа. [4] Поскольку кографы имеют ограниченную ширину клики, теорему Курселя можно использовать для проверки любого свойства монадической логики графов второго порядка (MSO 1 ) на кографах в линейное время. [13]
Проблема проверки того, находится ли данный граф на расстоянии k вершин и/или t ребер от кографа, решается с помощью фиксированных параметров . [14] Решение о том, можно ли удалить k -ребро графа в кограф, может быть решено за O * (2,415 k ) времени, [15] и отредактировано k -ребро в кограф за O * (4,612 k ). [16] Если самый большой индуцированный подграф кографа графа можно найти, удалив k вершин из графа, его можно найти за время O * (3,30 k ). [15]
Два кографа изоморфны тогда и только тогда, когда их кодеревья (в канонической форме, в которой нет двух смежных вершин с одинаковой меткой) изоморфны. Благодаря этой эквивалентности можно за линейное время определить, изоморфны ли два кографа, построив их кодеревья и применив тест изоморфизма линейного времени для помеченных деревьев. [4]
Если H — индуцированный подграф кографа G , то H сам является кографом; кодерево для H может быть сформировано путем удаления некоторых листьев из кодерева для G и последующего подавления узлов, имеющих только один дочерний элемент. Из теоремы Краскала о дереве следует , что отношение индуцированного подграфа является хорошим квазиупорядочением кографов. [17] Таким образом, если подсемейство кографов (таких как плоские кографы) замкнуто относительно индуцированных операций над подграфами, то оно имеет конечное число запрещенных индуцированных подграфов . С вычислительной точки зрения это означает, что проверка принадлежности к такому подсемейству может выполняться за линейное время, используя восходящие вычисления на кодереве данного графа, чтобы проверить, содержит ли он какой-либо из этих запрещенных подграфов. Однако, когда размеры двух кографов оба являются переменными, проверка того, является ли один из них индуцированным подграфом другого, является NP-полной . [18]
Кографы играют ключевую роль в алгоритмах распознавания однократно читаемых функций . [19]
Некоторые проблемы со счетом также становятся решаемыми, если входные данные ограничены кографом. Например, существуют алгоритмы с полиномиальным временем для подсчета количества клик или количества максимальных клик в кографе. [4]
Число связных кографов с n вершинами для n = 1, 2, 3,... равно:
При n > 1 несвязных кографов одинаковое количество, поскольку для каждого кографа связен ровно один из него или граф его дополнений .
Каждый полный граф K n является кографом с кодеревом, состоящим из одного 1-узла и n листьев. Аналогично, каждый полный двудольный граф K a , b является кографом. Его кодерево имеет корни в 1-узле, который имеет двух дочерних элементов 0-узла: один с дочерними элементами листа, а другой с дочерними элементами b- листа. Граф Турана может быть образован путем объединения семейства независимых множеств одинакового размера; таким образом, это также кограф с кодеревом, укорененным в 1-узле, который имеет дочерний 0-узел для каждого независимого набора.
Каждый пороговый граф также является кографом. Пороговый граф может быть сформирован путем многократного добавления одной вершины, связанной либо со всеми предыдущими вершинами, либо ни с одной из них; каждая такая операция является одной из операций несвязного объединения или соединения, с помощью которых может быть сформировано кодерево.[20]
Характеризация кографов свойством того, что каждая клика и максимальное независимое множество имеют непустое пересечение, является более сильной версией определяющего свойства сильно совершенных графов , в которых каждый индуцированный подграф содержит независимый набор, пересекающий все максимальные клики. В кографе каждое максимальное независимое множество пересекает все максимальные клики. Таким образом, каждый кограф сильно совершенен. [21]
Тот факт, что кографы свободны от P4 , означает, что они совершенно упорядочиваемы . Фактически, каждый порядок вершин кографа является идеальным порядком, что дополнительно означает, что нахождение максимальной клики и минимальная раскраска могут быть найдены за линейное время с любой жадной раскраской и без необходимости разложения кодерева.
Каждый кограф является дистанционно-наследственным графом , что означает, что каждый индуцированный путь в кографе является кратчайшим путем . Среди дистанционно-наследственных графов можно охарактеризовать кографы как имеющие диаметр не более двух в каждой компоненте связности. Каждый кограф также является графом сравнимости последовательно -параллельного частичного порядка , полученным заменой непересекающихся операций объединения и соединения, с помощью которых кограф был построен, операциями непересекающегося объединения и порядковой суммы на частичных порядках. Поскольку сильно совершенные графы, идеально упорядочиваемые графы, дистанционно-наследственные графы и графы сравнимости являются совершенными графами , кографы также совершенны. [20]
