Кограф

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

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

Кографы открывались независимо несколькими авторами, начиная с 1970-х годов. Самые ранние упоминания можно найти у Янга, Лерчса, Зайнше и Самнера. Эти графы назывались D*-графами, наследственными графами Дейси (после работы Джеймса Дейси [James C. Dacey, Jr.] об ортомодулярных решётках. Смотрите работу Самнера) и графы с двумя потомками Барлета и Ури.

Смотрите книгу Брандштедта, Ли и Шпинрада, где кографы рассмотрены более детально, включая факты, приведённые здесь.

Определение и описание

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

1. Любая отдельная вершина графа является кографом;
2. Если $G$ — кограф, то его дополнение ${\overline {G}}$ тоже кограф;
3. Если $G$ и $H$ — кографы, то их несвязанное объединение $G\cup 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.
• Кограф — это граф сравнимости последовательно-параллельного частичного порядка.
• Кограф — это граф перестановки разделимой перестановки.

Все полные графы, полные двудольные графы, пороговые графы и графы Турана являются кографами. Любой кограф является дистанционно-наследуемым совершенным графом сравнимости.

Кодеревья

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

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

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

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

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

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

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

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

Литература

• Prosenjit Bose, Jonathan Buss, Anna Lubiw. Pattern matching for permutations // Information Processing Letters. — 1998. — Т. 65. — С. 277—283. — doi:10.1016/S0020-0190(97)00209-3.
• Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 978-0-89871-432-6.
• M. Burlet, J. P. Uhry. Topics on Perfect Graphs. — 1984. — Т. 21. — С. 253—277.
• D. G. Corneil, H. Lerchs, L. Stewart Burlingham. Complement reducible graphs // Discrete Applied Mathematics. — 1981. — Т. 3, вып. 3. — С. 163—174. — doi:10.1016/0166-218X(81)90013-5.
• D. G. Corneil, Y. Perl, L. K. Stewart. A linear recognition algorithm for cographs // SIAM Journal on Computing. — 1985. — Т. 14, вып. 4. — С. 926—934. — doi:10.1137/0214065.
• B. Courcelle, S. Olariu. Upper bounds to the clique width of graphs // Discrete Applied Mathematics. — 2000. — Т. 101, вып. 1—3. — С. 77—144. — doi:10.1016/S0166-218X(99)00184-5.
• Peter Damaschke. Induced subgraphs and well-quasi-ordering // Journal of Graph Theory. — 1990. — Т. 14, вып. 4. — С. 427—435. — doi:10.1002/jgt.3190140406.
• Emeric Gioan, Christophe Paul. Split decomposition and graph-labelled trees: characterizations and fully-dynamic[sic] algorithms for totally decomposable graphs. — 2008.
• Michel Habib, Christophe Paul. A simple linear time algorithm for cograph recognition // Discrete Applied Mathematics. — 2005. — Т. 145, вып. 2. — С. 183—197. — doi:10.1016/j.dam.2004.01.011.
• H. A. Jung. On a class of posets and the corresponding comparability graphs // Journal of Combinatorial Theory, Series B. — 1978. — Т. 24, вып. 2. — С. 125—133. — doi:10.1016/0095-8956(78)90013-8.
• H. Lerchs. On cliques and kernels. — 1971.
• D. Seinsche. On a property of the class of n-colorable graphs // Journal of Combinatorial Theory, Series B. — 1974. — Т. 16, вып. 2. — С. 191—193. — doi:10.1016/0095-8956(74)90063-X.
• D. P. Sumner. Dacey graphs // J. Austral. Math. Soc.. — 1974. — Т. 18, вып. 04. — С. 492—502. — doi:10.1017/S1446788700029232.

Ссылки

• cograph graphs  (неопр.). Information System on Graph Class Inclusions.
• Weisstein, Eric W. Cograph (англ.) на сайте Wolfram MathWorld.