Для решения этой задачи обратимся к помощи компьютера. Тут нас подстерегают трудности: большинство ЭВМ лишено зрения, поэтому они не могут посмотреть на карту; к счастью, им нужно знать лишь, какие регионы являются соседями, т. е. смежны друг другу. Размер и форма регионов не влияют на раскраску, важно лишь наличие нетривиальных контактов между ними. Для представления отношения смежности полезно воспользоваться неориентированным графом.
Неориентированный граф состоит из конечного множества вершин и конечного множества ребер, связывающих вершины. Любые две вершины связаны не более чем одним ребром; не должно быть двух дублирующих друг друга ребер; кроме того, для рассматриваемой задачи мы запрещаем ребру связывать вершину с самой собой. На рис. 3.1 изображен неориентированный граф, представляющий первые 49 американских штатов. Ввести граф в ЭВМ несложно: достаточно перечислить все вершины, сопроводив каждую списком смежных ей вершин. Граф может не иметь вершин, а значит, и ребер; такой граф называется пустым. Вершина может быть изолированной, если нет ребер, связывающих ее с другими вершинами (примером тому могли бы служить Аляска и Гавайи); точно так же две части графа окажутся изолированными друг от друга, если нет ребер, их связывающих. Аналогия между картами и неориентированными графами столь тесна, что мы будем использовать эти понятия как равнозначные. Ну, а польза, приносимая графами, столь велика, что всем программистам следует иметь представление об их основных свойствах.
Рисунок 3.1. Топологическая карта Соединенных Штатов. Для нее достаточно четырех цветов. (WA — Вашингтон, OR — Орегон, CA — Калифорния, NV — Невада, ID — Айдахо, UT — Юта, AZ — Аризона, МТ — Монтана, WY — Вайоминг, СО — Колорадо, NM — Нью-Мексико, ND — Северная Дакота, SD — Южная Дакота, NE — Небраска, КА — Канзас, ОК — Оклахома, ТХ — Техас, MN — Миннесота, IA — Айова, МО — Миссури, AR — Арканзас, LA — Луизиана, WI — Висконсин, IL — Иллинойс, IN — Индиана, MS — Миссисипи, AL — Алабама, Ml — Мичиган, ОН — Огайо, KY — Кентукки, TN — Теннесси, GA — Джорджия, FL — Флорида, РА — Пенсильвания, WV — Западная Виргиния, VA — Виргиния, NC — Северная Каролина, SC — Южная Каролина, NY — Нью-Йорк, NJ — Нью-Джерси, DE — Делавэр, MD — Мэриленд, DC — округ Колумбия, VT — Вермонт, МА — Массачусетс, СТ — Коннектикут, WE — Мэн, NH — Нью-Гэмпшир, RI — Род-Айленд.)
Тема. Напишите программу, раскрашивающую карту в минимальное число цветов. Исходными данными служит список регионов с указанием соседей каждого региона. Результатом должен быть список регионов с приписанными им цветами и общее число использованных цветов. Обычно проще всего для обозначения регионов и цветов применить положительные числа, но куда приятнее (и полезнее для отладки), если допускается ввод более привычных названий. Исходные данные должны проверяться на непротиворечивость; выявляйте нелепые номера вершин и связанные с собой вершины. Постарайтесь сделать программу по возможности эффективной, иначе раскраска тяжелых случаев окажется для вас слишком дорогим удовольствием.
Указания исполнителю. Исходная карта не обязана быть планарной. В самом деле, вполне допустимыми крайними случаями служат карты, в которых любые два региона — соседи, и карты, в которых никакие два региона не являются соседями. Последний случай соответствует раскраске множества раздельных шаров, когда достаточно только одного цвета. Проверка планарности — важная тема информатики, ей посвящено немало статей. Возможно, вас заинтересует проверка гипотезы о четырех красках, утверждающей, что для любой планарной карты требуется не более четырех красок. Если вам удастся подтвердить или опровергнуть ее, вы сделаете себе имя[7].
Из ресурсов, требуемых данной задачей, самый важный — время. Конечно, нет смысла перебирать все возможные решения, поскольку их число быстро увеличивается с ростом числа регионов, а доля правильных решений (даже если таковых несколько) мала. Лучше воспользоваться методом перебора с возвратами. Начните с выбора некоторого региона и приписывания ему цвета. В дальнейшем переходите к соседнему нераскрашенному региону и пытайтесь приписать ему какой-нибудь из использованных цветов, совместимый с уже сделанной раскраской. (Может случиться, что раскрашивать больше нечего, тогда задача решена. Возможен и случай, когда не осталось нераскрашенных регионов, соседних с раскрашенными, т. е. попалась несвязная карта.) Если в некоторый момент новый регион не удается раскрасить, отступайте от уже раскрашенных регионов (в соответствии с порядком раскраски) до тех пор, пока не найдется регион, цвет которого можно изменить. Раскрасьте его в цвет, которого он ранее не имел, и снова продвигайтесь вперед. Если при отступлении вы возвратились в регион, раскрашенный первым, добавьте к своей палитре новый цвет и начните сначала.
7
Теперь это замечание имеет лишь исторический интерес. Разъяснение вы найдете в литературе к гл. 29.