Кограф

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

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

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

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

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

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

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

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

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

Кодеревья

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

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

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

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

Кограф можно распознать за линейное время и построить при этом представление в виде кодерева, если использовать модульное разложение^[10], очистку разложения^{[англ.][11]} или разложение расщеплением^[12]. Как только кодерево построено, многие знакомые задачи теории графов можно решить посредством прохода снизу вверх по кодереву.

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

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

Примечания

Литература

• 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.

Эта страница в последний раз была отредактирована 24 февраля 2024 в 22:34.