Теорема четырех красок
Простое доказательство теоремы четырех красок.
-----------------------------------------------
Определения:
0) Областью называется часть плоскости, ограниченная замкнутой кривой без пересечения последней самой себя.
1) Границей двух областей является часть кривой, принадлежащая им обоим , при этом не являющаяся точкой.
2) Группой областей называется множество областей на плоскости, каждая из которых имеет границу хотя бы с одной другой областью из этого множества.
3) Тесной группой областей размерности N называется группа областей, каждая из которых граничит с N-1 остальными областями
------------------------------------------------
Лемма ( о невозможности существования тесной группы размерности 5 на плоскости)
1. На плоскости возможно существование тесной группы размерности 4.
2. Из определения тесной группы размерности 5 следует, что каждая область в этой группе одновременно входит в тесную группу размерности 4 ( из того, что каждая область граничит с каждой из 4 оставшихся областей следует, что каждая область граничит с каждой из трех любых областей в этой группе)
3. Создание тесной группы размерности 5 возможно только добавлением одной и только одной кривой без самопересечения ( в противном случае образуется больше пяти областей, из которых по крайней мере одна из них не входит в тесную группу размерности 5, и следовательно - исключается из доказательства)
4. Добавление кривой к существующим областям на плоскости возможно в следующих вариантах:
5. Количество внутренних границ между областями в тесной группе очевидно равно (N-1)*N/2 ( коэффициент 2 означает, что граница области А с областью Б - та же самая, что граница области Б с областью А)
Для тесной группы размерности 4 это 6 общих внутренних границ (3*4/2) , для тесной группы размерностью 5 - это 10 общих границ (4*5/2).
6. Из п.4 следует , что при образовании новой тесной группы размерности 5 возможно максимум 3 новых границы. То есть в получившейся группе должно быть 9 внутренних границ. В то время как по определению, в тесной группе размерности 5 должно быть 10 внутренних границ.
Таким образом, мы пришли к выводу, что невозможно существование на плоскости тесной группы размерности 5.
-----------------------------------------------------
Теорема 4 красок.
Для любой карты на плоскости достаточно 4 красок для раскрашивания ее таким образом, чтобы каждая область граничила с областью другого цвета.
Доказательство.
Примем, что существует какая-либо карта на плоскости, которая требует для своего раскрашивания по указанному условию 5 красок. Это означает, что при любом варианте раскрашивания этой карты существует по крайней мере одна область, для которой необходима 5 краска, то есть она граничит минимум с четырьмя областями, каждая из которых окрашена в иной цвет.
1. Очевидно, что каждая из этих областей в данном варианте раскраски необходима окрашена именно в этот цвет. В противном случае одна из этих областей могла быть окрашена в другой цвет, и тогда исходная область не нуждается в 5-й краске.
2. Очевидно, что тезис 2 справедлив для всех вариантов раскрашивания карты.
3. Поскольку 5 краску мы выбрали произвольно, «пятой краской» мы можем назвать любую краску из пяти. Соответственно для любой из минимум четырех областей, соседствующих с областью, которая необходимо окрашена в пятый цвет, справедливы рассуждения, справедливые для этой области. То есть, каждая из этих областей необходимо окрашена в свой цвет, поскольку граничит минимум с четырьмя другими областями, каждая из которых необходимо окрашена в свой цвет. Отсюда вывод.
4. Каждая из областей карты на плоскости, которая необходимо окрашена в свой цвет, граничит минимум с четырьмя другими областями, каждая из которых необходимо окрашена в своей цвет.
5. Примем, что на карте существует N областей , необходимо окрашенных в свой цвет при конкретном варианте раскрашивания.
6. Из пункта 4 следует, что в то же время на той же карте должно быть минимум N+4N областей , необходимо окрашенных в свой цвет при конкретном варианте раскрашивания.
7.Это возможно в одном единственном случае. Если все эти области образуют тесные группы размерности не меньше 5, существование которых на плоскости опровергнуто в лемме. (существование тесных групп размерности большей, чем 5, на плоскости невозможно без существования тесных групп размерности 5)
Следовательно, исходное предположение о существовании на плоскости карты, для окрашивания которой необходимо не менее 5 красок - неверное.
Теорема доказана.
Следствия.
А. Доказательство справедливо для бесконечных карт, исключая фрактальные и карт областей бесконечно малого размера.
Б. Алгоритм раскрашивания любой карты на плоскости 4мя красками.
1. Случайная область раскрашивается в цвет n.
Переход на следующую по часовой стрелке область
2. Любая соседняя область раскрашивается в цвет n+1.
3. Область , соседняя с двумя областями , окрашивается в цвет mod((n(1)+n(2))/4) (то есть цвет, равный остатку от деления суммы соседних областей на 4) , если n(2)=n(1)+1 или n(1)=n(2)+1 . В противном случае она окрашивается в цвет mod(|n(1)-n(2)|/4)
4. Если существует область , соседняя с областями 1,2 и 3, она окрашивается в оставшийся цвет 4.
5. См. 1.