Просмотр кода страницы Кограф

[[Файл:Turan 13-4.svg|thumb|[[Граф Турана]] ''T''(13,4) как пример кографа]]
В [[Теория графов|теории графов]] '''кограф''', или '''дополнительно сводимый граф''', или '''граф, свободный от ''P''<sub>4</sub>,''' — это [[Граф (математика)|граф]], который можно получить из графа с единственной вершиной ''K''<sub>1</sub> путём операций [[Дополнение графа|дополнения]] и [[Операции над графами|объединения графов]]. Таким образом, семейство кографов — это наименьший класс графов, содержащий ''K''<sub>1</sub> и замкнутый относительно дополнения и объединения.

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

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

== Определение и описание ==
Любой кограф можно построить, следуя следующим правилам:
# Любая отдельная вершина графа является кографом;
# Если <math>G</math> — кограф, то его дополнение <math>\overline{G}</math> тоже кограф;
# Если <math>G</math> и <math>H</math> — кографы, то их несвязанное объединение <math>G\cup H</math> тоже кограф.

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

* Кограф — это граф, не содержащий [[Путь (теория графов)|путь]] ''P''<sub>4</sub> с 4 вершинами (то есть длины 3) в качестве [[Глоссарий теории графов|порождённого подграфа]]. Таким образом, граф является кографом тогда и только тогда, когда для любых четырёх вершин <math>v_1,v_2,v_3,v_4</math>, если <math>\{v_1,v_2\},\{v_2,v_3\}</math> и <math>\{v_3,v_4\}</math> — рёбра графа, то хотя бы одно из <math>\{v_1,v_3\},\{v_1,v_4\}</math> или <math>\{v_2,v_4\}</math> тоже является ребром{{sfn|Corneil, Lerchs, Burlingham|1981}}.
* Кограф — это граф, все порождённые подграфы которого обладают свойством, что любая максимальная [[Клика (теория графов)|клика]] пересекается с любым [[Наибольшее независимое множество|наибольшим независимым множеством]] в единственной вершине.
* Кограф — это граф, в котором любой нетривиальный порождённый подграф имеет по меньшей мере две вершины с совпадающими окрестностями.
* Кограф — это граф, в котором любой связный порождённый подграф имеет несвязное дополнение.
* Кограф — это граф, у всех связных порождённых подграфов которого [[Расстояние (теория графов)|диаметр]] не превосходит 2.
* Кограф — это граф, в котором любая [[Компонента связности графа|компонента связности]] является [[Дистанционно-наследуемый граф|дистанционно-наследуемым графом]] с диаметром, не превосходящим 2.
* Кограф — это граф, с [[Кликовая ширина|кликовой шириной]], не превосходящей 2{{sfn|Courcelle, Olariu|2000}}.
* Кограф — это [[граф сравнимости]] [[Последовательно-параллельный частичный порядок|последовательно-параллельного частичного порядка]]{{sfn|Jung|1978}}.
* Кограф — это [[граф перестановки]] {{не переведено 5|Разделимая перестановка|разделимой перестановки||separable permutation}}{{sfn|Bose, Buss, Lubiw|1998}}.

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

== Кодеревья ==
[[Файл:Cotree and cograph.svg|thumb|360px|Кодеревья и соответствующие кографы. Каждое ребро (''u'', ''v'') в кографе имеет соответствующий цвет ближайшего общего родителя вершин ''u'' и ''v'' в кодереве.]]
'''Кодерево''' — это дерево, в котором внутренние вершины помечены числами 0 и 1. Любое кодерево ''T'' определяет кограф ''G'', имеющий листья кодерева ''T'' в качестве вершин, а поддерево, имеющее корень в вершине ''T'', соответствует порождённому подграфу в ''G'', определённому множеством листьев-потомков этой вершины:
* Поддерево, состоящее из единственного листа соответствует порождённому подграфу с единственной вершиной.
* Поддерево, имеющее корнем вершину с меткой 0 соответствует объединению подграфов, образованных потомками вершины.
* Поддерево, имеющее корнем вершину с меткой 1 соответствует ''соединению'' подграфов, образованных потомками вершины. То есть, формируем объединение и добавляем ребро между любыми двумя вершинами, соответствующими двум листьям, лежащим в разных поддеревьях. Можно также рассматривать ''соединение'' как дополнение всех графов, образованных объединением дополнений, с последующим построением дополнения результирующего объединения.
Эквивалентный путь построения кографа из кодерева заключается в том, что две вершины соединяются ребром в том и только в том случае, когда [[наименьший общий предок]] соответствующих листьев помечен 1. И наоборот, любой кограф можно представить кодеревом таким способом. Если потребовать, чтобы все метки на всех путах от корня к листьям чередовались, такое представление будет единственным{{sfn|Corneil, Lerchs, Burlingham|1981}}.

== Вычислительные свойства ==
Кограф можно распознать за линейное время и построить при этом представление в виде кодерева, если использовать [[модульное разложение]]{{sfn|Corneil, Perl, Stewart|1985}}, {{не переведено 5|Очистка разложения|очистку разложения||partition refinement}}{{sfn|Habib, Paul|2005}} или разложение расщеплением{{sfn|Gioan, Paul|2008}}. Как только кодерево построено, многие знакомые задачи теории графов можно решить посредством прохода снизу вверх по кодереву.

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

Если ''H'' — порождённый подграф кографа ''G'', то ''H'' сам по себе является кографом. Кодерево для ''H'' можно получить удалением части листьев из кодерева для ''G'' с последующим слиянием вершин, имеющих единственного потомка. Из {{не переведено 5|Теорема Крускала о деревьях|теоремы Крускала о деревьях||Kruskal's tree theorem}} следует, что [[Бинарное отношение|отношение]] быть порождённым подграфом является {{не переведено 5|Хороший квазипорядок|хорошим квазипорядком||well-quasi-ordering}} на кографах{{sfn|Damaschke|1990}}. Так, если семейство кографов (таких как [[Планарный граф|планарные]] кографы) замкнуто относительно операции построения порождённого подграфа, то оно имеет конечное число [[Характеризация запрещёнными графами|запрещённых порождённых подграфов]]. С точки зрения вычислений, это означает, что проверку, принадлежит ли граф такому семейству, можно выполнить за линейное время, если использовать проход снизу вверх по кодереву заданного графа.

== Примечания ==
{{примечания|27em}}

== Литература ==
* {{статья
 | автор = Prosenjit Bose, Jonathan Buss, Anna Lubiw
 | заглавие =Pattern matching for permutations
 | mr = 1620935
 | год =1998
 | издание =[[Information Processing Letters]]
 | том =65
 | страницы =277—283
 | doi=10.1016/S0020-0190(97)00209-3
 | ref = Bose, Buss, Lubiw
}}
* {{книга
 | автор = Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad
 | заглавие =Graph Classes: A Survey
 | ссылка = https://archive.org/details/graphclassessurv0000bran
 | издательство =SIAM Monographs on Discrete Mathematics and Applications
 | isbn=978-0-89871-432-6
 | год =1999
 | ref = Brandstädt, Le, Spinrad
}}
* {{статья
 | автор = M. Burlet, J. P. Uhry
 | contribution =Parity Graphs
 | заглавие =Topics on Perfect Graphs
 | series =Annals of Discrete Mathematics
 | том =21
 | год =1984
 | страницы =253—277
 | ref = Burlet, Uhry
}}
* {{статья
 | автор = D. G. Corneil, H. Lerchs, L. Stewart Burlingham
 | заглавие =Complement reducible graphs
 | doi=10.1016/0166-218X(81)90013-5
 | mr =0619603
 | год =1981
 | издание =Discrete Applied Mathematics
 | том =3
 | страницы =163—174
 | выпуск =3
 | ref = Corneil, Lerchs, Burlingham
}}
* {{статья
 | автор = D. G. Corneil, Y. Perl, L. K. Stewart
 | заглавие =A linear recognition algorithm for cographs
 | doi =10.1137/0214065
 | mr =0807891
 | год =1985
 | издание =SIAM Journal on Computing
 | том =14
 | выпуск =4
 | страницы =926—934
 | ref = Corneil, Perl, Stewart
}}
* {{статья
 | автор = B. Courcelle, S. Olariu
 | заглавие = Upper bounds to the clique width of graphs
 | издание = Discrete Applied Mathematics
 | том = 101
 | выпуск = 1—3
 | год = 2000
 | страницы = 77—144
 | doi = 10.1016/S0166-218X(99)00184-5
 | ref = Courcelle, Olariu
}}
* {{статья
 | автор = Peter Damaschke  
 | doi = 10.1002/jgt.3190140406
 | выпуск = 4
 | издание = Journal of Graph Theory
 | mr = 1067237
 | страницы = 427—435
 | заглавие = Induced subgraphs and well-quasi-ordering
 | ссылка = https://archive.org/details/sim_journal-of-graph-theory_1990-09_14_4/page/427
 | том = 14
 | год = 1990
 | ref = Damaschke  
}}
* {{статья
 | автор = Emeric Gioan, Christophe Paul
 | заглавие =Split decomposition and graph-labelled trees: characterizations and fully-dynamic{{sic}} algorithms for totally decomposable graphs
 | год =2008
 | eprint =0810.1823
 | ref = Gioan, Paul
}}
* {{статья
 | автор = Michel Habib, Christophe Paul
 | заглавие =A simple linear time algorithm for cograph recognition
 | url =http://www.lirmm.fr/~paul/Biblio/Postscript/DAM-cographs.pdf
 | doi =10.1016/j.dam.2004.01.011
 | mr =2113140
 | год =2005
 | издание =Discrete Applied Mathematics
 | том =145
 | страницы =183—197
 | выпуск =2
 | ref = Habib, Paul
}}
* {{статья
 | автор = H. A. Jung 
 | заглавие =On a class of posets and the corresponding comparability graphs
 | mr= 0491356
 | год =1978
 | издание =Journal of Combinatorial Theory, Series B
 | том =24
 | страницы =125—133
 | doi =10.1016/0095-8956(78)90013-8
 | выпуск =2
 | ref = Jung
}}
* {{статья
 | автор = H. Lerchs
| заглавие = On cliques and kernels | publisher = Tech. Report, Dept. of Comp. Sci., Univ. of Toronto
 | год = 1971
| ref = Lerchs
}}
* {{статья
 | автор = D. Seinsche
 | заглавие =On a property of the class of ''n''-colorable graphs
 | mr =0337679
 | год =1974
 | издание =Journal of Combinatorial Theory, Series B
 | страницы =191—193
 | doi =10.1016/0095-8956(74)90063-X
 | том =16
 | выпуск =2
 | ref = Seinsche
}}
* {{статья
 | автор = D. P. Sumner
 | заглавие =Dacey graphs
 | mr =0382082
 | год =1974
 | издание =J. Austral. Math. Soc.
 | том =18
 | страницы =492—502
 | doi =10.1017/S1446788700029232
 | выпуск =04
 | ref = Sumner
}}

== Ссылки ==
* {{cite web | url=http://www.graphclasses.org/classes/gc_151.html | title=cograph graphs | work = [http://www.graphclasses.org Information System on Graph Class Inclusions]}}
* {{mathworld | urlname=Cograph | title=Cograph}}
{{rq|checktranslate}}

[[Категория:Теория графов]]
[[Категория:Семейства графов]]
[[Категория:Операции над графами]]