Кограф, или дополнительно сводимый граф, или свободный от P4 граф кратко

Привет, сегодня поговорим про кограф, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое кограф, дополнительно сводимый граф, свободный от p граф , кодеревья, кодерево , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

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

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

Смотрите книгу Брандштедта, Ли и Шпинрада (Brandstädt, Le, Spinrad 1999), где кографы рассмотрены более детально, включая факты, приведенные здесь.

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

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

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

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

• Кограф — это граф, не содержащий путь P4 с 4 вершинами (то есть, длины 3) в качестве порожденного подграфа. Таким образом, граф является кографом тогда и только тогда, когда для любых четырех вершин , если и — ребра графа, то хотя бы одно из или тоже является ребром (Corneil, Lerchs, Burlingham 1981).
• Кограф — это граф, все порожденные подграфы которого обладают свойством, что любая максимальная клика пересекается с любым наибольшим независимым множеством в единственной вершине.
• Кограф — это граф, в котором любой нетривиальный порожденный подграф имеет по меньшей мере две вершины с совпадающими окрестностями.
• Кограф — это граф, в котором любой связный порожденный подграф имеет несвязное дополнение.
• Кограф — это граф, у всех связных порожденных подграфов которого диаметр не превосходит 2.
• Кограф — это граф, в котором любая компонента связности является дистанцирнно-наследуемым графом[en] с диаметром, не превосходящим 2.
• Кограф — это граф, с кликовой шириной[en], не превосходящей 2 (Courcelle, Olariu 2000).
• Кограф — это граф сравнимости последовательно-параллельного частичного порядка[en] (Jung 1978).
• Кограф — это граф перестановки разделимой перестановки[en] (Bose, Buss, Lubiw 1998).

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

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

кодеревья

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

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

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

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

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

Кограф можно распознать за линейное время и построить при этом представление в виде кодерева, если использовать модульное разложение[en] (Corneil, Perl, Stewart 1985), очистку разложения[en] (Habib, Paul 2005) или разложение расщеплением (Gioan, Paul 2008). Как только кодерево построено, многие знакомые задачи теории графов можно решить посредством прохода снизу вверх по кодереву.

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

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

Ссылки

• Prosenjit Bose, Jonathan Buss, Anna Lubiw Pattern matching for permutations // Information Processing Letters. — Т. 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. — В. 4. — Т. 14. — С. 926–934. —DOI:10.1137/0214065.
• B. Courcelle, S. Olariu Upper bounds to the clique width of graphs // Discrete Applied Mathematics. — 2000. — В. 1–3. — Т. 101. — С. 77–144. — DOI:10.1016/S0166-218X(99)00184-5.
• Peter Damaschke Induced subgraphs and well-quasi-ordering // Journal of Graph Theory. — 1990. — В. 4. — Т. 14. — С. 427–435. — DOI:10.1002/jgt.3190140406.
• Emeric Gioan, Christophe Paul Split decomposition and graph-labelled trees: characterizations and [sic]dynamic algorithms for totally decomposable graphs. — 2008..
• Michel Habib, Christophe Paul A simple linear time algorithm for cograph recognition //Discrete Applied Mathematics. — 2005. — В. 2. — Т. 145. — С. 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. — В. 2. — Т. 24. — С. 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. — В. 2. — Т. 16. — С. 191–193. — DOI:10.1016/0095-8956(74)90063-X.
• D. P. Sumner Dacey graphs // J. Austral. Math. Soc.. — 1974. — В. 04. — Т. 18. — С. 492–502. — DOI:10.1017/S1446788700029232.

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