Этюды для программистов

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

Для решения этой задачи обратимся к помощи компьютера. Тут нас подстерегают трудности: большинство ЭВМ лишено зрения, поэтому они не могут посмотреть на карту; к счастью, им нужно знать лишь, какие регионы являются соседями, т. е. смежны друг другу. Размер и форма регионов не влияют на раскраску, важно лишь наличие нетривиальных контактов между ними. Для представления отношения смежности полезно воспользоваться неориентированным графом.

Неориентированный граф состоит из конечного множества вершин и конечного множества ребер, связывающих вершины. Любые две вершины связаны не более чем одним ребром; не должно быть двух дублирующих друг друга ребер; кроме того, для рассматриваемой задачи мы запрещаем ребру связывать вершину с самой собой. На рис. 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 — Род-Айленд.)

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