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

Graph with tight clique-coloring relation

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

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

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

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

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

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

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

Два дополнительных совершенных графа

Теорема о совершенном графе утверждает, что дополнительный граф совершенного графа сам по себе является совершенным. Дополнительный граф имеет ребро между двумя вершинами тогда и только тогда, когда данный граф не имеет. Клика в дополнительном графе соответствует независимому множеству в данном. Раскраска дополнительного графа соответствует покрытию кликами , разбиению вершин данного графа на клики. Тот факт, что дополнение совершенного графа также является совершенным, подразумевает, что само по себе число независимости (размер его максимального независимого множества ) равно числу покрытия кликами (наименьшему числу клик, необходимых для покрытия кликами). Более того, то же самое верно в каждом индуцированном подграфе дополнительного графа. Это дает альтернативное и эквивалентное определение совершенных графов: это графы, для которых в каждом индуцированном подграфе число независимости равно числу покрытия кликами. ^{[2] [3]} ${\displaystyle G}$ ${\displaystyle G}$

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

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

История

Теория совершенных графов развилась из результата Тибора Галлаи 1958 года , который на современном языке можно интерпретировать как утверждение, что дополнение двудольного графа является совершенным; ^[8] этот результат также можно рассматривать как простой эквивалент теоремы Кёнига , гораздо более раннего результата, связывающего паросочетания и покрытия вершин в двудольных графах. Первая формулировка концепции совершенных графов в более общем виде была в статье Клода Берже 1961 года на немецком языке ^[9] , а первое использование фразы «совершенный граф», по-видимому, относится к статье Берже 1963 года. ^[10] В этих работах он объединил результат Галлаи с несколькими похожими результатами, определив совершенные графы, и выдвинул гипотезы как о совершенном графе, так и о сильной теореме о совершенном графе. Формулируя эти концепции, Берже руководствовался концепцией емкости Шеннона графа , тем фактом, что для (ко)совершенных графов она равна числу независимости, и поиском минимальных примеров графов, для которых это не так. ^[11] Пока не была доказана сильная теорема о совершенном графе, графы, описываемые ею (то есть графы без нечетных дыр и без нечетных антидыр), назывались графами Берже . ^[12]

Теорема о совершенном графе была доказана Ласло Ловасом в 1972 году ^[2], который в том же году доказал более сильное неравенство между числом вершин и произведением числа клик и числа независимости, без использования сильной теоремы о совершенном графе. ^[5] В 1991 году Альфред Леман выиграл премию Фулкерсона , спонсируемую совместно Обществом математической оптимизации и Американским математическим обществом , за свою работу по обобщению теории совершенных графов на логические матрицы . ^[13] Предполагаемая сильная теорема о совершенном графе стала центром исследований в области теории совершенных графов на многие годы ^[12] , пока ее доказательство не было объявлено в 2002 году Марией Чудновской , Нилом Робертсоном , Полом Сеймуром и Робином Томасом ^[14] и опубликовано ими в 2006 году . ^[4] Эта работа принесла ее авторам премию Фулкерсона 2009 года. ^[15] Теорема о совершенном графе имеет короткое доказательство, ^{[5] [6]} но доказательство сильной теоремы о совершенном графе длинное и техническое, основанное на глубокой структурной декомпозиции графов Берже. Связанные методы декомпозиции также принесли плоды в изучении других классов графов, и в частности для графов без клешней . ^[16] Симметричная характеристика совершенных графов в терминах произведения числа клик и числа независимости была первоначально предложена Хайналом и доказана Ловасом. ^[5]

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

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

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

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

В двудольных графах (по крайней мере с одним ребром) хроматическое число и число клики оба равны двум. Их индуцированные подграфы остаются двудольными, поэтому двудольные графы являются совершенными. ^[12] Другие важные семейства графов являются двудольными, и, следовательно, также совершенными, включая, например, деревья и медианные графы . ^[17] По теореме о совершенном графе максимальные независимые множества в двудольных графах имеют тот же размер, что и их минимальные покрытия кликами. Максимальное независимое множество является дополнительным к минимальному покрытию вершин , набору вершин, который касается всех ребер. Минимальное покрытие кликами состоит из максимального паросочетания (как можно большего числа непересекающихся ребер) вместе с кликами из одной вершины для всех оставшихся вершин, и его размер равен числу вершин за вычетом числа совпадающих ребер. Следовательно, это равенство можно эквивалентно выразить как равенство между размером максимального паросочетания и минимальным покрытием вершин в двудольных графах, обычная формулировка теоремы Кёнига . ^{[18] [19]}

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

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

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

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

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

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

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

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

Конечные графы сравнимости (и их дополнительные графы несравнимости) всегда совершенны. ^[23] Клика в графе сравнимости происходит из подмножества элементов, которые все попарно сравнимы; такое подмножество называется цепью , и оно линейно упорядочено заданным частичным порядком. Независимое множество происходит из подмножества элементов, никакие два из которых не сравнимы; такое подмножество называется антицепью . Например, в проиллюстрированном графе частичного порядка и сравнимости является цепью в порядке и кликой в ​​графе, в то время как является антицепью в порядке и независимым множеством в графе. Таким образом, раскраска графа сравнимости является разбиением его элементов на антицепи, а покрытие кликой является разбиением его элементов на цепи. Теорема Дилворта в теории частичных порядков утверждает, что для каждого конечного частичного порядка размер наибольшей антицепи равен минимальному числу цепей, на которые могут быть разделены элементы. На языке графов это можно сформулировать так: каждый конечный граф сравнимости является совершенным. Аналогично теорема Мирского утверждает, что для каждого конечного частичного порядка размер наибольшей цепи равен минимальному числу антицепей, на которые можно разбить элементы, или что каждый конечный граф несравнимости является совершенным. Эти две теоремы эквивалентны посредством теоремы о совершенном графе, но теорему Мирского легче доказать напрямую, чем теорему Дилворта: если каждый элемент помечен размером наибольшей цепи, в которой он максимален, то подмножества с одинаковыми метками образуют разбиение на антицепи, причем число антицепей равно размеру наибольшей цепи в целом. ^[24] Каждый двудольный граф является графом сравнимости. Таким образом, теорему Кёнига можно рассматривать как частный случай теоремы Дилворта, связанный посредством теории совершенных графов. ^[25] ${\displaystyle \{A,B,C\}}$ ${\displaystyle \{C,D\}}$

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

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

Интервальный график и интервалы, его определяющие

Интервальные графы являются графами несравнимости интервальных порядков , упорядочений, определяемых наборами интервалов на действительной прямой с всякий раз, когда интервал находится полностью слева от интервала . В соответствующем интервальном графе есть ребро от до всякий раз, когда два интервала имеют общую точку. Раскрашивание этих графов может использоваться для моделирования проблем назначения ресурсов задачам (например, классных комнат классам) с интервалами, описывающими запланированное время каждой задачи. ^[27] Как интервальные графы, так и графы перестановок обобщаются трапециевидными графами . ^[28] Системы интервалов, в которых нет двух вложенных, производят более узкий класс графов, графы безразличия , графы несравнимости полупорядков . Они использовались для моделирования человеческих предпочтений в предположении, что когда элементы имеют полезности, которые очень близки друг к другу, они будут несравнимы. ^[29] Интервалы, где каждая пара вложена или не пересекается, производят тривиально совершенные графы , ^[30] графы сравнимости упорядоченных деревьев . В них число независимости равно числу максимальных клик . ^[31] ${\displaystyle x\leq y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как доказал Вацлав Хватал , каждая матрица с этим свойством является (с точностью до удаления нерелевантных "доминируемых" строк) максимальной матрицей инцидентности клики против вершины совершенного графа. Эта матрица имеет столбец для каждой вершины графа и строку для каждой максимальной клики с коэффициентом, равным единице в столбцах вершин, принадлежащих клике, и нулю в остальных столбцах. Интегральные линейные программы, закодированные этой матрицей, ищут независимое множество максимального веса данного графа с весами, заданными вектором . ^{[1] [53]} ${\displaystyle A}$ ${\displaystyle c}$

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

Алгоритмы

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

Метод решения для полуопределенных программ, используемый этим алгоритмом, основан на методе эллипсоида для линейного программирования . Он приводит к полиномиальному алгоритму для вычисления хроматического числа и числа клик в совершенных графах. Однако решение этих задач с использованием числа Ловаса и метода эллипсоида является сложным и имеет высокую полиномиальную экспоненту. ^{[54] [55]} Для многих особых случаев известны более эффективные комбинаторные алгоритмы. ^[56]

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

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

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

Помимо решения этих проблем, еще одной важной вычислительной проблемой, касающейся совершенных графов, является их распознавание, проблема проверки того, является ли данный граф совершенным. В течение многих лет сложность распознавания графов Берже и совершенных графов рассматривалась отдельно (поскольку еще не было известно, что они эквивалентны), и обе оставались открытыми. Было известно, что они оба находятся в co-NP ; для графов Берже это следует из определения, ^[57] в то время как для совершенных графов это следует из характеристики с использованием произведения числа клик и числа независимости. ^[6] После того, как была доказана сильная теорема о совершенном графе, Чудновский, Корнуэжоль, Лю, Сеймур и Вушкович открыли алгоритм полиномиального времени для проверки существования нечетных дыр или антидыр. По сильной теореме о совершенном графе это можно использовать для проверки того, является ли данный граф совершенным, за полиномиальное время. ^[58]

Связанные концепции

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

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

Ссылки

1. Чудновски, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2003). «Прогресс в области идеальных графов» (PDF) . Математическое программирование . 97 (1-2(B)): 405–422. doi :10.1007/s10107-003-0449-8. MR  2004404. S2CID  5226655. Zbl  1028.05035.
2. Lovász, László (1972). «Нормальные гиперграфы и гипотеза о совершенном графе». Дискретная математика . 2 (3): 253–267. doi :10.1016/0012-365X(72)90006-4. MR  0302480. Zbl  0239.05111.
3. Cornuéjols, Gérard (2002). «Сильная гипотеза о совершенном графе». Труды Международного конгресса математиков, т. III (Пекин, 2002) . Пекин: Higher Education Press. стр. 547–559. arXiv : math/0304464 . MR  1957560. Zbl  1004.05034.
4. Чудновски, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006). «Сильная теорема о совершенном графе». Annals of Mathematics . 164 (1): 51–229. arXiv : math/0212070 . doi :10.4007/annals.2006.164.51. MR  2233847. S2CID  119151552. Zbl  1112.05042.
5. Ловас, Ласло (1972). «Характеристика совершенных графов». Журнал комбинаторной теории . Серия B. 13 (2): 95–98. doi :10.1016/0095-8956(72)90045-7. MR  0309780. Zbl  0241.05107.
6. Gasparian, GS (июнь 1996). «Минимальные несовершенные графы: простой подход». Combinatorica . 16 (2): 209–212. doi :10.1007/bf01844846.
7. Padberg, Manfred W. (декабрь 1974). «Идеальные матрицы ноль-один». Математическое программирование . 6 (1): 180–196. doi :10.1007/bf01580235.О связи между сильной теоремой о совершенном графе и характеристикой произведения совершенных графов см. замечания, предшествующие теореме 2.1 и следующие за теоремой 2.2.
8. Галлай, Тибор (1958). «Максимум-минимум Sätze über Graphen». Acta Mathematica Academiae Scientiarum Hungaricae . 9 (3–4): 395–434. дои : 10.1007/BF02020271. МР  0124238. S2CID  123953062. Збл  0084.19603.
9. Берже, Клод (1961). «Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind». Висс. З. Мартин-Лютер-Унив. Галле-Виттенберг Math.-Natur. Рейхе . 10 : 114.
10. Берж, Клод (1963). «Идеальные графы». Шесть статей по теории графов . Калькутта: Индийский статистический институт. С. 1–21.
11. Чудновский и др. (2003); обратите внимание, что Чудновский и др. определяют емкость, используя дополнение графов, используемых для определения емкости графа по Шеннону , и включают логарифм, который не включен в связанную статью.
12. Hougardy, Stefan (2006). «Классы совершенных графов». Дискретная математика . 306 (19–20): 2529–2571. doi : 10.1016/j.disc.2006.05.021 . MR  2261918. Zbl  1104.05029.
13. "Премии имени Д. Р. Фулкерсона 1991 года по дискретной математике" (PDF) . Лауреаты премии 1991 года. Optima: Mathematical Optimization Society Newsletter (35): 4–8. Ноябрь 1991 г. Получено 21 января 2023 г.
14. Маккензи, Дана (5 июля 2002 г.). «Математика: теория графов раскрывает корни совершенства». Science . 297 (5578): 38. doi :10.1126/science.297.5578.38. PMID  12098683. S2CID  116891342.
15. "Цитата о премии Фулкерсона 2009 года". Mathematical Optimization Society . Получено 21.01.2023 .
16. Чудновская, Мария ; Сеймур, Пол (2005). "Структура графов без клешней" (PDF) . Обзоры по комбинаторике 2005 года. Статьи 20-й Британской комбинаторной конференции, Университет Дарема, Дарем, Великобритания, 10–15 июля 2005 года . Cambridge University Press. стр. 153–171. ISBN 0-521-61523-2. MR  2187738. Zbl  1109.05092.
17. "Двудольные графы". Информационная система по классам графов и их включениям . Получено 24.01.2023 .
18. Кениг, Денес (1931). «Графок — это матрица». Математика – это физика . 38 : 116–119.
19. Троттер, Л. Э. Младший (1977). «Линейно-совершенные графы». Математическое программирование . 12 (2): 255–259. doi :10.1007/BF01593791. MR  0457293. S2CID  38906333. Zbl  0366.05043.
20. Борос, Э .; Гурвич, В. (2006). «Идеальные графы, ядра и ядра кооперативных игр». Дискретная математика . 306 (19–20): 2336–2354. doi :10.1016/j.disc.2005.12.031. MR  2261906. Zbl  1103.05034.
21. Кениг, Денес (1916). «Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre». Математические Аннален . 77 (4): 453–465. дои : 10.1007/BF01456961. ЖФМ  46.0146.03. MR  1511872. S2CID  121097364.
22. Харцхейм, Эгберт (2005). «Графы сравнимости». Упорядоченные множества . Достижения в математике. Т. 7. Нью-Йорк: Springer. С. 353–368. doi :10.1007/0-387-24222-8_12. ISBN 0-387-24219-8. MR  2127991. Zbl  1072.06001.
23. Берж, Клод (1967). «Некоторые классы совершенных графов». Теория графов и теоретическая физика . Лондон: Academic Press. С. 155–165. MR  0232694. Zbl  0203.26403.
24. Мирский, Леон (1971). «Двойственная теорема разложения Дилворта». The American Mathematical Monthly . 78 (8): 876–877. doi :10.2307/2316481. JSTOR  2316481. MR  0288054. Zbl  0263.06002.
25. Perfect, Hazel (1980). «Замечания о теореме Дилворта в отношении трансверсальной теории». Glasgow Mathematical Journal . 21 (1): 19–22. doi : 10.1017/S0017089500003931 . MR  0558270. Zbl  0428.06001.
26. Pnueli, A. ; Lempel, A. ; Even, S. (1971). «Транзитивная ориентация графов и идентификация графов перестановок». Canadian Journal of Mathematics . 23 : 160–175. doi : 10.4153/CJM-1971-016-5 . MR  0292717. Zbl  0204.24604.
27. Колен, Антон WJ ; Ленстра, Ян Карел ; Пападимитриу, Христос Х .; Спиксма, Фриц Ч.Р. (2007). «Интервальное планирование: опрос». Логистика военно-морских исследований . 54 (5): 530–543. дои : 10.1002/nav.20231 . МР  2335544. Збл  1143.90337.
28. Даган, Идо; Голумбик, Мартин Чарльз ; Пинтер, Рон Яир (1988). «Трапециевидные графы и их раскраска». Дискретная прикладная математика . 21 (1): 35–46. doi :10.1016/0166-218X(88)90032-7. MR  0953414. Zbl  0658.05067.
29. Робертс, Фред С. (1969). «Графы безразличия». Методы доказательства в теории графов (Труды Второй конференции по теории графов в Энн-Арборе, Энн-Арбор, Мичиган, 1968) . Нью-Йорк: Academic Press. стр. 139–146. MR  0252267. Zbl  0193.24205.
30. Скрин, Дейл Дж. (1982). «Связь между триангулированными графами, графами сравнимости, правильными интервальными графами, правильными круговыми дуговыми графами и вложенными интервальными графами». Журнал теории графов . 6 (3): 309–316. doi :10.1002/jgt.3190060307. MR  0666799. Zbl  0495.05027.
31. Golumbic, Martin Charles (1978). «Тривиально совершенные графы». Discrete Mathematics . 24 (1): 105–107. doi :10.1016/0012-365X(78)90178-4. MR  0522739. Zbl  0384.05057.
32. Хаммер, Питер Л.; Симеоне, Бруно (1981). «Разделение графа». Combinatorica . 1 (3): 275–284. doi :10.1007/BF02579333. MR  0637832.
33. Prömel, Hans Jürgen; Steger, Angelika (1992). «Почти все графы Берже совершенны». Combinatorics, Probability and Computing . 1 (1): 53–79. doi :10.1017/S0963548300000079. MR  1167295. S2CID  28696495. Zbl  0793.05063.
34. МакДиармид, Колин; Йолов, Никола (2019). «Случайные совершенные графы». Случайные структуры и алгоритмы . 54 (1): 148–186. arXiv : 1604.00890 . doi : 10.1002/rsa.20770. MR  3884617. S2CID  53489550. Zbl  1405.05165.
35. Rose, Donald J. (декабрь 1970 г.). «Триангулированные графы и процесс исключения». Журнал математического анализа и приложений . 32 (3): 597–609. doi :10.1016/0022-247x(70)90282-9.
36. Дирак, Джорджия (1961). «О жестких схемных графах». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 25 (1–2): 71–76. дои : 10.1007/BF02992776. MR  0130190. S2CID  120608513.
37. Harary, Frank (1974). "Последние результаты по деревьям". В Bari, Ruth A. ; Harary, Frank (ред.). Графы и комбинаторика: Труды Капитальной конференции по теории графов и комбинаторике в Университете Джорджа Вашингтона, 18–22 июня 1973 г. Lecture Notes in Mathematics. Vol. 406. Springer. pp. 1–9. doi :10.1007/bfb0066429. ISBN 9783540378099.
38. Földes, Stéphane; Hammer, Peter Ladislaw (1977). "Split graphs". Труды Восьмой юго-восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, Луизиана, 1977) . Congressus Numerantium. Т. XIX. Виннипег: Utilitas Math. стр. 311–315. MR  0505860.
39. Бандельт, Ханс-Юрген; Малдер, Генри Мартин (1986). «Дистанционно-наследственные графы». Журнал комбинаторной теории . Серия B. 41 (2): 182–208. doi :10.1016/0095-8956(86)90043-2. ​​MR  0859310. Zbl  0605.05024.
40. Юнг, HA (1978). «О классе частично упорядоченных множеств и соответствующих графах сравнимости». Журнал комбинаторной теории, Серия B. 24 ( 2): 125–133. doi : 10.1016/0095-8956(78)90013-8 . Zbl  0382.05045.
41. Корнейл, Д.Г .; Лерчс, Х.; Стюарт Берлингем, Л. (1981). «Дополнительные сводимые графы». Дискретная прикладная математика . 3 (3): 163–174. doi :10.1016/0166-218X(81)90013-5. MR  0619603. Zbl  0463.05057.
42. Kay, David C.; Chartrand, Gary (1965). «Характеристика некоторых птолемеевых графов». Canadian Journal of Mathematics . 17 : 342–346. doi : 10.4153/CJM-1965-034-0 . MR  0175113. Zbl  0139.17301.
43. Хеггернес, Пинар ; Кратч, Дитер (2007). «Линейно-временные сертифицированные алгоритмы распознавания и запрещенные индуцированные подграфы» (PDF) . Nordic Journal of Computing . 14 (1–2): 87–108 (2008). MR  2460558. Zbl  1169.68653.
44. "Пороговые графы". Информационная система по классам графов и их включениям . Получено 2023-02-12 .
45. Гаврил, Фаника (1972). «Алгоритмы минимальной раскраски, максимальной клики, минимального покрытия кликами и максимального независимого множества хордового графа». SIAM Journal on Computing . 1 (2): 180–187. doi :10.1137/0201013.
46. Хаммер, Питер Л.; Маффрей, Фредерик (1990). «Полностью отделимые графы». Дискретная прикладная математика . 27 (1–2): 85–99. doi : 10.1016/0166-218x(90)90131-u .
47. Хоанг, CT; Рид, BA (сентябрь 1989). «Некоторые классы совершенно упорядочиваемых графов». Журнал теории графов . 13 (4): 445–463. doi :10.1002/jgt.3190130407.
48. Gyárfás, A.; Lehel, J. (июнь 1988). «Онлайн и первая подходящая раскраска графов». Журнал теории графов . 12 (2): 217–227. doi :10.1002/jgt.3190120212.
49. Golumbic, Martin Charles ; Trenk, Ann N. (2004). Графики толерантности . Cambridge Studies in Advanced Mathematics. Vol. 89. Cambridge University Press. doi : 10.1017/CBO9780511542985. ISBN 0-521-82758-2. МР  2051713.
50. Хоанг, CT (1987). «О гипотезе Мейниэля». Журнал комбинаторной теории, Серия B. 42 ( 3): 302–312. doi :10.1016/0095-8956(87)90047-5. MR  0888682. Zbl  0634.05058.
51. Cicerone, Serafino; Di Stefano, Gabriele (1999). «Классы графов между четностью и дистанционно-наследуемыми графами». Discrete Applied Mathematics . 95 (1–3): 197–216. doi :10.1016/S0166-218X(99)00075-X. MR  1708837. Zbl  0933.05144.
52. Jansen, Klaus (1998). "Новая характеристика для графов четности и проблема раскраски со стоимостью". В Lucchesi, Claudio L.; Moura, Arnaldo V. (ред.). LATIN '98: Теоретическая информатика, Третий латиноамериканский симпозиум, Кампинас, Бразилия, 20-24 апреля 1998 г., Труды . Заметки лекций по информатике. Том 1380. Springer. стр. 249–260. doi :10.1007/BFb0054326. hdl : 11858/00-001M-0000-0014-7BE2-3 . MR  1635464. Zbl  0910.05028.
53. Chvátal, Václav (1975). «О некоторых многогранниках, связанных с графами». Журнал комбинаторной теории, Серия B. 18 ( 2): 138–154. doi :10.1016/0095-8956(75)90041-6. MR  0371732. Zbl  0277.05139.
54. Грётшель, Мартин ; Ловас, Ласло ; Шрайвер, Александр (1984). «Полиномиальные алгоритмы для совершенных графов». В Berge, C.; Chvátal, V. (ред.). Темы о совершенных графах . North-Holland Mathematics Studies. Том 88. North-Holland, Амстердам. стр. 325–356. doi :10.1016/S0304-0208(08)72943-8. MR  0778770.
55. Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1988). Геометрические алгоритмы и комбинаторная оптимизация . Спрингер-Верлаг. МР  0936633. Збл  0634.05001.См. особенно главу 9 «Стабильные множества в графах», стр. 273–303.
56. Golumbic, Martin Charles (1980). Алгоритмическая теория графов и совершенные графы . Academic Press. doi :10.1016/C2013-0-10739-8. ISBN 0-444-51530-5.Второе издание, Annals of Discrete Mathematics 57, Elsevier, 2004.
57. Lovász, László (1983). "Идеальные графы". В Beineke, Lowell W.; Wilson, Robin J. (ред.). Избранные темы в теории графов, т. 2. Academic Press. стр. 55–87. ISBN 0-12-086202-6.
58. Чудновский, Мария ; Корнюжоль, Жерар ; Лю, Синьмин; Сеймур, Пол ; Вушкович, Кристина (2005). «Распознавание графов Берге». Комбинаторика . 25 (2): 143–186. дои : 10.1007/s00493-005-0012-8. S2CID  2229369.
59. Gyárfás, A. (1987). "Problems from the world around the perfect graphs" (PDF) . Труды Международной конференции по комбинаторному анализу и его приложениям (Pokrzywna, 1985). Zastosowania Matematyki . 19 (3–4): 413–441 (1988). MR  0951359.
60. Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997). «Claw-free graphs — A survey». Discrete Mathematics . 164 (1–3): 87–147. doi : 10.1016/S0012-365X(96)00045-3 . MR  1432221.

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

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