Кограф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Граф Турана T(13,4) как пример кографа

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

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

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

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

[править | править код]

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

  1. Любая отдельная вершина графа является кографом;
  2. Если  — кограф, то его дополнение тоже кограф;
  3. Если и  — кографы, то их несвязанное объединение тоже кограф.

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

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

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

Кодерево — это дерево, в котором внутренние вершины помечены числами 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.