|
Проблема четырёх красок выделяется из всех других математических задач невероятным сочетанием простоты формулировки с беспрецедентной сложностью решения. Оно было найдено лишь через столетие в 1975 г, и то не человеком, а компьютером. В результате «топорного» перебора невероятного числа вариантов комп вынес вердикт: Да, любую карту или глобус можно раскрасить всего четырьмя красками, так, чтобы никакие две одноцветные страны не соприкасались линиями границ (хотя соприкосновение в узловых точках допустимо).
Однако, формально закрыв проблему, это доказательство не вскрыло всей подоплёки проблемы. И «простому» человеку остаётся лишь верить узкопрофессиональным специалистам в решённости проблемы.
Мною было найдено «настоящее», «человеческое» решение, доступное пониманию дикаря-людоеда. Оно не только доказывает возможность раскраски, но и конкретно раскрашивает карту.
В качестве примера рассмотрим раскраску додекаэдра. Обратимся к книге Харари Ф. «Теория графов» 1973г. На стр. 16 имеется рисунок додекаэдра и на нём замкнутый маршрут, проходящий через каждый узел ровно по одному разу. Раскрасим додекаэдр по двухэтапной методике:
1-й этап: Маркировка. Поставим в 1-м кружке, скажем плюс и запомним, что в первом узле (движение 20-1-2) делается левый поворот.
Далее, входя в узел 2, отметим, что поворот в нём, наоборот, правый. В таком случае маркируем узел 2 тем же плюсом. Поворот 3, в противоположность предыдущему 2-му, левый. Маркируем 3 также, как и 2 плюсом. В узле 4 поворот противоположный – правый, следовательно, знак сохраняется – опять плюс. Далее, в узле 5 поворот совпадает с 4-м (оба правые). Меняем знак, ставим в узле 5 минус. В узле 6 опять правый поворот (как и в 5) – знак снова меняем – опять плюс.
Пройдя все узлы, получим минусы в узлах 5,8,15,18 и плюсы в остальных. Маркировка окончена.
2-й этап: Раскраска. Естественно, страны, граничащие по ребру, окрашиваются разноцветно по самому условию проблемы. Но ребро не только является границей двух стран, но и упирается концами ещё в две страны. Они раскрашиваются по следующему правилу: Если концы ребра разнополярны (один плюс, другой минус), страны окрашиваются одинаково. Если же оба конца плюсы или оба минусы – окраска разных цветов.
Например, ребро 4-5 разнополярно. Значит, страны, ограниченные узлами 2-3-4-14-15 и 5-6-10-11-12 окрашиваются одинаковым цветом. Страны же 3-4-5-6-7 и 1-2-15-16-20, соединённые однополярным ребром 2-3 окрашиваются в разные цвета. Внешнее обрамление рассматривается как полноправная страна и окрашивается по общим правилам.
Додекаэдр – многогранник, имеющий только трёхрёберные узлы. Но любую карту или глобус можно без ущерба преобразовать в чисто трёхрёберную, поместив в многорёберный узел новую страну и расщепив такой узел на несколько трёхрёберных. Поэтому, раскрасить можно любую карту, достаточно лишь найти замкнутый маршрут, проходящий через каждый (трёхрёберный) узел ровно один раз.
|
