Loading AI tools
граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов Из Википедии, свободной энциклопедии
В теории графов кограф, или дополнительно сводимый граф, или граф, свободный от P4, — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов. Таким образом, семейство кографов — это наименьший класс графов, содержащий K1 и замкнутый относительно дополнения и объединения.
Кографы открывались независимо несколькими авторами, начиная с 1970-х годов. Самые ранние упоминания можно найти у Янга[1], Лерчса[2], Зайнше[3] и Самнера[4]. Эти графы назывались D*-графами[1], наследственными графами Дейси (после работы Джеймса Дейси [James C. Dacey, Jr.] об ортомодулярных решётках[англ.]. Смотрите работу Самнера[4]) и графы с двумя потомками Барлета и Ури[5].
Смотрите книгу Брандштедта, Ли и Шпинрада[6], где кографы рассмотрены более детально, включая факты, приведённые здесь.
Любой кограф можно построить, следуя следующим правилам:
Можно дать несколько других описаний кографов. Среди них:
Все полные графы, полные двудольные графы, пороговые графы и графы Турана являются кографами. Любой кограф является дистанционно-наследуемым совершенным графом сравнимости.
Кодерево — это дерево, в котором внутренние вершины помечены числами 0 и 1. Любое кодерево T определяет кограф G, имеющий листья кодерева T в качестве вершин, а поддерево, имеющее корень в вершине T, соответствует порождённому подграфу в G, определённому множеством листьев-потомков этой вершины:
Эквивалентный путь построения кографа из кодерева заключается в том, что две вершины соединяются ребром в том и только в том случае, когда наименьший общий предок соответствующих листьев помечен 1. И наоборот, любой кограф можно представить кодеревом таким способом. Если потребовать, чтобы все метки на всех путах от корня к листьям чередовались, такое представление будет единственным[7].
Кограф можно распознать за линейное время и построить при этом представление в виде кодерева, если использовать модульное разложение[10], очистку разложения[англ.][11] или разложение расщеплением[12]. Как только кодерево построено, многие знакомые задачи теории графов можно решить посредством прохода снизу вверх по кодереву.
Например, чтобы найти максимальную клику в кографе, вычисляем, проходя снизу вверх, максимальную клику в каждом подграфе, представленным поддеревом кодерева. Для каждой вершины с меткой 0 максимальная клика — это максимальная клика, полученная у потомков вершины. Для вершины с меткой 1 максимальная клика будет объединением клик, вычисленных для потомков вершины, а размер этой клики равен сумме размеров клик. Таким образом, попеременно беря максимальный размер и суммируя значения для каждой вершины кодерева, мы вычислим максимальный размер клики, а попеременно выбирая максимальную клику и объединяя, построим саму максимальную клику. Похожий подход прохода снизу вверх позволяет получить максимальное независимое множество, хроматическое число, максимальное кликовое покрытие и существование гамильтонового пути за линейное время. Можно также использовать кодеревья для определения за линейное время являются ли два кографа изоморфными.
Если H — порождённый подграф кографа G, то H сам по себе является кографом. Кодерево для H можно получить удалением части листьев из кодерева для G с последующим слиянием вершин, имеющих единственного потомка. Из теоремы Крускала о деревьях[англ.] следует, что отношение быть порождённым подграфом является хорошим квазипорядком[англ.] на кографах[13]. Так, если семейство кографов (таких как планарные кографы) замкнуто относительно операции построения порождённого подграфа, то оно имеет конечное число запрещённых порождённых подграфов. С точки зрения вычислений, это означает, что проверку, принадлежит ли граф такому семейству, можно выполнить за линейное время, если использовать проход снизу вверх по кодереву заданного графа.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.