Идеальный график

График дуопризмы 3-3 ( линейный график $K_{3,3}$) идеально. Здесь он раскрашен тремя цветами, при этом выделена одна из его трехвершинных максимальных клик.

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

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

Теорема о совершенном графе утверждает, что граф дополнений идеального графа также совершенен. Теорема о сильном идеальном графе характеризует идеальные графы с точки зрения определенных запрещенных индуцированных подграфов , что приводит к алгоритму с полиномиальным временем для проверки того, является ли граф совершенным.

Определения и характеристики

Семивершинный цикл и его дополнение, показывающие в каждом случае оптимальную раскраску и максимальную клику (показаны толстыми ребрами). Ни один из графов не использует количество цветов, равное размеру его клики, поэтому ни один из них не идеален.

Клика — в неориентированном графе это подмножество его вершин, смежных друг с другом, например подмножества вершин, соединенных тяжелыми ребрами на иллюстрации. Номер клики — это количество вершин в самой большой клике: две в иллюстрированном цикле из семи вершин и три в другом показанном графе. присваивает Раскраска графа цвет каждой вершине, так что каждые две соседние вершины имеют разные цвета, как также показано на рисунке. Хроматическое число графа — это минимальное количество цветов в любой раскраске. Показанные раскраски являются оптимальными, поэтому хроматическое число равно трем для 7-цикла и четырем для другого показанного графа. Вершины любой клики должны иметь разные цвета, поэтому хроматическое число всегда больше или равно номеру клики. Для некоторых графов они равны; для других, таких как показанные, они неравны. Идеальные графы определяются как графы, для которых эти два числа равны не только в самом графе, но и в каждом индуцированный подграф, полученный удалением некоторых его вершин.

Два взаимодополняющих совершенных графа

Теорема о совершенном графе утверждает, что граф дополнений идеального графа сам по себе совершенен. Дополнительный граф имеет ребро между двумя вершинами тогда и только тогда, когда данный граф его не имеет. Клика в графе дополнений соответствует независимому множеству в данном. Раскраске дополнительного графа соответствует кликовое покрытие — разбиение вершин данного графа на клики. Тот факт, что дополнение идеального графа $G$ также совершенно означает, что в $G$ Само по себе число независимости (размер его максимального независимого множества ) равно числу кликового покрытия (наименьшему количеству клик, необходимых для кликового покрытия). В более строгом смысле то же самое верно для каждого индуцированного подграфа графа дополнений. Это дает альтернативное и эквивалентное определение идеальных графов: это графы, для которых в каждом индуцированном подграфе число независимости равно числу кликового покрытия.

Сильная теорема о совершенных графах дает другой способ определения идеальных графов на основе их структуры, а не свойств.Он основан на существовании графов циклов и их дополнений внутри данного графа. Цикл нечетной длины, превышающий три, не является совершенным: его кликовое число равно двум, а хроматическое число равно трем. По теореме о совершенном графе дополнение к нечетному циклу длины больше трех также не является совершенным. Дополнением цикла длины 5 является другой цикл длины 5, но для больших нечетных длин дополнение не является циклом; это называется антициклом . Сильная теорема о совершенном графе утверждает, что это единственные запрещенные индуцированные подграфы для совершенных графов: граф совершенен тогда и только тогда, когда его индуцированные подграфы не содержат ни нечетного цикла, ни нечетного антицикла из пяти или более вершин. В этом контексте индуцированные циклы , которые не являются треугольниками, называются «дырками», а их дополнения называются «антидырками», поэтому сильную теорему о совершенном графе можно сформулировать более кратко: граф совершенен тогда и только тогда, когда он не имеет ни нечетных ни дыра, ни странная антидыра.

Эти результаты можно объединить в другую характеристику совершенных графов: это графы, для которых произведение кликового числа и числа независимости больше или равно числу вершин, и для которых то же самое верно для всех индуцированных подграфов. Поскольку утверждение этой характеристики остается инвариантным относительно дополнения графов, из него следует теорема об идеальном графе. Одно направление этой характеристики легко следует из исходного определения совершенства: число вершин в любом графе равно сумме размеров классов цветов в оптимальной раскраске и меньше или равно количеству цветов, умноженному на номер независимости. В идеальном графе количество цветов равно числу клик и в этом неравенстве может быть заменено числом клики. Другое направление можно доказать непосредственно, но это также следует из сильной теоремы о совершенном графе: если граф несовершенен, он содержит нечетный цикл или его дополнение, и в этих подграфах произведение кликового числа и числа независимости на единицу меньше числа вершин.

История

Теория совершенных графов возникла на основе результата Тибора Галлая 1958 года , который на современном языке можно интерпретировать как утверждение о том, что дополнение двудольного графа совершенно; этот результат также можно рассматривать как простой эквивалент теоремы Кенига , гораздо более раннего результата, касающегося паросочетаний и вершинных покрытий в двудольных графах. Первая формулировка концепции совершенных графов в более общем плане была в статье Клода Берже 1961 года на немецком языке: и первое использование фразы «идеальный граф», по-видимому, встречается в статье Берге 1963 года. В этих работах он объединил результат Галлаи с несколькими аналогичными результатами, определив совершенные графы, и выдвинул гипотезы как о теореме об идеальном графе, так и о сильной теореме о совершенном графе. При формулировке этих концепций Берге руководствовался концепцией шенноновской емкости графа , тем фактом, что для (ко)совершенных графов она равна числу независимости, а также поиском минимальных примеров графов, для которых это не так. случай. До тех пор, пока не была доказана сильная теорема о совершенных графах, описываемые ею графы (то есть графы без нечетных дырок и нечетных антидырок) назывались графами Бержа .

Теорема о совершенном графе была доказана Ласло Ловасом в 1972 году: который в том же году доказал более сильное неравенство между количеством вершин и произведением кликового числа на число независимости, не прибегая к сильной теореме о совершенном графе. В 1991 году Альфред Леман получил премию Фулкерсона , спонсируемую совместно Обществом математической оптимизации и Американским математическим обществом , за работу по обобщению теории совершенных графов на логические матрицы . Предполагаемая сильная теорема о совершенных графах на многие годы стала предметом исследований в области теории совершенных графов. до тех пор, пока его доказательство не было объявлено в 2002 году Марией Чудновской , Нилом Робертсоном , Полом Сеймуром и Робином Томасом . и опубликовано ими в 2006 году. Эта работа принесла своим авторам премию Фулкерсона 2009 года. Теорема об идеальном графе имеет краткое доказательство: но доказательство сильной теоремы о совершенном графе является длинным и техническим, основанным на глубокой структурной декомпозиции графов Бержа. Связанные методы декомпозиции также принесли плоды при изучении других классов графов, в частности графов без когтей . Симметричная характеристика совершенных графов в терминах произведения кликового числа и числа независимости была первоначально предложена Хайналом и доказана Ловасом.

Семейства графов

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

Двудольные графики и линейные графики

Двудольный граф (слева) и его линейный график (справа). Заштрихованные клики в линейном графе соответствуют вершинам лежащего в основе двудольного графа и имеют размер, равный степени соответствующей вершины.

В двудольных графах (хотя бы с одним ребром) хроматическое число и кликовое число равны двум. Их индуцированные подграфы остаются двудольными, поэтому двудольные графы совершенны. Другие важные семейства графов являются двудольными и, следовательно, также совершенными, включая, например, деревья и медианные графы . По теореме о совершенном графе максимальные независимые множества в двудольных графах имеют тот же размер, что и их минимальные кликовые покрытия. Максимальный независимый набор дополняет минимальное вершинное покрытие — набор вершин, касающийся всех ребер. Минимальное кликовое покрытие состоит из максимального совпадения (как можно большего количества непересекающихся ребер) вместе с одновершинными кликами для всех оставшихся вершин, а его размер равен количеству вершин минус количество совпадающих ребер. Следовательно, это равенство можно эквивалентно выразить как равенство между размером максимального паросочетания и минимальным покрытием вершин в двудольных графах - обычная формулировка теоремы Кенига .

Соответствие в любом графе $G$, — это то же самое, что независимый набор на линейном графике $L(G)$, граф, в котором есть вершина для каждого ребра в $G$ и ребро между двумя вершинами в $L(G)$ для каждой пары ребер в $G$ которые имеют общую конечную точку. Линейные графы имеют два вида клик: наборы ребер в $G$ с общим концом и треугольниками в $G$. В двудольных графах треугольников нет, поэтому кликовое покрытие в $L(G)$ соответствует вершинному покрытию в $G$. Следовательно, в линейных графах двудольных графов число независимости и число кликового покрытия равны. Индуцированные подграфы линейных графов двудольных графов являются линейными графами подграфов, поэтому линейные графы двудольных графов совершенны. Примеры включают ладейные графы , линейные графы полных двудольных графов . Каждый линейный граф двудольного графа является индуцированным подграфом ладейного графа.

Поскольку линейные графы двудольных графов совершенны, их кликовое число равно хроматическому числу. Число клики линейного графа двудольного графа — это максимальная степень любой вершины лежащего в основе двудольного графа. Хроматическое число линейного графа двудольного графа — это хроматический индекс лежащего в основе двудольного графа, минимальное количество цветов, необходимое для окраски ребер так, чтобы соприкасающиеся ребра имели разные цвета. Каждый цветовой класс образует сопоставление, а хроматический индекс — это минимальное количество сопоставлений, необходимое для покрытия всех ребер. Равенство максимальной степени и хроматического индекса в двудольных графах — еще одна теорема Денеша Кёнига . В произвольных простых графах они могут отличаться на единицу; это теорема Визинга .

Линейный идеальный график с черными двудольными двусвязными компонентами, синий $K_{4}$и красные треугольные книги

Базовый график $G$ идеального линейного графика $L(G)$ представляет собой идеальный линейный график . Это графы, двусвязные компоненты которых являются двудольными графами, полный граф $K_{4}$и треугольные книги — наборы треугольников, имеющих общее ребро. Эти компоненты совершенны, и их сочетание сохраняет совершенство, поэтому каждая линия идеального графика идеальна.

Двудольные графы, их дополнения и линейные графы двудольных графов и их дополнений образуют четыре основных класса совершенных графов, которые играют ключевую роль в доказательстве теоремы о сильном совершенном графе. Согласно структурной декомпозиции совершенных графов, используемой в рамках этого доказательства, каждый совершенный граф, который еще не принадлежит ни к одному из этих четырех классов, может быть разложен путем разделения его вершин на подмножества одним из четырех способов, называемых 2-соединением: дополнение 2-соединения, однородной пары или косого разбиения .

Графики сопоставимости

Диаграмма Хассе частично упорядоченного множества и ее график сравнимости

определяется Частично упорядоченный набор набором его элементов и отношением сравнения. $\leq$ рефлексивно элементов (для всех $x$, $x\leq x$), антисимметричный (если $x\leq y$ и $y\leq x$, затем $x=y$и транзитивный (если $x\leq y$ и $y\leq z$, затем $x\leq z$). Элементы $x$ и $y$ сравнимы , если $x\leq y$ или $y\leq x$, и несравнимо в остальном. Например, установите включение ( $\subseteq$) частично упорядочивает любое семейство множеств . Граф сравнимости частично упорядоченного множества имеет элементы множества в качестве вершин, а ребро соединяет любые два сравнимых элемента. Его дополнение называется графом несравнимости . Различные частичные заказы могут иметь один и тот же график сопоставимости; например, обращение всех сравнений меняет порядок, но не график.

Графы конечной сравнимости (и дополняющие их графы несравнимости) всегда совершенны. Клика в графе сравнимости происходит из подмножества элементов, которые все попарно сравнимы; такое подмножество называется цепью и оно линейно упорядочено по заданному частичному порядку. Независимый набор состоит из подмножества элементов, среди которых нет двух сопоставимых; такое подмножество называется антицепью . Например, на проиллюстрированном графике частичного порядка и сравнимости: $\{A,B,C\}$ является цепью в порядке и кликой в ​​графе, а $\{C,D\}$ является антицепью в порядке и независимым множеством в графе. Таким образом, раскраска графа сравнимости — это разбиение его элементов на антицепи, а кликовое покрытие — разбиение его элементов на цепи. Теорема Дилворта в теории частичных порядков утверждает, что для каждого конечного частичного порядка размер наибольшей антицепи равен минимальному количеству цепей, на которые можно разделить элементы. На языке графов это можно сформулировать так: каждый конечный граф сравнимости совершенен. Точно так же теорема Мирского утверждает, что для каждого конечного частичного порядка размер наибольшей цепи равен минимальному количеству антицепей, на которые можно разбить элементы, или что каждый конечный граф несравнимости совершенен. Эти две теоремы эквивалентны с точки зрения теоремы об идеальном графе, но теорему Мирского легче доказать напрямую, чем теорему Дилворта: если каждый элемент помечен размером наибольшей цепи, в которой он максимален, то подмножества с одинаковыми метками образуют разбиение. на антицепи, причем количество антицепей равно размеру самой большой цепи в целом. Любой двудольный граф является графом сравнимости. Таким образом, теорему Кенига можно рассматривать как частный случай теоремы Дилворта, связанный через теорию совершенных графов.

Граф перестановок перестановки (4,3,5,1,2) соединяет пары элементов, порядок которых меняется на противоположный в результате перестановки.

Граф перестановок определяется как перестановка полностью упорядоченной последовательности элементов (обычно целые числа из $1$ к $n$), которые образуют вершины графа. Ребра графа перестановок соединяют пары элементов, порядок которых меняется на обратный в результате данной перестановки. Это, естественно, графы несравнимости для частичного порядка, в котором $x\leq y$ в любое время $x$ происходит до $y$ как в данной последовательности, так и в ее перестановке. Дополнением графа перестановок является другой граф перестановок, обратный данной перестановке. Следовательно, графы перестановок не только являются графами несравнимости, но и являются графами сравнимости. Фактически графы перестановок — это именно те графы, которые одновременно являются графами сравнимости и несравнимости. Клика в графе перестановок — это подпоследовательность элементов, которые появляются в данной перестановке в порядке возрастания, а независимый набор — это подпоследовательность элементов, которые появляются в порядке убывания. В любом идеальном графе произведение кликового числа и числа независимости равно как минимум количеству вершин; частным случаем этого неравенства для графов перестановок является теорема Эрдеша – Секереша .

График интервалов и определяющие его интервалы

Графы интервалов — это графики несравнимости порядков интервалов , порядков, определяемых наборами интервалов на вещественной прямой с $x\leq y$ всякий раз, когда интервал $x$ находится полностью левее интервала $y$. В соответствующем графе интервалов имеется ребро из $x$ к $y$ всякий раз, когда эти два интервала имеют общую точку. Раскраску этих графиков можно использовать для моделирования проблем распределения ресурсов по задачам (например, классы по классам) с интервалами, описывающими запланированное время каждой задачи. И графы интервалов, и графы перестановок обобщаются графами трапеций . Системы интервалов, в которые никакие два не вложены, образуют более ограниченный класс графов — графы безразличия , графы несравнимости полупорядков . Они использовались для моделирования человеческих предпочтений в предположении, что, когда полезности предметов очень близки друг к другу, они будут несравнимы. Интервалы, в которых каждая пара является вложенной или непересекающейся, создают тривиально совершенные графики . графы сравнимости упорядоченных деревьев . В них число независимости равно числу максимальных клик .

Разделенные графы и случайные идеальные графы

Оптимальная раскраска разделенного графа , полученная путем присвоения каждой вершине максимальной клики (тяжелых вершин и ребер) отдельного цвета, а затем присвоения каждой оставшейся вершине того же цвета, что и вершине клики, с которой она не является смежной.

— Разбитый граф это граф, который можно разделить на клику и независимое множество. Его можно раскрасить, присвоив отдельный цвет каждой вершине максимальной клики, а затем раскрасив каждую оставшуюся вершину в цвет несмежной вершины клики. Следовательно, эти графы имеют одинаковые кликовые числа и хроматические числа и являются совершенными. Более широкий класс графов, униполярные графы, можно разделить на клику и кластерный граф — несвязное объединение клик. К ним относятся также двудольные графы, для которых кластерный граф представляет собой всего лишь одну клику. Униполярные графы и их дополнения вместе образуют класс обобщенных расщепляемых графов . Почти все совершенные графы являются обобщенными расщепленными графами в том смысле, что доля совершенных графов $n$-вершинные графы, которые являются обобщенными расщепляемыми графами, в пределе стремятся к единице как $n$ становится сколь угодно большим.

Другие предельные свойства почти всех совершенных графов можно определить, изучая обобщенные расщепляемые графы. Таким образом было показано, что почти все совершенные графы содержат гамильтонов цикл . Если $H$ — произвольный граф, предельная вероятность того, что $H$ возникает, когда индуцированный подграф большого случайного совершенного графа равен 0, 1/2 или 1 соответственно как $H$ не является обобщенным расщепленным графом, является униполярным или коуниполярным, но не тем и другим одновременно, или является одновременно униполярным и коуниполярным.

Инкрементные конструкции

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

• Хордальные графы — это графы, образованные конструкцией такого типа, в которой в момент добавления вершины ее соседи образуют клику. Хордальные графы также можно охарактеризовать как графы, не имеющие дыр (четных или нечетных). В качестве частных случаев они включают леса, интервальные графы, и максимальные внешнепланарные графы . Расщепляемые графы — это именно те графы, которые являются хордальными и имеют хордальное дополнение. , k -деревья занимающие центральное место в определении ширины дерева , представляют собой хордальные графы, образованные путем начала с ( k + 1) -вершинной клики и многократного добавления вершины так, чтобы она и ее соседи образовывали клику одинакового размера.

Три типа сложения вершин в дистанционно-наследственном графе

• Дистанционно -наследственные графы формируются, начиная с одновершинного графа, путем многократного добавления вершин первой степени («висячие вершины») или копий существующих вершин (с теми же соседями). Каждая вершина и ее копия могут быть смежными ( истинные двойники ) или несмежными ( ложные двойники ). В каждом связном индуцированном подграфе этих графов расстояния между вершинами такие же, как и во всем графе. Если используются только двойные операции, результатом является кограф . Кографы представляют собой графы сравнимости последовательно-параллельных частичных порядков. а также может быть образован другим процессом построения, сочетающим дополнение и непересекающееся объединение графов .
• Графы, которые одновременно являются хордальными и дистанционно-наследственными, называются графами Птолемея , поскольку их расстояния подчиняются неравенству Птолемея . Они имеют ограниченную форму дистанционно-наследственной последовательности построения, в которой ложный близнец может быть добавлен только тогда, когда его соседи образуют клику. В качестве частных случаев к ним относятся графы ветряных мельниц, состоящие из клик, соединенных в одной вершине, и блочные графы , в которых каждая компонента двусвязности является кликой.
• Пороговые графы формируются из пустого графа путем многократного добавления либо изолированной вершины (связанной ни с чем), либо универсальной вершины (связанной со всеми остальными вершинами). Это частные случаи расщепляемых графов и тривиально совершенных графов. Это именно те графы, которые одновременно тривиально совершенны и являются дополнением к тривиально совершенному графу; они также являются графами, которые одновременно являются кографами и расщепляемыми графами.

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

Сильное совершенство

Сильно совершенные графы — это графы, в которых в каждом индуцированном подграфе существует независимое множество, пересекающее все максимальные клики . В графах Мейнеля или очень сильно совершенных графах каждая вершина принадлежит такому независимому множеству. Графы Мейнеля также можно охарактеризовать как графы, в которых каждый нечетный цикл длины пять или более имеет как минимум две хорды.

Граф четности , который не является ни дистанционно-наследственным , ни двудольным.

Граф четности определяется тем свойством, что между любыми двумя вершинами все индуцированные пути имеют одинаковую четность: либо все они четные по длине, либо все они нечетные по длине. К ним относятся дистанционно-наследственные графы, в которых все индуцированные пути между двумя вершинами имеют одинаковую длину, и двудольные графы, для которых все пути (а не только индуцированные пути) между любыми двумя вершинами имеют одинаковую четность. Графы четности являются графами Мейниэля и, следовательно, совершенны: если бы длинный нечетный цикл имел только одну хорду, две части цикла между конечными точками хорды были бы индуцированными путями разной четности. Призма над любым графом четности (ее декартово произведение с одним ребром) является еще одним графом четности, а графы четности — единственные графы, призмы которых совершенны.

Матрицы, многогранники

Совершенные графы тесно связаны с теорией линейного программирования и целочисленного программирования . И линейные, и целочисленные программы выражаются в канонической форме как поиск вектора. $x$ которая максимизирует линейную целевую функцию $c\cdot x$, с учетом линейных ограничений $x\geq 0$ и $Ax\leq b$. Здесь, $A$ задается в виде матрицы и $b$ и $c$ задаются в виде двух векторов. Хотя линейные и целочисленные программы задаются одинаково, они отличаются тем, что в линейной программе вектор решения $x$ в качестве коэффициентов допускается использовать произвольные действительные числа , тогда как в целочисленной программе эти неизвестные коэффициенты должны быть целыми числами. Это имеет очень большое значение в вычислительной сложности этих задач: линейное программирование может быть решено за полиномиальное время , но целочисленное программирование является NP-сложным .

Когда одинаковые заданные значения $A$, $b$, и $c$ используются для определения как линейной программы, так и целочисленной программы, они обычно имеют разные оптимальные решения. Линейная программа называется интегральной линейной программой, если оптимальное решение целочисленной программы является оптимальным и для линейной программы. (В противном случае соотношение между двумя значениями решения называется разрывом целочисленности и важно при анализе алгоритмов аппроксимации для целочисленной программы.) Идеальные графики могут использоваться для характеристики матриц (0, 1). $A$ (то есть матрицы, в которых все коэффициенты равны 0 или 1) со следующим свойством: если $b$ — вектор «все единицы» , тогда для всех вариантов выбора $c$ полученная линейная программа является целой.

Как показал Вацлав Хватал , каждая матрица $A$ с этим свойством является (с точностью до удаления нерелевантных «доминируемых» строк) максимальной матрицей клики и инцидентности вершин идеального графа. Эта матрица имеет столбец для каждой вершины графа и строку для каждой максимальной клики с коэффициентом, равным единице в столбцах вершин, принадлежащих клике, и нулю в остальных столбцах. Целочисленные линейные программы, закодированные этой матрицей, ищут независимый набор максимального веса данного графа с весами, заданными вектором $c$.

Для матрицы $A$ определенные таким образом из идеального графа, векторы $x$ удовлетворяющее системе неравенств $x\geq 0$, $Ax\leq 1$ образуют целый многогранник . Это выпуклая оболочка индикаторных векторов независимых множеств в графе с гранями , соответствующими максимальным кликам в графе. Совершенные графы — единственные графы, у которых два заданных таким образом многогранника из независимых множеств и из максимальных клик совпадают.

Алгоритмы

Во всех идеальных графах задача раскраски графа , проблема максимальной клики и проблема максимального независимого множества могут быть решены за полиномиальное время . Алгоритм для общего случая использует число Ловаса этих графов. Число Ловаса любого графа можно определить, пометив его вершины единичными векторами большой размерности , так, чтобы каждые две несмежные вершины имели перпендикулярные метки и чтобы все векторы лежали в конусе с как можно меньшим углом раскрытия. . Тогда число Ловаса равно $1/\cos ^{2}\theta$, где $\theta$ — половина угла этого конуса. Несмотря на это сложное определение, точное численное значение числа Ловаса можно вычислить с помощью полуопределенного программирования , и для любого графа число Ловаса находится между хроматическим числом и числом клики. Поскольку эти два числа равны друг другу в идеальных графах, они также равны числу Ловаса. Таким образом, их можно вычислить, достаточно точно аппроксимировав число Ловаса и округлив результат до ближайшего целого числа.

Метод решения полуопределенных программ, используемый в этом алгоритме, основан на методе эллипсоидов линейного программирования . Это приводит к алгоритму с полиномиальным временем для вычисления хроматического числа и кликового числа в идеальных графах. Однако решение этих задач с использованием числа Ловаса и метода эллипсоидов сложно и имеет высокий полиномиальный показатель. Для многих частных случаев известны более эффективные комбинаторные алгоритмы.

Этот метод также можно обобщить, чтобы найти максимальный вес клики во взвешенном графе вместо номера клики. С помощью этих методов также можно найти клику максимального или максимального веса и оптимальную раскраску графа, а максимальное независимое множество можно найти, применив тот же подход к дополнению графа. Например, максимальную клику можно найти по следующему алгоритму:

• Перебираем вершины графа. Для каждой вершины $v$, выполните следующие действия:
  • Предварительно удалить $v$ из графика.
  • Используйте полуопределенное программирование, чтобы определить кликовый номер результирующего индуцированного подграфа.
  • Если этот номер клики такой же, как и для всего графа, навсегда удалите $v$; в противном случае восстановить $v$ к графику.
• Верните подграф, который остался после всех постоянных удалений.

Алгоритм поиска оптимальной раскраски более сложен и зависит от теории двойственности линейных программ, использующей этот алгоритм поиска клик в качестве оракула разделения .

Помимо решения этих проблем, еще одной важной вычислительной проблемой, касающейся совершенных графов, является их распознавание, проблема проверки того, является ли данный граф совершенным. В течение многих лет сложность распознавания графов Бержа и совершенных графов рассматривалась отдельно (поскольку их эквивалентность еще не была известна), и оба оставались открытыми. Было известно, что они оба были в совместном НП ; для графов Бержа это следует из определения: а для совершенных графов это следует из характеристики с использованием произведения кликового числа и числа независимости. После того, как была доказана сильная теорема о совершенном графе, Чудновский, Корнюжоль, Лю, Сеймур и Вушкович открыли алгоритм с полиномиальным временем для проверки существования нечетных дыр или антидыр. Согласно сильной теореме о совершенном графе, это можно использовать для проверки того, является ли данный граф совершенным, за полиномиальное время.

Связанные понятия

Обобщая идеальные графы, класс графов называется χ-ограниченным, если хроматическое число графов в классе может быть ограничено функцией их кликового числа. Идеальные графы — это именно те графы, для которых эта функция является тождественной как для самого графа, так и для всех его индуцированных подграфов.

Равенство кликового числа и хроматического числа в совершенных графах побудило определение других классов графов, в которых другие инварианты графа считаются равными друг другу. Например, совершенные графы доминирования определяются как графы, в которых в каждом индуцированном подграфе наименьшее доминирующее множество (набор вершин, смежных со всеми остальными вершинами) равно размеру наименьшего независимого множества, которое является доминирующим множеством. К ним относятся, например, графы без когтей .

Внешние ссылки

• Теорема о сильном совершенном графе Вацлава Хватала .
• Открытые задачи на совершенных графах , поддерживаемые Американским институтом математики .
• Совершенные проблемы , поддерживаемые Вацлавом Хваталом.
• Информационная система по включению классов графов : идеальный граф