5.9. Оптимальная раскраска вершин на графе
Раскраска географической карты
Задача о раскраске географической карты (рис. 5.21) состоит в том, чтобы определить, как нужно раскрасить карту, изображающую на плоской или сферической поверхности различные страны и границы между ними, если известно, что соседние страны нельзя закрашивать одним цветом.
Эту задачу математики пытались решить в течение почти 100 лет. Они пытались доказать результат, известный под названием задачи (или гипотезы) о четырех красках (гипотеза — теорема, являющаяся предположительно верной, практически подтверждаемая большим числом случаев, но не имеющая полного формального доказательства): “для раскраски карты на плоской или сферической поверхности достаточно четырех цветов”.
В 1976 г. эта теорема была доказана с помощью 
которая чисто комбинаторным способом проверила огромное число вариантов рисунков [Appel и Haken, 1976].
Первый этап исследования рассматриваемой задачи состоит в упрощении способа представления данных: задача сводится
Рис. 5.21. Фрагмент карты Европы.
к изучению несложного объекта, называемого неориентированным графом (как в задачах, рассмотренных в предыдущей главе). Для этого в каждой стране выделяется внутренняя точка (например, столица) и с помощью линий, которые назьн ваются ребрами, связываются все пары точек, принадлежащих соседним странам (рис. 5.22).
Рис. 5.22. Граф, эквивалентный карте, изображенной на рис. 5.21.
Тогда задача сводится к раскраске имеющихся на нашем рисунке точек (они называются вершинами), причем соблюдается следующее правило: две соединенные между собой вершины должны быть раскрашены в различные цвета. В этом виде задачу можно обобщить следующим
образом: пусть имеется произвольный граф, т. е. множество вершин и множество ребер, связывающих эти вершины попарно. Нужно найти наименьшее число цветов, с помощью которых можно его раскрасить, соблюдая то же правило: две связанные между собой вершины должны быть раскрашены в различные цвета. Здесь (в отличие от предыдущего случая) граф не обязательно является плоским. Это означает, что необязательно существует такое изображение данного графа на плоскости, при котором никакие два ребра не пересекаются.
Именно в таком виде эта задача возникает в самых разных ситуациях (некоторые из них описаны ниже).
5.9.1. Организация конференции
Для установления порядка заседаний секретариат попросил всех участников составить список секционных заседаний, в которых они хотели бы участвовать. Подмножество секционных заседаний с участием того или иного человека должно быть разбито на взаимно не пересекающиеся во времени части.
Рис. 5.23. Граф задачи об организации конференции.
Пример. Пусть планируется 9 секционных заседаний, обозначенных буквами 
каждое из них длится полдня. Мы располагаем необходимым числом аудиторий.
Несовместимость заседаний во времени задается списком соответствующих подмножеств: 
(существует по крайней мере один человек, который хочет участвовать в работе всех секций, входящих в одно и то же подмножество).
Данная задача сводится непосредственно к задаче раскраски графа: заседания секций соответствуют вершинам графа, а несовместимость их во времени — ребрам (рис. 5.23). Итак, задача секретариата — организовать конференцию так, чтобы она длилась минимальное число дней (в день проходят два заседания — утреннее и вечернее).
