Лабораторная работа 25. Np полные задачи

Концепция раскраски графов

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Впервые о хроматических многочленах было упомянуто в книге Бирхофа, Г. Д. и Левиса, Д. С. «Chromatic Polynomials» 1946 года.

На сегодняшний день уже получены хорошие результаты для оптимизации таких сложных комбинаторных задач, как задача составления расписания, классическая задача о раскраске карт, распределение регистров в микропроцессорах, распараллеливание численных методов, вычисление производных,
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета^[1]. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Раскраска вершин — главная задача раскраски графов, все остальные задачи в этой области могут быть сведены к ней. Например, раскраска рёбер графа — это раскраска вершин его рёберного графа, а раскраска областей планарного графа — это раскраска вершин его двойственного графа^[1]. Тем не менее, другие проблемы раскраски графов часто ставятся и решаются в изначальной постановке. Причина этого частично заключается в том, что это даёт лучшее представление о происходящем и более показательно, а частично из-за того, что некоторые задачи таким образом решать удобнее (например, раскраска рёбер).
Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования.
Первые результаты были получены для плоских графов в задаче раскрашивания карт. Пытаясь раскрасить карту округов Англии, Францис Гутри^[en] сформулировал проблему четырёх красок, отметив, что четырёх цветов достаточно, чтобы раскрасить карту так, чтобы любые два смежных региона имели разные цвета. Его брат передал вопрос своему учителю по математике, Огастесу де Моргану, который упомянул о нём в своем письме Уильяму Гамильтону в 1852 году. Артур Кэли поднял эту проблему на встрече Лондонского математического сообщества в 1878 году. В том же году Тэйтом было предложено первое решение этой задачи. Раскраску вершин первоначального графа он свел к раскраске рёбер двойственного графа и предположил, что эта задача всегда имеет решение^[2]. В 1880 году Альфред Кемпе^[en] опубликовал статью, в которой утверждалось, что ему удалось установить результат, и на десятилетие проблема четырёх цветов считалась решённой. За это достижение Кемпе был избран членом Лондонского Королевского общества и позже — президентом Лондонского математического сообщества^[3].
В 1890 году Хивуд^[en] нашёл ошибку в доказательстве Кемпе. В этой же статье он доказал теорему пяти красок^[en], показав, что любая плоская карта может быть раскрашена не более, чем пятью цветами. При этом он опирался на идеи Кемпе. В следующем столетии было разработано большое количество теорий в попытках уменьшить минимальное число цветов. Теорема четырёх красок была окончательно доказана в 1977 году учеными Кеннетом Аппелем^[en] и Вольфгангом Хакеном^[en] с использованием компьютерного перебора. Идея доказательства во многом опиралась на идеи Хивуда и Кемпе и игнорировала большинство промежуточных исследований^[4]. Доказательство теоремы четырёх красок является одним из первых доказательств, в которых был использован компьютер.
В 1912 году Джордж Дэвид Биркхоф предложил использовать для изучения задач раскраски хроматический многочлен, являющийся важной частью в алгебраической теории графов. Хроматический многочлен впоследствии был обобщён Уильямом Таттом (многочлен Татта). Кемпе в 1879 году уже обращал внимание на общий случай, когда граф не являлся плоским. Много результатов обобщений раскраски плоских графов на поверхности более высоких порядков появилось в начале 20 века.
В 1960 году Клод Бердж сформулировал гипотезу о совершенных графах, мотивированное понятием из теории информации, а именно нулевой ошибкой ёмкости графа, представленным Шенноном. Утверждение оставалось неподтвержденным на протяжении 40 лет, пока не было доказано как знаменитая строгая теорема о совершенных графах^[en] математиками Чудновской^[en], Робертсоном^[en], Сеймуром и Томасом в 2002 году.
Раскраска графов как алгоритмическая проблема начала изучаться с 1970-х годов: определение хроматического числа — входит в число 21 NP-полных задач Карпа (1972). И примерно в то же время были разработаны разнообразные алгоритмы на базе поиска с возвратом и рекурсивного удаления и стягивания Зыкова. С 1981 года раскраска графа применяется для распределения регистров в компиляторах.
Раскраска графа – это очень хорошо изученная задача. Известно, что это NP-полная задача для произвольных графов, так что (предполагая, что P != NP) можно не стремится находить эффективный алгоритм для раскрашивания произвольного графа. Для любого графа предполагается, что каждый узел может иметь любой цвет, однако должен отличаться от соседнего, затем идет назначение каждому узлу цвета и проверка правильности решения если решение не найдено, то происходит возврат в начальное положение системы и следующая попытка. Это, по сути, алгоритм перебора с возвратами (“backtracking” algorithm). Если ни одно предположение не оправдывается, тогда либо задача не решаема или предыдущее предположение неверно, так что нужно возвращаться на один шаг ранее. Алгоритм продолжает выполнение до тех, пока не перепробует все возможные варианты.
Именно эта особенность алгоритма потенциально дает экспоненциальное время выполнения. На реальных графах шаг, уменьшающий количество вариантов, быстро уменьшает множество возможностей, так что не приходится перебирать все возможные варианты, прежде чем найти решение или прийти к заключению, что решения не существует.
Для большинства типовых графов, следующий простой алгоритм вполне подходит. Начинается он с того, что предполагаем, что каждый узел может быть каждого возможного цвета. Затем:

1. 
   Если имеется один возможный цвет для каждого узла графа, то работа алгоритма успешно завершена!
   
2. 
   Если есть хотя бы один узел, которому не подходит ни один цвет, то работа алгоритма завершилась неудачно!
   
3. 
   В противном случае, должен быть узел, как минимум с двумя возможными цветами.
   
4. 
   У некоторых узлов может быть только один возможный цвет, тогда этот цвет нужно удалить из списка возможных цветов его соседних узлов.
   
5. 
   Эта операция может привести к тому, что у соседей может остаться только один единственный цвет. Если это так, то нужно удалить эти цвета из возможных цветов соседних узлов.
   
6. 
   И так далее; нужно продолжать уменьшать количество возможных вариантов до тех, пока это будет возможно.
   
7. 
   Если количество возможных цветов уменьшено, то либо получено решение, либо его вообще нет. Возврат к шагу 1.
   
8. 
   В противном случае количество возможных вариантов не уменьшено и есть узел с двумя или более возможными цветами. Выберем один возможный цвет для этого узла.
   
9. 
   Применяем рекурсию; если следующая итерация рекурсии приводит к успеху, то решение найдено. Если следующая итерация приводит к неудаче, тогда гипотетическое предположение не сработало.
   
10. 
    Если есть еще неопробованный гипотетический цвет для этого узла, возврат к шагу 8 и выбирается другой цвет.
    
11. 
    В противном случае ни один из вариантов для этого «неопределенного» узла не подходит; алгоритм завершился неудачно.
    

Для того чтобы построить подходящий алгоритм раскраски графов для решения какой-либо задачи, нужно:
1. Представить задачу в виде набора узлов неориентированного графа
2. Определить значения известных узлов
3. Определить соседние узлы или подгруппу узлов
4. Определить алгоритм раскраски, когда строим решение
Алгоритм, использующий метод Магу – Вейссмана.
Разработанный алгоритм работает на основе операций с матрицей смежности.