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

Карты и цвета

Большинство географических карт можно интерпретировать как графы, вершинами которых являются точки, где сходятся три линии и более, а ребрами — границы стран и территорий. Составители карт пытались раскрасить их так, чтобы разные страны и территории были окрашены в разные цвета. Учитывая число стран и ограниченное количество цветов, которые использовались при цветной печати, требовалось раскрасить карты так, чтобы в разные цвета были окрашены только страны с общими границами. Естественно, возник вопрос: какое минимальное число цветов необходимо, чтобы все страны с общими границами были окрашены в разные цвета? (Подразумевается, что точка не является границей.) Так как существует множество различных карт (карты стран, регионов, промышленных районов и так далее), то очевидно, что задачу нужно сформулировать в общем виде с помощью графов. Иными словами, нужно рассматривать карты, описывающие произвольный плоский граф.

Сначала обратимся к следующим фигурам. Для раскраски каждой из них в соответствии с заданными правилами требуется 1, 2, 3 и 4 цвета соответственно.

Заметим, что если мы также захотим раскрасить и внешнюю область, то нам понадобится соответственно 2, 3, 4 и… снова 4 цвета.

Следующие фигуры более сложны.

Сразу же становится понятно, что для их раскраски достаточно четырех цветов.

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