Совершенные графы и Сильная теорема: Элита дискретной математики

Граф называется совершенным (Perfect graph), если хроматическое число равно кликовому числу не только для самого графа, но и для абсолютно любого его индуцированного подграфа (части графа, образованной удалением некоторых вершин). Понятие было введено Клодом Бержем в 1960 году. К совершенным графам относятся двудольные графы, хордальные графы и графы интервалов.

Почему программисты обожают совершенные графы? Потому что почти все NP-трудные задачи (поиск клики, раскраска, независимое множество) на совершенных графах решаются за полиномиальное время! Если вы знаете, что структура ваших данных образует совершенный граф (например, матрица несовместимости регистров в компиляторе имеет вид интервального графа), вы можете отбросить экспоненциальный перебор и использовать быстрые алгоритмы.

В этой теории есть две грандиозные математические теоремы:

1. Слабая теорема о совершенных графах (Доказана Ласло Ловасом в 1972 г.): Граф является совершенным тогда и только тогда, когда его дополнение (инверсия ребер) также является совершенным графом. Это глубокая структурная симметрия.
2. Сильная теорема о совершенных графах (Доказана Марией Чудновской, Нилом Робертсоном, Полом Сеймуром и Робином Томасом в 2002 г.): Это было одно из важнейших математических доказательств начала XXI века. Теорема гласит, что граф совершенен тогда и только тогда, когда он не содержит в себе в качестве индуцированных подграфов "нечетных дыр" (циклов нечетной длины от 5 и более) и "нечетных анти-дыр" (дополнений нечетных циклов).

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