Протокол доказательства с нулевым знанием для задачи раскраска графа

Обновлено: 04.07.2024

Математик-любитель Обри де Грей (Aubrey de Grey) шокировал математиков, сделав первый за много десятилетий значительный прорыв в решении давней математической проблемы — той, над которой ломали головы лучшие умы последних 60 лет.

Проблема, называемая задачей Нелсона-Эрдёша-Хадвигера , по сути говорит о несоприкосаемых цветах и о том, как много, — а точнее, насколько мало, — их может быть на графе с потенциально бесконечным числом связей.

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

Да, вот так просто можно объяснить суть задачи Нелсона-Эрдёша-Хадвигера, но решить ее очень непросто — особенно, когда мы теоретически говорим о бесконечном числе связанных вершин.

Впервые задачу сформулировал в 1950-м году Эдвард Нельсон , математик из Принстона. Ее так никогда окончательно не решили, и вовсе не потому, что не пытались.

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

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

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

Кстати, в 2009 году он Обри де Грей даже приезжал в Россию по приглашению фонда “Наука за продление жизни” и выступал с лекциями в МГУ и Доме ученых.

К счастью, в прошедшее Рождество у него появилось достаточно свободного времени, чтобы заняться задачей Нелсона-Эрдёша-Хадвигера. И он вывел, что предположение, которое выдвинули математики много десятилетий назад, на самом деле неверно!

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

Де Грей совершил открытие, применяя задачку к фигуре, называемой Веретеном Мозера , в которой 7 вершин и 11 граней.

Объединив множество таких фигур вместе с некоторыми другими, де Грей получил фигуру с 20,425 точками, которой требовалось больше 4 цветов: впервые(!) за 60 лет промежуток для задачи Нелсона-Эрдёша-Хадвигера сузился.

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

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

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

Ну а что касается де Грея, человека, который мечтает,что когда-нибудь мы будем жить до 1000 лет, он довольно скромно отнесся к открытию: “Мне просто невероятно повезло. Не каждый день кто-то находит решение 60-летней задачи.”

Гордон Роял (Gordon Royle), математик из Университета Западной Австралии, так прокомментировал открытие: “В таких задачах как эта финальное решение может лежать в глубинах математической науки, а может зависить от чьей-либо изобретательности в поиске графа, который потребует много цветов.”

При раскрашивании карты (например, стран на карте мира) желательно раскрасить соседние области в разные цвета, чтобы их границы были четко видны, — но при этом, чтобы избежать лишней пестроты, использовать минимальное количество цветов. В середине XIX века Фрэнсис Гатри заметил, что карту графств Англии можно раскрасить таким образом всего четырьмя цветами, и его заинтересовало, обладает ли этим свойством любая карта. Он спросил своего брата, который передал вопрос одному из своих профессоров; так родилась знаменитая математическая задача: гипотеза четырех цветов.

Задача о раскраске графа

Под раскраской графа понимается аналогичный процесс с ненаправленным графом G, в котором узлы играют роль раскрашиваемых областей, а ребра представляют соседние пары. Требуется назначить цвет каждому узлу G так, чтобы при наличии ребра (u, v) узлам u и v были назначены разные цвета; целью является выполнение этих условий с минимальным набором цветов. В более формальном варианте k-раскраской G называется такая функция f: V → , что для каждого ребра (u, v) выполняется f(u) = f(v). (Таким образом, цвета обозначаются 1, 2, . k, а функция f представляет выбор цвета для каждого узла.) Если для G существует k-раскраска, он называется k-раскрашиваемым.

В отличие от карт на плоскости, вполне очевидно, что не существует фиксированной константы k, с которой любой граф имеет k-раскраску: например, если взять множество из n узлов и соединить каждую пару ребром, то для раскраски полученного графа потребуется n цветов. Тем не менее алгоритмическая версия задачи очень интересна:

Для заданного графа G и границы k имеет ли граф G k-раскраску?

Будем называть эту задачу задачей раскраски графа — или k-раскраски, когда мы хотим подчеркнуть конкретный выбор k.

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

♦ Допустим, имеется набор из n процессов в системе, которая позволяет выполнять несколько заданий в параллельном режиме. При этом некоторые пары заданий не могут выполняться одновременно, потому что им нужен доступ к некоторому ресурсу. Для следующих k временных квантов требуется спланировать выполнение процессов, чтобы каждый процесс выполнялся минимум в одном из них. Возможно ли это? Если построить граф G на базе множества процессов, соединяя два процесса ребром при наличии конфликта, то k-раскраска G будет представлять план выполнения, свободный от конфликтов: все узлы, окрашенные в цвет j, будут выполняться на шагеj, а вся конкуренция за ресурсы будет исключена.

♦ Другое известное применение задачи встречается при разработке компиляторов. Предположим, при компиляции программы мы пытаемся связать каждую переменную с одним из к регистров. Если две переменные используются одновременно, они не могут быть связаны с одним регистром (в противном случае присваивание одной переменной приведет к потере значения другой). Для множества переменных строится граф G; две переменные соединяются ребром в том случае, если они используются одновременно. K-раскраска G соответствует безопасному способу распределения переменных между регистрами: все узлы с раскраской j могут быть связаны с регистром j, так как никакие два из них не используются одновременно.

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

Вычислительная сложность задачи о раскраске графа

Какую сложность имеет задача k-раскраски? Прежде всего, в случае k = 2 возникает задача, которую мы уже видели в главе 3. Вспомните, что мы рассматривали задачу определения того, является ли граф G двудольным, и показали, что она эквивалентна следующему вопросу: можно ли раскрасить узлы G в красный и синий цвета так, чтобы у каждого ребра один конец был красным, а другой синим?

Но последний вопрос в точности соответствует задаче о раскраске графа для k = 2 цветам (красный и синий). Таким образом, мы показали, что

(8.21) Граф G является 2-раскрашиваемым в том, и только в том случае, если он является двудольным.

Это означает, что алгоритм из раздела 3.4 может использоваться для принятия решения о том, является ли входной граф 2-раскрашиваемым, за время O(m + n), где n — количество узлов G, а m — количество ребер.

Стоит перейти к k = 3 цветам, как ситуация значительно усложняется. Никакого простого эффективного алгоритма для задачи 3-раскраски не видно, и рассуждать об этой задаче вообще сложно. Например, изначально может возникнуть впечатление, что в любом графе, не являющиеся 3-раскрашиваемым, присутствует “доказательство” в форме четырех узлов, являющихся взаимно смежными (для которых потребуются четыре разных цвета) — но это не так. Например, граф на рис. 8.10 не имеет 3-раскраски по более тонкой (хотя и объяснимой) причине; более того, можно привести намного более сложные графы, не являющиеся 3-раскрашиваемыми по причинам, для которых трудно найти компактное объяснение.

Рис. 8.10. Граф, не имеющим 3-раскраски

Более того, как вы сейчас убедитесь, в случае трех цветов задача уже становится очень сложной.

Доказательство NР-полноты задачи о 3-раскраске

(8.22) Задача о 3-раскраске является NP-полной.

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

Как и другие задачи в этом разделе, задачу о 3-раскраске графа трудно связать с другой NP-полной задачей, виденной ранее, поэтому мы снова вернемся к 3-SAT. Заданный экземпляр 3-SAT с переменными x₁, . x_n и условиями C₁, . C_k будет решен с использованием “черного ящика” для решения задачи 3-раскраски.

Начало сведения выглядит вполне ожидаемо. Возможно, основное достоинство 3-раскраски при кодировании булевых выражений заключается в том факте, что мы можем связать узлы графа с конкретными литералами, а соединяя узлы ребрами, можно гарантировать, что им будут назначены разные цвета; это обстоятельство позволяет связать с одним узлом истинное, а с другим — ложное значение. С учетом сказанного мы определяем узлы и соответствующие каждой переменной и ее отрицанию Также определяются три “специальных узла” Т, F и В (сокращения от True, False и Base).

Для начала мы соединим каждую пару узлов v_i, ребром и соединим оба этих узла с Base (в результате чего образуется треугольник из v_i, и Base для каждого У). Также True, False и Baseсоединяются в треугольник. Простой граф G, определенный к настоящему моменту, изображен на рис. 8.11, и он уже обладает рядом полезных свойств.

♦ В любой 3-раскраске графа G узлам v_i и должны быть назначены разные цвета, и оба они должны отличаться от цвета Base.

♦ В любой 3-раскраске графа G узлам True, False и Base должны быть назначены все три цвета в некоторой перестановке. В дальнейшем эти три цвета будут называться цветами True, False и Base в зависимости от того, какому из узлов соответствует тот или иной цвет. В частности, это означает, что для всех i одно из значений v_i или получает цвет True, а другому достается цвет False. В оставшейся части этого построения будем считать, что переменной х_i значение 1 в заданном экземпляре 3-SAT присваивается в том, и только в том случае, если узлу v_i назначается цвет True.

Рис. 8.11. Начало сведения для задачи о 3-раскраске

Короче говоря, мы получили граф G, в котором любая 3-раскраска неявно определяет логическое присваивание для переменных в экземпляре 3-SAT. Теперь необходимо нарастить G так, чтобы только выполняющие присваивания могли быть расширены до 3-раскрасок полного графа. Как это сделать?

Как и в других сведениях 3-SAT, рассмотрим условие вида На языке 3-раскраски графа G это означает: “По крайней мере одному из узлов или v₃ должен быть назначен цвет True”. Итак, нам нужен маленький подграф, который можно присоединить к G, чтобы любая 3-раскраска, расширяющаяся на этот подграф, обладала свойством назначения цвета True по крайней мере одному из узлов или v₃. Найти такой подграф удается не сразу, но один из работающих вариантов изображен на рис. 8.12.

Этот подграф из шести узлов “присоединяется” к основному графу G в пяти существующих узлах: True, False и узлах, соответствующих трем литералам в условии, которое мы пытаемся представить (в данном случае и v₃). Теперь предположим, что в некоторой 3-раскраске G всем трем узлам или v₃ назначен цвет False. Тогда двум нижним затемненным узлам подграфа должен достаться цвет Base, а трем затемненным узлам над ними — соответственно цвета False, Base и True, а следовательно, для верхних затемненных узлов цветов уже не останется. Другими словами, 3-раскраска, в которой ни одному из узлов или v₃ не назначается цвет True, не может быть расширена до 3-раскраски этого подграфа 2 .

Рис. 8.12. Присоединение подграфа для представления условия

Наконец, ручная проверка показывает, что если одному из узлов или v₃ назначен цвет True, весь подграф может иметь 3-раскраску.

Далее остается лишь завершить построение: мы начинаем с графа G, определенного выше, и для каждого условия в экземпляре 3-SAT присоединяем подграф из шести узлов, изображенный на рис. 8.12. Назовем полученный граф G'.

Утверждается, что заданный экземпляр 3-SAT выполним в том, и только в том случае, если граф G' имеет 3-раскраску. Сначала предположим, что для экземпляра 3-SAT существует выполняющее присваиванием. Определим раскраску G', окрасив Base, True и False в три разных цвета, а затем для каждого У назначим v цвет True, если х_i = 1, или цвет False, если х_i = 0. После этого назначается единственный свободный цвет. Наконец, как объяснялось выше, теперь эта 3-раскраска может быть расширена на каждый подграф условия, состоящий из шести узлов, что приведет к 3-раскраске всех G'.

И наоборот, предположим, что у G' существует 3-раскраска. В этой раскраске каждому узлу v_i назначается либо цвет True, либо цвет False; переменная x_i задается соответствующим образом. Теперь утверждается, что в каждом условии экземпляра 3-SAT по крайней мере один из литералов в условии имеет значение истинности 1. В противном случае всем трем соответствующим узлам в 3-раскраске G' был бы назначен цвет False, но, как было показано выше, в такой ситуации не существует 3-раскраски соответствующего подграфа условия, — возникает противоречие. ■

При k > 3 задача о 3-раскраске очень легко сводится к k-раскраске. Фактически все, что требуется, — взять экземпляр задачи 3-раскраски, представленный графом G, добавить k - 3 новых узлов и соединить эти новые узлы друг с другом и с каждым узлом в G. Полученный граф является k-раскрашиваемым в том, и только в том случае, если исходный граф G является 3-раскрашиваемым. Следовательно, k-раскраска для всех k > 3 также является NР-полной.

Заключение: о проверке гипотезы четырех цветов

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

Библиотека образовательных материалов для студентов, учителей, учеников и их родителей.

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

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

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

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

Содержание

Введение 3
1.Теоремы и оценки, относящиеся к хроматическим числам
1.1Нижние оценки для . 5
1.2. Верхние оценки для . 5
1.3. Гипотеза четырех красок. 6
2. Приближенные алгоритмы раскрашивания.
2.1. Переборный алгоритм для раскраски 9
2.2. Раскраска ребер 11
2.3. Рационализация поиска наибольшего независимого множества 15
3. Задачи раскраски.
3.1. Простая задача размещения (загрузки). 17
3.2. Составление графиков осмотра (проверки). 18
3.3. Распределение ресурсов. 18
Заключение 19
Список литературы 21

Прикрепленные файлы: 1 файл

graf-raskras.docx

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

Рис. 1.

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

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

2.2. Раскраска ребер

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

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

Теорема 1. Для любого графа справедливы неравенства .

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

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

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

ребро не окрашено;

ребро окрашено в цвет , ;

в вершине отсутствует цвет , ;

все попарно различны.

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

Рис. 2.

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

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

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

(Б) Цвет совпадает с одним из цветов . Пусть . Рассмотрим вершины . В каждой из них отсутствует какой-нибудь из цветов или . Значит, в подграфе, образованном ребрами этих двух цветов, степень каждой из этих вершин не превосходит 1. Следовательно, все три вершины не могут принадлежать одной -компоненте. Рассмотрим две возможности.

(Б1) Вершины и принадлежат разным -компонентам. Перекрасим веер . Ребро станет неокрашенным. Теперь перекрасим -компоненту, содержащую вершину . После этого цвет будет отсутствовать в вершине и ребро можно окрасить в этот цвет.

(Б2) Вершины и принадлежат разным -компонентам. Перекрасим веер . Ребро станет неокрашенным. Теперь перекрасим -компоненту, содержащую вершину . После этого цвет будет отсутствовать в вершине и ребро можно окрасить в этот цвет.

Итак, в любом случае получаем правильную раскраску, в которой добавилось еще одно раскрашенное ребро .

На рис. 3 иллюстрируются случаи (Б1) и (Б2) на примере веера из рисунка 2. Здесь , . Левое изображение соответствует случаю (Б1): вершины и принадлежат разным -компонентам. После перекраски веера и -компоненты, содержащей вершину , появляется возможность окрасить ребро в цвет 5. Случай (Б2) показан справа: здесь вершины и принадлежат разным -компонентам, поэтому после перекраски веера , , , , и -компоненты, содержащей вершину , появляется возможность окрасить ребро в цвет 5.

Рис. 3.

Итак, все графы делятся на два класса: у одних хроматический индекс равен максимальной степени вершины, у других он на единицу больше. Оказывается, определение принадлежности графа к тому или иному классу является NP-трудной задачей. Алгоритм, который можно извлечь из доказательства теоремы 3.2, за полиномиальное время находит раскраску в не более чем цветов. Его можно назвать "идеальным" приближенным алгоритмом - более высокую точность имеет только точный алгоритм.

5. Рационализация поиска наибольшего независимого множества

Известны различные приемы сокращения перебора при использовании описанной стратегии исчерпывающего поиска. Один из них основан на следующем наблюдении. Допустим, в графе , для которого нужно найти наибольшее независимое множество, имеются две вершины и , такие, что каждая вершина, отличная от и смежная с вершиной , смежна и с вершиной . Иначе говоря, . Будем говорить в этом случае, что вершина поглощает вершину . Если при этом вершины и смежны, то скажем, что вершина смежно поглощает вершину . Вершину в этом случае назовем смежно поглощающей. Например, в графе, изображенном на рис. 4, вершина 2 смежно поглощает вершины 1 и 3. Вершины 5 и 6 в этом графе тоже являются смежно поглощающими.

Рис. 4.

Теорема 1. Если вершина является смежно поглощающей в графе , то .

Доказательство. Допустим, вершина смежно поглощает вершину в графе . Пусть - наибольшее независимое множество графа . Если не содержит вершину , то оно является наибольшим независимым множеством и в графе , так что в этом случае . Предположим, что множество содержит вершину . Тогда ни одна вершина из множества не принадлежит . Значит, не содержит вершину и ни одну вершину из множества . Но тогда множество тоже будет независимым, причем оно целиком содержится в графе , а число элементов в нем такое же, как в множестве . Значит, и в этом случае .

Итак, если мы удалим из графа смежно поглощающую вершину , то получим граф с тем же числом независимости. Так как новый граф является порожденным подграфом исходного графа , то каждое наибольшее независимое множество нового графа будет наибольшим независимым множеством исходного. Этот прием называется "сжатием по включению". Исследование применимости и применение операции сжатия по включению к каждому встречающемуся подграфу требуют, конечно, дополнительных расходов времени (каких?), но могут привести к существенному сокращению дерева подзадач. Для некоторых графов задача о независимом множестве может быть решена с помощью одних только сжатий по включению. Таков, например, граф , и вообще любой лес. Действительно, любая вершина, смежная с листом, поглощает этот лист. Рассмотрим более широкий класс графов, для которых этот прием эффективен.

3. Задачи раскраски.

3.1. Простая задача размещения (загрузки).

3.2. Составление графиков осмотра (проверки).

3.3. Распределение ресурсов.

Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов . Построим граф G: каждой работе соответствует определенная вершина графа, а ребро существует в графе тогда и только тогда, когда для выполнения i-й и j-й работ требуется хотя бы один общий ресурс, т. е. когда . Это означает, что i-я и j-я работы не могут выполняться одновременно. Раскраска графа G определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цвета, выполняются одновременно. Наилучшее использование ресурсов (т.е. выполнение всех n работ за наименьшие время) достигается при оптимальной раскраске вершин графа G.

Заключение

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

В этой статье мы расскажем о недавнем удивительном продвижении в одной из самых известных задач комбинаторной геометрии. Это задача о так называемом хроматическом числе плоскости. Требуется найти минимальное число цветов, в которые можно так покрасить плоскость, чтобы расстояние между точками одного цвета никогда не равнялось единице. Это число и называется хроматическим, а обозначается оно \( χ (\mathbb^2) \). Зачем так много букв? Ну, просто красить можно не только плоскость — можно и прямую, и пространство, и многие другие интересные объекты. На прямой, кстати, все почти очевидно: \( χ (\mathbb^1) = 2 \), так как одного цвета, конечно, не хватит, а двух достаточно, о чем свидетельствует рисунок 1. Что же с плоскостью?

Рис. 1. Раскраска прямой в 2 цвета

Рис. 2. Мозеровское веретено

Рис. 3. Первая раскраска плоскости в 7 цветов

Рис. 4. Вторая раскраска плоскости в 7 цветов

Задача об отыскании хроматического числа плоскости возникла в 1950 году (см. [1]), хотя еще в 1944 году очень близкую задачу изучал Хадвигер. До недавнего времени все, что было известно о хроматическом числе, — это с легкостью доказанные нами только что оценки

Иными словами, около 70 лет в крайне популярной задаче было целых 4 варианта ответа, и никаких продвижений к установлению истины не было!

Отметим ряд интересных смежных фактов. Например, все нижние оценки, которые мы получали, это фактически оценки с помощью графов. И треугольник, и мозеровское веретено — это так называемые дистанционные графы, т.е. графы, вершины которых — точки плоскости, а ребра — отрезки длины 1, соединяющие пары точек, отстоящих друг от друга на расстояние 1. Напомним, что хроматическое число графа G — это минимальное число цветов \( χ(G)\), в которые можно так покрасить вершины графа, чтобы концы любого ребра имели разные цвета. Таким образом, \( χ (\mathbb^2) ≥ χ(G) \) для любого дистанционного графа G. В 1976 году Эрдёш поставил вопрос, существуют ли дистанционные графы с хроматическим числом 4 (как у мозеровского веретена), но без треугольников. Оказалось, и такое бывает! Сейчас известны примеры всего лишь на двадцати трех вершинах (см. [2]).

Многие другие любопытные факты можно найти в книгах [1] и [3].

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

В работе ди Грея дистанционный граф с хроматическим числом 5 имел 1581 вершину. Сейчас уже найдены графы с 553 вершинами [6]. И есть смельчаки, надеющиеся отыскать графы с хроматическим числом 6!

В настоящей статье мы расскажем о том, как получается результат ди Грея.

О пользе свежего взгляда

Рис. 5. Подграфы в веретене Мозеров

Разобьем граф Голомба на два подграфа (рис. 6, а). Первый из них — шестиугольник, содержащий шесть равносторонних треугольников. С точностью до перестановок цветов он красится в три цвета единственным образом (рис. 6, б) Значит, вершины равностороннего треугольника A′B′C′ со стороной \( \sqrt \) раскрашены в этом случае в один цвет.

Рис. 6. Подграфы в графе Голомба

Обозначим здесь и далее \( Δ_> \) — множество, состоящее из вершин равностороннего треугольника со стороной \( \sqrt \). При этом расположение треугольника на плоскости может быть любым.

Во втором подграфе вершины такого равностороннего треугольника соединены с вершинами равностороннего треугольника со стороной 1 (рис. 6, в). При раскраске в три цвета точки X, Y, Z разноцветные. Тогда A″, B″, C″ не могут быть одного цвета, поскольку он совпадет с цветом одной из точек X, Y, Z. Таким образом, в графе Голомба к противоречию приводит раскраска двух подграфов: первый из них гарантирует, что вершины \( Δ_> \) будут одноцветными, а второй исключает такую возможность.

Именно так и действовал ди Грей: он рассматривал в качестве шаблона треугольник \( Δ_> \), как в графе Голомба, и перебирал раскраски в 4 цвета двух довольно сложных дистанционных графов, о которых речь пойдет далее.

Построение графа, содержащего одноцветный \( Δ_> \)

В каких множествах точек среди попарных расстояний встречается много единиц, а среди всевозможных треугольников — много \( Δ_> \)? Первое, что приходит в голову, это кусок треугольной решетки. Рассуждая от противного, предположим, что одноцветный треугольник \( Δ_> \) отсутствует. Это не приводит к противоречию сразу, но сильно ограничивает число возможных раскрасок.

1. Убедитесь, что если правильная раскраска в 4 цвета графа на рисунке 7 не содержит одноцветного \( Δ_> \), то: а) каждый цвет, кроме цвета центральной вершины, встречается ровно два раза; б) с точностью до поворотов и перестановок цветов допустимы только две раскраски.

Рис. 7. Раскраски графа на 7 вершинах

2. Докажите, что всякая раскраска треугольной решетки в 4 цвета, не содержащая одноцветного \( Δ_> \), состоит из чередующихся линий сетки, на каждой из которых есть вершины только двух цветов.

Указание. Можно рассмотреть два случая: а) в шестиугольниках встречается только раскраска, приведенная на рисунке 7 справа; б) хотя бы в одном шестиугольнике встречается тип раскраски, как на рисунке 7 слева.

Рис. 8. Граф Q

Возьмем участок треугольной решетки в форме цветка (рис. 8) и назовем этот граф Q. С точностью до поворотов и перестановок цветов существует шесть раскрасок центрального большого шестиугольника без одноцветного \( Δ_> \) (рис. 9). Цвета двенадцати крайних вершин нам не интересны, хотя их наличие влияет на число вариантов раскраски. Важно, что в раскрасках a, г все вершины шестиугольника раскрашены в тот же цвет, что и его центр; в раскрасках б, д таких вершин четыре, а в раскрасках в, е только две.

Рис. 9. Возможные раскраски центральной области в графе Q

Рис. 10. Граф X состоит из двух экземпляров графа Q с общей центральной вершиной

Что будет, если взять два экземпляра графа Q₁ и Q₂ с общей центральной вершиной и повернуть один из них на угол \( α = 2 \text \frac \) относительно другого (рис. 10)? В получившемся графе, обозначим его X, расстояния между соответствующими вершинами шестиугольников равны единице:

AA′ = BB′ = CC′ = DD′ = EE′ = FF′ = 1.

Кроме того, в каждом из экземпляров графа Q две, четыре или шесть вершин шестиугольника раскрашены в тот же цвет, что и центральная. Если хотя бы в одном из экземпляров таких вершин четыре или шесть, то найдутся две вершины одного цвета на расстоянии 1. Следовательно, в Q₁ и Q₂ допустимы лишь раскраски в, е.

Наконец, заметим, что в раскрасках в, е концы диагоналей шестиугольников раскрашены одинаково. Поэтому в графе X при дополнительном условии об отсутствии одноцветного \( Δ_> \) вершины A, D имеют один цвет — почти как в трехцветной раскраске веретена Мозеров. Возьмем два экземпляра графа X, совместим их и повернем один из них относительно другого вокруг A на угол \( β = 2 \text \frac \). Тогда \( D\tilde = 1 \) и эти вершины раскрашены в тот же цвет, что и A. Мы пришли к противоречию, а значит, построен граф G, в котором хотя бы один треугольник \( Δ_> \) раскрашен в один цвет (рис. 11).

Рис. 11. Граф G, в свою очередь, состоит из двух экземпляров графа X

Упражнение 3. Докажите, что если множество узлов треугольной сетки размножить тремя поворотами на углы α, β, α вокруг одного и того же узла, получая при этом еще три экземпляра сетки (рис. 12), то полученный бесконечный дистанционный граф при любой раскраске узлов в 4 цвета также содержит одноцветный \( Δ_> \). Как и выше, \( α = 2 \text \frac \), \( β = 2 \text \frac \).

Рис. 12. Четыре экземпляра треугольной сетки

Построение графа, исключающего раскраску \( Δ_> \) в один цвет

Ди Грей предположил, что если в дистанционном графе содержится достаточно много веретен Мозеров в качестве подграфов, то удастся исключить одноцветную раскраску хотя бы одного фиксированного треугольника \( Δ_> \). Как построить такой дистанционный граф, чтобы на одну вершину в среднем приходилось как можно больше веретен? После ряда неудачных попыток ди Грей пришел к конструкции, при описании которой пригодится следующее определение.

Определение. Пусть X, Y — некоторые множества векторов (вообще говоря, X, Y могут состоять из чего угодно, лишь бы была определена операция сложения). Суммой Минковского M = X + Y называется множество, состоящее из всех возможных сумм x + y, где x ∈ X, y ∈ Y (см. пример на рисунке 13).

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

Рис. 14. Классы эквивалентности ребер. Граф V

P, Q, R> ⊂ V ⊂ V + V ⊂ V + V + V.

Упражнение 4. а) Убедитесь, что если кузнечику разрешается сделать не более 2 прыжков, то ему доступны вершины графа W = V + V. б) Докажите, что W содержит веретено Мозеров в качестве подграфа.

Оказывается, что если отметить все точки, в которые кузнечик может попасть за 0, 1, 2 или 3 прыжка (V + V + V) и покрасить точки P, Q, R в один цвет, то правильно раскрасить остальные вершины в четыре цвета невозможно!

Искомый граф построен, но компьютерный перебор раскрасок затрагивает лишь небольшую часть вершин. Ди Грей не стал спешить с публикацией и попробовал сделать построение более экономным. Опишем вариант, к которому он пришел.

Пусть W′ состоит из векторов из W, длина которых не превосходит \( \sqrt \). Пусть U — подграф V на 7 вершинах, показанный на рисунке 7.

Упражнение 5. Найдите мощности множеств W и W′.

Рис. 15. Граф H на 1345 вершинах

Граф H = W′ + U имеет 1345 вершин и является подграфом V + V + V (рис. 15). Если раскрасить в первый цвет три точки в вершинах \( Δ_> \), выбранных из вершин U, компьютерный перебор показывает, что для раскраски остальных вершин четырех цветов (включая первый) не хватает.

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

Плоские дистанционные графы с хроматическим числом 5

В предыдущих разделах мы описали построение графа G, при раскраске которого в 4 цвета хотя бы один из треугольников \( Δ_> \) будет раскрашен в один цвет, и графа H, при раскраске которого в 4 цвета фиксированный треугольник \( Δ_> \) не может быть одноцветным. Из первого условия следует, что на плоскости, раскрашенной в 4 цвета, найдется одноцветный \( Δ_> \), а из второго — что одноцветного \( Δ_> \) на плоскости нет. Это уже означает, что

но нетрудно указать и конкретный граф, обеспечивающий нижнюю оценку. Прикрепим к каждому из 52 шестиугольников в графе G по экземпляру H. При этом многие вершины совпадут, но это не должно нас беспокоить. Если не существует правильной раскраски графа в четыре цвета без учета их расположения на плоскости и отождествления вершин, то после отождествления ее тем более не будет. Полученный граф P на 20425 вершинах невозможно правильно раскрасить в четыре цвета.

Как и при переборе раскрасок H, выясняется, что большую часть вершин можно отбросить. Ди Грею удалось выделить из графа P подграф P′ на 1581 вершине, который также не красится в четыре цвета (рис. 16).

Рис. 16. Граф P′ на 1581 вершине. Не существует правильной раскраски P′ в четыре цвета

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

Литература
1. A. Soifer. The Mathematical Coloring Book. Springer, 2009.
2. А. Райгородский, О. Рубанов, В. Кошелев. Хроматические числа // Квант, 2008, №3.
3. А. М. Райгородский. Хроматические числа. М.: МЦНМО, 2015.
4. А. Я. Канель-Белов, В. А. Воронов, Д. Д. Черкашин. О хроматическом числе плоскости // Алгебра и анализ, 29:5 (2017), с. 68–89.
5. A. D. N. J. de Grey. The chromatic number of the plane is at least 5 // arXiv preprint arXiv:1804.02385 (2018).
6. M. J. H. Heule. Computing small unit-distance graphs with chromatic number 5 // arXiv preprint arXiv:1805.12181 (2018).
7. Проект Polymath.

1 На рисунке 4 розовым выделена часть границы, окрашиваемая в тот же цвет, что и сам квадрат. Черная часть границы получает цвет от соседних квадратов.

2 Специализированные алгоритмы и программы, предназначенные для решения задачи о выполнимости булевых формул — NP-полной задачи, к которой сводится в том числе и задача о раскраске графа в k цветов.

Читайте также: