Русская Википедия:Кограф
В теории графов кограф, или дополнительно сводимый граф, или граф, свободный от P4, — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов. Таким образом, семейство кографов — это наименьший класс графов, содержащий K1 и замкнутый относительно дополнения и объединения.
Кографы открывались независимо несколькими авторами, начиная с 1970-х годов. Самые ранние упоминания можно найти у ЯнгаШаблон:Sfn, ЛерчсаШаблон:Sfn, ЗайншеШаблон:Sfn и СамнераШаблон:Sfn. Эти графы назывались D*-графамиШаблон:Sfn, наследственными графами Дейси (после работы Джеймса Дейси [James C. Dacey, Jr.] об Шаблон:Не переведено 5. Смотрите работу СамнераШаблон:Sfn) и графы с двумя потомками Барлета и УриШаблон:Sfn.
Смотрите книгу Брандштедта, Ли и ШпинрадаШаблон:Sfn, где кографы рассмотрены более детально, включая факты, приведённые здесь.
Определение и описание
Любой кограф можно построить, следуя следующим правилам:
- Любая отдельная вершина графа является кографом;
- Если <math>G</math> — кограф, то его дополнение <math>\overline{G}</math> тоже кограф;
- Если <math>G</math> и <math>H</math> — кографы, то их несвязанное объединение <math>G\cup H</math> тоже кограф.
Можно дать несколько других описаний кографов. Среди них:
- Кограф — это граф, не содержащий путь P4 с 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.
- Кограф — это граф, все порождённые подграфы которого обладают свойством, что любая максимальная клика пересекается с любым наибольшим независимым множеством в единственной вершине.
- Кограф — это граф, в котором любой нетривиальный порождённый подграф имеет по меньшей мере две вершины с совпадающими окрестностями.
- Кограф — это граф, в котором любой связный порождённый подграф имеет несвязное дополнение.
- Кограф — это граф, у всех связных порождённых подграфов которого диаметр не превосходит 2.
- Кограф — это граф, в котором любая компонента связности является дистанционно-наследуемым графом с диаметром, не превосходящим 2.
- Кограф — это граф, с кликовой шириной, не превосходящей 2Шаблон:Sfn.
- Кограф — это граф сравнимости последовательно-параллельного частичного порядкаШаблон:Sfn.
- Кограф — это граф перестановки Шаблон:Не переведено 5Шаблон:Sfn.
Все полные графы, полные двудольные графы, пороговые графы и графы Турана являются кографами. Любой кограф является дистанционно-наследуемым совершенным графом сравнимости.
Кодеревья
Кодерево — это дерево, в котором внутренние вершины помечены числами 0 и 1. Любое кодерево T определяет кограф G, имеющий листья кодерева T в качестве вершин, а поддерево, имеющее корень в вершине T, соответствует порождённому подграфу в G, определённому множеством листьев-потомков этой вершины:
- Поддерево, состоящее из единственного листа соответствует порождённому подграфу с единственной вершиной.
- Поддерево, имеющее корнем вершину с меткой 0 соответствует объединению подграфов, образованных потомками вершины.
- Поддерево, имеющее корнем вершину с меткой 1 соответствует соединению подграфов, образованных потомками вершины. То есть, формируем объединение и добавляем ребро между любыми двумя вершинами, соответствующими двум листьям, лежащим в разных поддеревьях. Можно также рассматривать соединение как дополнение всех графов, образованных объединением дополнений, с последующим построением дополнения результирующего объединения.
Эквивалентный путь построения кографа из кодерева заключается в том, что две вершины соединяются ребром в том и только в том случае, когда наименьший общий предок соответствующих листьев помечен 1. И наоборот, любой кограф можно представить кодеревом таким способом. Если потребовать, чтобы все метки на всех путах от корня к листьям чередовались, такое представление будет единственнымШаблон:Sfn.
Вычислительные свойства
Кограф можно распознать за линейное время и построить при этом представление в виде кодерева, если использовать модульное разложениеШаблон:Sfn, Шаблон:Не переведено 5Шаблон:Sfn или разложение расщеплениемШаблон:Sfn. Как только кодерево построено, многие знакомые задачи теории графов можно решить посредством прохода снизу вверх по кодереву.
Например, чтобы найти максимальную клику в кографе, вычисляем, проходя снизу вверх, максимальную клику в каждом подграфе, представленным поддеревом кодерева. Для каждой вершины с меткой 0 максимальная клика — это максимальная клика, полученная у потомков вершины. Для вершины с меткой 1 максимальная клика будет объединением клик, вычисленных для потомков вершины, а размер этой клики равен сумме размеров клик. Таким образом, попеременно беря максимальный размер и суммируя значения для каждой вершины кодерева, мы вычислим максимальный размер клики, а попеременно выбирая максимальную клику и объединяя, построим саму максимальную клику. Похожий подход прохода снизу вверх позволяет получить максимальное независимое множество, хроматическое число, максимальное кликовое покрытие и существование гамильтонового пути за линейное время. Можно также использовать кодеревья для определения за линейное время являются ли два кографа изоморфными.
Если H — порождённый подграф кографа G, то H сам по себе является кографом. Кодерево для H можно получить удалением части листьев из кодерева для G с последующим слиянием вершин, имеющих единственного потомка. Из Шаблон:Не переведено 5 следует, что отношение быть порождённым подграфом является Шаблон:Не переведено 5 на кографахШаблон:Sfn. Так, если семейство кографов (таких как планарные кографы) замкнуто относительно операции построения порождённого подграфа, то оно имеет конечное число запрещённых порождённых подграфов. С точки зрения вычислений, это означает, что проверку, принадлежит ли граф такому семейству, можно выполнить за линейное время, если использовать проход снизу вверх по кодереву заданного графа.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
Ссылки
