2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Теореме красок – человечное доказательство!
Сообщение13.01.2008, 12:21 


13/01/08
2
Проблема четырёх красок выделяется из всех других математических задач невероятным сочетанием простоты формулировки с беспрецедентной сложностью решения. Оно было найдено лишь через столетие в 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 окрашиваются в разные цвета. Внешнее обрамление рассматривается как полноправная страна и окрашивается по общим правилам.
Додекаэдр – многогранник, имеющий только трёхрёберные узлы. Но любую карту или глобус можно без ущерба преобразовать в чисто трёхрёберную, поместив в многорёберный узел новую страну и расщепив такой узел на несколько трёхрёберных. Поэтому, раскрасить можно любую карту, достаточно лишь найти замкнутый маршрут, проходящий через каждый (трёхрёберный) узел ровно один раз.

 Профиль  
                  
 
 
Сообщение13.01.2008, 12:54 
Аватара пользователя


23/09/07
364
1)
Крупин С.Ю. писал(а):
Если концы ребра разнополярны (один плюс, другой минус), страны окрашиваются одинаково. Если же оба конца плюсы или оба минусы – окраска разных цветов.

Вы не приводите конкретной расскраски, а именно "если вокруг страны узлы с такими-то полярностями, то красим в такой-то цвет". Так что карту ваше доказательство "чисто конкретно" не расскрашивает. Ну это ещё ладно.
Но с чего Вы взяли, что при вашей расскраске не произойдёт какого-нибудь противоречия? Что, если мы расскрасим две каких-нибудь страны одинаковым цветом, а потом вдруг окажется, что они соединены ребром с однополярными концами?

2)
Крупин С.Ю. писал(а):
достаточно лишь найти замкнутый маршрут, проходящий через каждый (трёхрёберный) узел ровно один раз.

А почему он существует?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Someone


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group