Раскраска карт

§3. Раскраска карт

Интересны задачи о раскраске карт. Пусть на плоскости задана некоторая географическая карта.

Определение. Будем говорить, что карта правильно раскрашена, если любая ее страна раскрашена определенной краской, причем любые ее две страны, имеющие между собой общую границу, закрашены в разные цвета.

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

Пример 3.1. Для раскраски следующих карт нужно:

2 цвета 3 цвета 4 цвета

До сих пор не найдено ни одной карты, которую не удалось бы правильно раскрасить четырьмя красками. Впервые на это обстоятельство обратил внимание немецкий математик Мебиус более ста лет назад. С тех пор многие крупные ученые пытались решить эту проблему четырех красок. То есть пытались либо доказать, что четырех красок достаточно для раскраски любой карты, либо найти пример карты, которую нельзя раскрасить четырьмя красками. Однако до сих пор этого никому не удалось сделать. Установлено, что для правильной раскраски любой карты достаточно пяти красок.

Любопытно, что для некоторых поверхностей, устроенных, казалось бы, более сложно, чем плоскость, проблема раскраски карт решена полностью. Так, например, доказано, что на поверхности тора (“баранки”) для правильной

раскраски любой карты достаточно семи красок. Причем существуют карты, которые нельзя правильно раскрасить 6 красками.

Пример 3.2. Пусть прямоугольник разбит на части n прямыми. Тогда его можно так закрасить черной и белой красками, что каждые две части, имеющие общую сторону, будут окрашены в разные цвета.

Доказательство. При n = 1 имеем:

Теорема 2. Пусть дано, что утверждение верно при n=k. Тогда оно верно при

n = k + 1.

При n = k + 1 нужно раскрасить конфигурацию, образованную k прямыми из данных k + 1 прямых следующим образом:

(k+1) прямая

Затем перекрасить всё, что лежит с одной из сторон оставшейся (k+1) прямой в противоположный цвет.

(k+1) прямая

Теорема 2 доказана.

Из доказанной теоремы 1 и теоремы 2 следует, что утверждение верно при любом натуральном n .

Пример 3.3. На плоскости дано n ³ 2 окружностей. Доказать, что при любом расположении этих окружностей образуемую ими карту можно правильно раскрасить двумя красками.

Доказательство. При n = 2 имеем при всевозможных положениях окружностей следующие рисунки:

Теорема 2. Пусть дано, что утверждение верно при n = k ³ 2. Тогда это утверждение верно при n = k +1. Пусть на плоскости заданы k + 1 окружностей.

Теорема 2 доказана. Из доказанной теоремы 1 и теоремы 2 следует справедливость утверждения при любом натуральном n ³ 2 .

Литература. Содержание