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

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

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

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

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

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}\}}$ тоже является ребром .
• Кограф — это граф, все порождённые подграфы которого обладают свойством, что любая максимальная клика пересекается с любым наибольшим независимым множеством в единственной вершине.
• Кограф — это граф, в котором любой нетривиальный порождённый подграф имеет по меньшей мере две вершины с совпадающими окрестностями.
• Кограф — это граф, в котором любой связный порождённый подграф имеет несвязное дополнение.
• Кограф — это граф, у всех связных порождённых подграфов которого диаметр не превосходит 2.
• Кограф — это граф, в котором любая компонента связности является дистанционно-наследуемым графом с диаметром, не превосходящим 2.
• Кограф — это граф, с кликовой шириной , не превосходящей 2 .
• Кограф — это граф сравнимости последовательно-параллельного частичного порядка .
• Кограф — это граф перестановки .

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

Кодеревья

Кодерево — это дерево, в котором внутренние вершины помечены числами 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 // . — 1998. — Т. 65 . — С. 277—283 . — doi : .
• 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 : .
• D. G. Corneil, Y. Perl, L. K. Stewart. A linear recognition algorithm for cographs // SIAM Journal on Computing. — 1985. — Т. 14 , вып. 4 . — С. 926—934 . — doi : .
• B. Courcelle, S. Olariu. Upper bounds to the clique width of graphs // Discrete Applied Mathematics. — 2000. — Т. 101 , вып. 1—3 . — С. 77—144 . — doi : .
• Peter Damaschke. // Journal of Graph Theory. — 1990. — Т. 14 , вып. 4 . — С. 427—435 . — doi : .
• 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 : .
• 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 : .
• 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 : .
• D. P. Sumner. Dacey graphs // J. Austral. Math. Soc.. — 1974. — Т. 18 , вып. 04 . — С. 492—502 . — doi : .

Ссылки

• (неопр.) . .
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .