Совершенные графы: связь раскраски и клик

Введение

Граф с тесной связью между раскраской и кликой

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

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

Клика в ненаправленном графе — это подмножество его вершин, все из которых смежны друг с другом, например, подмножества вершин, соединенных выделенными ребрами на иллюстрации. Число клики — это число вершин в наибольшей клике: два в показанном семивершинном цикле и три в другом изображенном графе. Раскраска графа присваивает цвет каждой вершине так, чтобы любые две смежные вершины имели разные цвета, что также показано на иллюстрации. Хроматическое число графа — это минимальное число цветов в любой раскраске. Приведенные раскраски оптимальны, поэтому хроматическое число равно трем для 7-цикла и четырем для другого показанного графа. Вершины любой клики должны иметь разные цвета, поэтому хроматическое число всегда больше или равно числу клики. Для некоторых графов они равны, для других, таких как показанные, — нет. Совершенные графы определяются как графы, для которых эти два числа равны не только в самом графе, но и в каждом индуцированном подграфе, полученном удалением некоторых его вершин. Теорема о совершенных графах утверждает, что дополнение совершенного графа само по себе является совершенным. Дополнение графа имеет ребро между двумя вершинами тогда и только тогда, когда данный граф не имеет такого ребра. Клика в дополнении графа соответствует независимому множеству в данном графе. Раскраска дополнения графа соответствует покрытию кликами, то есть разбиению вершин данного графа на клики. Тот факт, что дополнение совершенного графа также является совершенным, означает, что число независимости (размер его максимального независимого множества) равно числу покрытия кликами (минимальному числу клик, необходимых для покрытия кликами) в самом графе. Более того, то же самое верно для каждого индуцированного подграфа дополнения графа. Это дает альтернативное и эквивалентное определение совершенных графов: это графы, для которых в каждом индуцированном подграфе число независимости равно числу покрытия кликами. Теорема о сильных совершенных графах дает другой способ определения совершенных графов, исходя из их структуры, а не из их свойств. Она основана на существовании циклов и их дополнений в заданном графе. Цикл нечетной длины, большей трех, не является совершенным: его число клики равно двум, а хроматическое число — трем. Согласно теореме о совершенных графах, дополнение нечетного цикла длиной более трех также не является совершенным. Дополнение цикла длины 5 — это другой цикл длины 5, но для больших нечетных длин дополнение не является циклом; оно называется антициклом. Теорема о сильных совершенных графах утверждает, что это единственные запрещенные индуцированные подграфы для совершенных графов: граф совершенен тогда и только тогда, когда его индуцированные подграфы не содержат ни нечетного цикла, ни нечетного антицикла, состоящих из пяти или более вершин. В этом контексте индуцированные циклы, которые не являются треугольниками, называются «дырами», а их дополнения — «антидырами», поэтому теорему о сильных совершенных графах можно сформулировать более кратко: граф совершенен тогда и только тогда, когда он не содержит ни нечетной дыры, ни нечетной антидыры. Эти результаты можно объединить в другую характеристику совершенных графов: это графы, для которых произведение числа клики и числа независимости больше или равно числу вершин, и для которых то же самое верно для всех индуцированных подграфов. Поскольку утверждение этой характеристики инвариантно относительно дополнения графов, оно подразумевает теорему о совершенных графах. Одно из направлений этой характеристики легко следует из исходного определения совершенства: число вершин в любом графе равно сумме размеров цветовых классов в оптимальной раскраске и не превышает числа цветов, умноженного на число независимости. В совершенном графе число цветов равно числу клики и может быть заменено числом клики в этом неравенстве. Другое направление можно доказать напрямую, но оно также следует из теоремы о сильных совершенных графах: если граф не совершенен, он содержит нечетный цикл или его дополнение, и в этих подграфах произведение числа клики и числа независимости на единицу меньше числа вершин.

История

Теория совершенных графов развилась из результата Тибора Галлая 1958 года, который на современном языке можно интерпретировать как утверждение, что дополнение двудольного графа является совершенным; этот результат также можно рассматривать как простой эквивалент теоремы Кёнига, гораздо более раннего результата, связывающего паросочетания и вершинные покрытия в двудольных графах. Первая формулировка понятия совершенных графов в более общем виде была представлена в статье Клода Берге 1961 года, написанной на немецком языке, а первое использование фразы «совершенный граф», по-видимому, встречается в статье Берге 1963 года. В этих работах он объединил результат Галлая с несколькими аналогичными результатами, определив совершенные графы, и выдвинул гипотезы как о теореме о совершенных графах, так и о теореме о сильных совершенных графах. При формулировании этих понятий Берге был мотивирован понятием ёмкости Шеннона графа, тем фактом, что для (ко)совершенных графов она равна числу независимости, и поиском минимальных примеров графов, для которых это не выполняется. До тех пор, пока теорема о сильных совершенных графах не была доказана, графы, описываемые ею (то есть графы без нечётных циклов и нечётных антициклов), назывались графами Берге. Теорему о совершенном графе доказал Ласло Ловаш в 1972 году, который в том же году доказал более сильное неравенство между числом вершин и произведением числа клики и числа независимости, без использования теоремы о сильных совершенных графах. В 1991 году Альфред Леман получил премию Фулкерсона, спонсируемую совместно Обществом математической оптимизации и Американским математическим обществом, за его работу по обобщению теории совершенных графов на логические матрицы. Предполагаемая теорема о сильных совершенных графах стала объектом исследований в теории совершенных графов на протяжении многих лет, пока её доказательство не было объявлено в 2002 году Марией Чудновски, Нилом Робертсоном, Полом Сеймуром и Робином Томасом и опубликовано ими в 2006 году. Эта работа принесла авторам премию Фулкерсона 2009 года. Теорема о совершенном графе имеет короткое доказательство, но доказательство теоремы о сильных совершенных графах длинное и технически сложное, основанное на глубоком структурном разложении графов Берге. Схожие методы разложения также оказались плодотворными при изучении других классов графов, в частности, графов без когтей. Симметричная характеристика совершенных графов с точки зрения произведения числа клики и числа независимости была первоначально предложена Хайналем и доказана Ловашем.

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

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

Бипартитные и линейные графики

В двухдольных графах (с хотя бы одним ребром) хроматическое число и число клики равны 2. Их индуцированные подграфы остаются двудольными, поэтому двудольные графы совершенны. Другие важные семейства графов являются двудольными и, следовательно, также совершенными, включая, например, деревья и медианные графы. Согласно теореме о совершенных графах, максимальные независимые множества в двухдольных графах имеют тот же размер, что и их минимальные покрытия кликами. Максимальное независимое множество дополняет минимальное вершинное покрытие, множество вершин, которые инцидентны всем ребрам. Минимальное покрытие кликами состоит из максимального паросочетания (как можно больше непересекающихся ребер) вместе с кликами из одной вершины для всех оставшихся вершин, и его размер равен числу вершин минус число ребер паросочетания. Поэтому это равенство может быть эквивалентно выражено как равенство между размером максимального паросочетания и минимального вершинного покрытия в двухдольных графах, обычной формулировке теоремы Кёнига. Паросочетание в любом графе – это то же самое, что независимое множество в линейном графе, графе, который имеет вершину для каждого ребра в исходном графе и ребро между двумя вершинами в линейном графе для каждой пары ребер в исходном графе, имеющих общую конечную точку. Линейные графы имеют два вида клик: множества ребер с общей конечной точкой и треугольники. В двухдольных графах нет треугольников, поэтому покрытие кликами в линейном графе соответствует вершинному покрытию в исходном графе. Поэтому в линейных графах двухдольных графов число независимости и число покрытия кликами равны. Индуцированные подграфы линейных графов двухдольных графов являются линейными графами подграфов, поэтому линейные графы двухдольных графов совершенны. Примеры включают графы ладей, линейные графы полных двухдольных графов. Каждый линейный граф двудольного графа является индуцированным подграфом графа ладей. Поскольку линейные графы двухдольных графов совершенны, их число клики равно их хроматическому числу. Число клики линейного графа двудольного графа – это максимальная степень любой вершины базового двудольного графа. Хроматическое число линейного графа двудольного графа – это хроматический индекс базового двудольного графа, минимальное число цветов, необходимое для раскраски ребер так, чтобы смежные ребра имели разные цвета. Каждый цветовой класс образует паросочетание, а хроматический индекс – это минимальное число паросочетаний, необходимое для покрытия всех ребер. Равенство максимальной степени и хроматического индекса в двухдольных графах – еще одна теорема Денеша Кёнига. В произвольных простых графах они могут отличаться на единицу; это теорема Визинга. Базовый граф совершенного линейного графа – это линейно совершенный граф. Это графы, чьи двусвязные компоненты являются двудольными графами, полным графом и треугольными книгами, множествами треугольников, имеющих общее ребро. Эти компоненты совершенны, и их комбинация сохраняет совершенство, поэтому каждый линейно совершенный граф совершенен. Двудольные графы, их дополнения, и линейные графы двудольных графов и их дополнений образуют четыре основных класса совершенных графов, которые играют ключевую роль в доказательстве теоремы о сильных совершенных графах. Согласно структурному разложению совершенных графов, используемому в качестве части этого доказательства, каждый совершенный граф, который еще не входит в один из этих четырех классов, может быть разложен путем разбиения его вершин на подмножества одним из четырех способов, называемых 2-соединением, дополнением 2-соединения, однородной парой или косым разбиением.

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

Частично упорядоченное множество определяется своим множеством элементов и отношением сравнения, которое является рефлексивным (для всех элементов , ), антисимметричным (если и , то , и транзитивным (если и , то ). Элементы и сопоставимы, если или , и несравнимы в противном случае. Например, включение множества частично упорядочивает любое семейство множеств. Граф сопоставимости частично упорядоченного множества имеет элементы множества в качестве вершин, с ребром, соединяющим любые два сопоставимых элемента. Его дополнение называется графом несравненности. Различные частичные порядки могут иметь один и тот же граф сопоставимости; например, изменение порядка всех сравнений меняет порядок, но не граф. Конечные графы сопоставимости (и их дополнительные графы несравненности) всегда совершенны. Клика в графе сопоставимости происходит из подмножества элементов, которые все попарно сопоставимы; такое подмножество называется цепью и линейно упорядочено заданным частичным порядком. Независимое множество происходит из подмножества элементов, ни два из которых не сопоставимы; такое подмножество называется антицепью. Например, в иллюстрированном частичном порядке и графе сопоставимости, является цепью в порядке и кликой в графе, в то время как является антицепью в порядке и независимым множеством в графе. Таким образом, раскраска графа сопоставимости — это разбиение его элементов на антицепи, а покрытие кликами — разбиение его элементов на цепи. Теорема Дилворта в теории частичных порядков утверждает, что для каждого конечного частичного порядка размер наибольшей антицепи равен минимальному числу цепей, на которые можно разбить элементы. На языке графов это можно выразить так: каждый конечный граф сопоставимости совершенен. Аналогично, теорема Мирского утверждает, что для каждого конечного частичного порядка размер наибольшей цепи равен минимальному числу антицепей, на которые можно разбить элементы, или что каждый конечный граф несравненности совершенен. Эти две теоремы эквивалентны через теорему о совершенном графе, но теорему Мирского легче доказать напрямую, чем теорему Дилворта: если каждый элемент помечен размером наибольшей цепи, в которой он является максимальным, то подмножества с равными метками образуют разбиение на антицепи, при этом число антицепей равно размеру наибольшей цепи в целом. Каждый двудольный граф — это граф сопоставимости. Таким образом, теорему Кёнига можно рассматривать как частный случай теоремы Дилворта, связанный с помощью теории совершенных графов. Граф перестановок определяется перестановкой на полностью упорядоченной последовательности элементов (обычно целых чисел от до ), которые образуют вершины графа. Рёбра графа перестановок соединяют пары элементов, порядок которых обращён заданной перестановкой. Это естественным образом графы несравненности для частичного порядка, в котором всякий раз, когда встречается раньше как в данной последовательности, так и в её перестановке. Дополнение графа перестановок — это другой граф перестановок, для обратной заданной перестановки. Поэтому, помимо того, что они являются графами несравненности, графы перестановок являются графами сопоставимости. На самом деле, графы перестановок — это точно графы, которые являются и графами сопоставимости, и графами несравненности. Клика в графе перестановок — это подпоследовательность элементов, которые появляются в возрастающем порядке в заданной перестановке, а независимое множество — это подпоследовательность элементов, которые появляются в убывающем порядке. В любом совершенном графе произведение числа клики и числа независимости не меньше числа вершин; частным случаем этого неравенства для графов перестановок является теорема Эрдеша — Секереша. Интервальные графы — это графы несравненности интервальных порядков, порядки, определяемые наборами интервалов на вещественной прямой, причем, когда интервал полностью левее интервала, в соответствующем интервальном графе есть ребро от до, когда два интервала имеют общую точку. Раскраска этих графов может быть использована для моделирования задач распределения ресурсов на задачи (например, аудиторий для классов) с интервалами, описывающими запланированное время каждой задачи. И интервальные графы, и графы перестановок обобщаются трапецеидальными графами. Системы интервалов, в которых ни один не вложен в другой, порождают более ограниченный класс графов — графы безразличия, графы несравненности полупорядков. Они использовались для моделирования предпочтений человека при условии, что, когда у элементов утилиты очень близки друг к другу, они будут несравнимы. Интервалы, где каждая пара вложена или не пересекается, порождают тривиально совершенные графы, графы сопоставимости упорядоченных деревьев. В них число независимости равно числу максимальных клик.

Разделенные графики и случайные совершенные графики

Разделенный граф — это граф, который можно разбить на клику и независимое множество. Его можно раскрасить, присвоив отдельный цвет каждой вершине максимальной клики, а затем раскрасив каждую оставшуюся вершину тем же цветом, что и не смежная вершина клики. Следовательно, эти графы имеют одинаковые числа клик и хроматические числа и являются совершенными. Более широкий класс графов, однополярные графы, можно разбить на клику и кластерный граф — непересекающееся объединение клик. К ним также относятся двудольные графы, для которых кластерный граф представляет собой всего одну клику. Однополярные графы и их дополнения вместе образуют класс обобщенных разделенных графов. Почти все совершенные графы являются обобщенными разделенными графами, в том смысле, что доля совершенных вершинных графов, являющихся обобщенными разделенными графами, стремится к единице в пределе, когда n становится произвольно большим. Другие предельные свойства почти всех совершенных графов можно определить, изучая обобщенные разделенные графы. Таким образом, было показано, что почти все совершенные графы содержат гамильтонов цикл. Если G — произвольный граф, то предельная вероятность того, что G возникает как индуцированный подграф большого случайного совершенного графа, равна 0, 1/2 или 1, в зависимости от того, является ли G не обобщенным разделенным графом, однополярным или кооднополярным, но не обоими, или одновременно однополярным и кооднополярным.

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

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

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

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

Матрицы, полиэдры и целочисленное программирование

Идеальные графы тесно связаны с теорией линейного программирования и целочисленного программирования. Как линейные программы, так и целочисленные программы выражаются в канонической форме как поиск вектора, максимизирующего линейную целевую функцию , при линейных ограничениях и . Здесь задана как матрица, а и заданы как два вектора. Хотя линейные программы и целочисленные программы определяются одинаково, они различаются тем, что в линейной программе вектор решения может иметь произвольные действительные числа в качестве коэффициентов, в то время как в целочисленной программе эти неизвестные коэффициенты должны быть целыми числами. Это существенно влияет на вычислительную сложность этих задач: линейное программирование может быть решено за полиномиальное время, а целочисленное программирование является NP-трудным. Когда одни и те же значения , , и используются для определения как линейной, так и целочисленной программы, они обычно имеют разные оптимальные решения. Линейная программа называется интегральной линейной программой, если оптимальное решение целочисленной программы также является оптимальным для линейной программы. (В противном случае отношение между двумя значениями решения называется интегральным разрывом и важно при анализе алгоритмов аппроксимации для целочисленной программы.) Совершенные графы могут быть использованы для характеризации матриц (0, 1) (то есть матриц, где все коэффициенты равны 0 или 1) со следующим свойством: если – вектор, состоящий из одних единиц, то для всех выборов полученная линейная программа является интегральной. Как доказал Вацлав Хваталь, каждая матрица с этим свойством является (с учетом удаления несущественных "доминирующих" строк) матрицей максимальной клики против инцидентности вершин совершенного графа. Эта матрица имеет столбец для каждой вершины графа и строку для каждой максимальной клики, с коэффициентом, равным единице в столбцах вершин, принадлежащих клике, и нулю в остальных столбцах. Интегральные линейные программы, закодированные этой матрицей, ищут максимальное взвешенное независимое множество данного графа с весами, заданными вектором . Для матрицы, определенной таким образом из совершенного графа, векторы, удовлетворяющие системе неравенств, образуют интегральный политоп. Это выпуклая оболочка индикаторных векторов независимых множеств в графе, с гранями, соответствующими максимальным кликам в графе. Идеальные графы – единственные графы, для которых два политопа, определенных таким образом из независимых множеств и из максимальных клик, совпадают.

Алгоритмы

Во всех совершенных графах задача раскраски графа, задача о максимальной клике и задача о максимальном независимом множестве могут быть решены за полиномиальное время. Алгоритм для общего случая включает число Ловаса этих графов. Число Ловаса любого графа можно определить, обозначив его вершины высокоразмерными единичными векторами так, чтобы любые две несмежные вершины имели перпендикулярные обозначения, и чтобы все векторы лежали в конусе с наименьшим возможным углом раскрытия. Тогда число Ловаса равно , где – половина угла раскрытия этого конуса. Несмотря на это сложное определение, точное численное значение числа Ловаса можно вычислить с помощью полудефинитного программирования, и для любого графа число Ловаса заключено между хроматическим числом и числом клики. Поскольку эти два числа равны друг другу в совершенных графах, они также равны числу Ловаса. Таким образом, их можно вычислить, достаточно точно аппроксимировав число Ловаса и округлив результат до ближайшего целого числа. Метод решения полудефинитных программ, используемый этим алгоритмом, основан на эллипсоидном методе для линейного программирования. Это приводит к алгоритму, работающему за полиномиальное время, для вычисления хроматического числа и числа клики в совершенных графах. Однако решение этих задач с использованием числа Ловаса и эллипсоидного метода сложно и имеет высокую степень полинома. Для многих частных случаев известны более эффективные комбинаторные алгоритмы. Этот метод также можно обобщить для нахождения максимального веса клики в взвешенном графе вместо числа клики. Саму максимальную или максимальную весовую клику, а также оптимальную раскраску графа можно найти этими методами, а максимальное независимое множество можно найти, применив тот же подход к дополнительному графу. Например, максимальную клику можно найти следующим алгоритмом:
Перебирайте вершины графа. Для каждой вершины выполняйте следующие действия:
Временно удалите из графа. Используйте полудефинитное программирование для определения числа клики полученного индуцированного подграфа. Если это число клики совпадает с числом клики для всего графа, удалите вершину безвозвратно; в противном случае, восстановите вершину в графе. Верните подграф, который остался после всех безвозвратных удалений. Алгоритм поиска оптимальной раскраски более сложен и основан на теории двойственности линейных программ, используя этот алгоритм поиска клики в качестве оракула для разделения. Помимо решения этих задач, важной вычислительной задачей, связанной с совершенными графами, является их распознавание, то есть проверка, является ли данный граф совершенным. В течение многих лет сложность распознавания графов Берже и совершенных графов рассматривалась отдельно (поскольку их эквивалентность еще не была известна), и обе оставались открытыми. Известно, что обе задачи принадлежат классу co NP; для графов Берже это следует из определения, а для совершенных графов – из характеризации с использованием произведения числа клики и числа независимости. После доказательства теоремы о сильной совершенности графов Чудновский, Корнюэйлс, Лю, Сеймур и Вушкович обнаружили алгоритм, работающий за полиномиальное время, для проверки существования нечетных дыр или антидыр. По теореме о сильной совершенности графов, это можно использовать для проверки, является ли данный граф совершенным, за полиномиальное время.

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

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