Comments 30
Ну то была конкретная карта графвтв Англии.
Не любая карта, конечно же.
Не только четыре одновременно граничащих государства требуют 4 цвета. Любое государство, окружённое нечётным числом других, приведёт к использованию 4 цветов (потому что при попытке раскрасить в 3 цвета получилось бы 232323...32 - нестыковка начала и конца).
Кроме того, вы не доказали исходную задачу, а лишь задачу "одно государство, окружённое другими". Потому что у вас нет доказательства того, что при описанной вами стратегии не возникнет противоречия между раскрасками дальних соседей.
Чудесно! Автору предлагаю также заняться поиском простого доказательства теоремы Ферма и построением вечного двигателя. А то ученые-моченые чего-то там мудрят все время.
Есть нюанс. На самом деле, задача заключается в том, чтобы доказать, что четырёх (или пяти) красок достаточно для раскраски любой (контурной) карты. При этом, нет требования, чтобы каждым цветом закрашивалась только одна область. Есть только требование того, чтобы области имеющие общую границу закрашивались разными цветами. Здесь есть небольшая вина Мартина Гарднера, как популяризатора задачи. В своём рассказе "Остров пяти красок", он не утрудил себя правильной формулировкой задачи.
Нормальная там формулировка. Во всяком случае, в том переводе, по которому только что проверял.
Согласен, я сам немного не точно сформулировал. Формулировка проблемы нормальная (прямо в третьем абзаце рассказа), но дальше он уже раскрашивает не любую, а вполне конкретную карту стран, расположенных на острове, причём, поскольку это именно страны, каждая из них представляет собой регион, состоящий из одного куска, что немного вводит читателя в заблуждение, относительно самой задачи (меня во всяком случае ввело, когда я это читал в первый раз).
В этом случае ее можно раскрасить цветом той страны, с которой она не граничит - т.е. новый цвет не нужен.
В комментарии показано, что это не так.
По сути имеем не одну проблему, а две:
1. Доказать, что для раскраски любой карты четырех цветов достаточно.
2. Разработать алгоритм последовательной раскраски областей — определить критерии выбора следующей раскрашиваемой области и ее цвета, не приводящие в сколь угодно дальней перспективе к противоречию п.1.
Дело даже хуже: невозможно разработать алгоритм последовательной раскраски областей, картину нужно рассматривать полностью, в совокупности.
Возвращаясь к тому моему примеру, на который Вы сослались.
Предположим, что на 12-м шаге областью стало не кольцо, а тоже кусочек.
Тогда с построением всё нормально.
Теперь перекрасим так, как я предложил, чтобы не было проблем на 12-м шаге с закраской кольца.
На 12-м кольцевом шаге проблем не будет, да.
Но зато если на 12-м шаге областью станет не кольцо, а кусочек, на 15-м шаге опять возникнет проблема.
Таким образом, последовательно раскрашивать, не зная, что будет дальше, невозможно. Нужна вся картина сразу.
Пропустил 13 (хотя вроде как я не суеверный!) - после 12 у меня сразу идёт 14, ну да надеюсь, всё равно понятно.
Раз уж пишу комментарий, то добавлю, что в последнем варианте нам не поможет и другой выбор цвета на 12-м ходу: если выбрать вместо синего красный, то на 14-м (который должен был быть обозначен как 13-й) придётся выбрать синий, и на 15-м всё равно возникает проблема.
(Ну и за техническое качество иллюстраций снова прошу извинить, надеюсь, что ни у кого глаза не вытекли.)
Я бы вообще предложил бы красить не в цвета, а в «возможности». То есть, хранить для каждой области дозволительные варианты раскраски. И тогда связи между областями будут «в случае такой раскраски соседних областей остаются такие варианты для этой». Но под «раскраской соседних» здесь понимается комбинация соседних «цветов», поэтому различающихся вариантов раскраски областей может быть больше четырёх, один цвет области при разных ограничениях это разные «цвета». Могут быть такие комбинации соседних цветов, что варианта для области не останется. Но этот вариант исключается из рассмотрения, а теория о раскраске говорит, что исключать такое можно спокойно, меньше одного варианта для всей карты не останется.
Если алгоритм существует, то не обязательно одно и то же состояние «До» будет достигнуто для разных модификаций карты. Т.е. алгоритм как раз не обязан рассматривать только близлежащие окрестности уже закрашенных областей. Возможно, он должен перебирать всевозможные последовательности закраски от закрашенного участка к «краям», отсекая по какому-то критерию бесперспективные или рискованные. А потом, осуществляя рекурсивный возврат получать набор допустимых цветов для одной из областей, граничащей с закрашенными.
Эээ... Это, типа, доказательство? Или что это?
Но — хороший повод выложить свой написанный фрагмент.
Теорема о четырёх красках.
Существует довольно простое предположение, что после разделения плоскости на области, такого чтобы в углах они встречались не больше чем по трое, эти области можно раскрасить так, чтобы соседи не были раскрашены одинаково. И что хватит четырёх красок. Так как плоскость в топологии аналогична поверхности шара, доказать что не хватит трёх красок легко: спроецировать на сферу тетраэдр — и вот вам четыре участка, каждый соседствует один с другим, четыре цвета обязательны. Но хватит ли четыре цвета для всех видов разделения? Ведь тогда любое разделение можно спроецировать обратно на тетраэдр.
Предположим, что у меня есть задача доказать теорему. Я бы начал с описания нарушающего случая. У нас будет область, которая имеет как минимум четыре соседа, таких, которые обязательно различаются между собой. На графике, отражающем линии, проводящие эту недопустимость сходства лежат так, что у них обязательно есть пересечение. Это можно отметить для исследования. Если бы был способ передавать соседство на расстояния, то либо его нельзя представить линией передачи, либо задача сводится к самой себе: доказать что невозможно две таких передачи пересечь.
Рассмотрим дальнюю передачу соседства, в некотором виде оно возможно. Это можно сделать через обязательное совпадение первой областей и соседней ко второй, тут без такого соседа ко второй не обойтись. В свою очередь дальней передачи цвета можно достичь, если сделать так, чтобы между этими областями были расставлены все посредники, количество которых на единицу меньше количества используемых красок. В данном случае, получается, три, хотя к этому количеству уже могут быть вопросы, ведь количество красок у нас четыре условно. Но тут появляется кое-что ещё: принципиальная необходимость того, что эти трое цветов соединились в опоясывающий контур, иначе два цвета будут разделены между собой третьим и появляется возможность сменить цвет одной области на повторяющий. А не допустить смены цвета можно только если как-то другим способом передать соседство. А что это за другой способ? Разве такой есть?
Итак, опосредованно соседство не передать, либо способ неизвестен, а непосредственное соседство сводит задачу к ней же самой. И здесь ситуация, в которой, как говорится, предполагаемое либо не получится, либо одно из двух.
Не смотря на незаконченность, это может выглядеть как перспективный черновик на доказательство. Развивать можно, уточняя определения и схемы проверки. Но уже здесь кое что упущено. По логике, само существование десятого запрета в группе пяти областей, обязательно создающего пересечение, вовсе не обязательно. Достаточно того, что расставленные цвета действительно различаются, а запрет может быть симулирован через запрет менять цвета. Запрет одинакового соседства и запрет смены цвета как невозможность перерасстановки при соблюдения первого запрета — могут быть разными запретами. В случае если доказываемая теорема не верна.
Мы не избавились от необходимости в полноте и точности закончить доказательство, ничего не доказано. Похоже, теперь — нужно разобраться в том, почему поменять цвета в случае завершённой расстановки будет невозможно. Только, изначально доказываемая теорема предполагает о том что это возможно. Так что, очень сложно рассмотреть этот запрет — рассмотреть то, что предположительно не существует. Теорема оказалось действительно сложна в доказательстве, как за неё не возьмись — она выглядит как «а почему бы и нет».
***
Даже это — то что я написал — не сообщает о доказательстве ничего. Некоторые утверждения при дальнейшем разборе наверняка окажутся не точны, не верны. Но это лучше чем: «смотрите, схема в которой хватает четырёх цветов существует, я математег.»
Не знаю, возможно ли простое доказательство, но оно — не на столько простое.
Так как плоскость в топологии аналогична поверхности шара
Это не так. Чтобы сфера стала гомеоморфна плоскости, нужно из сферы выколоть одну точку. После этого пример с тетраэдром перестаёт быть очевидной иллюстрацией, вообще говоря.
Вообще, даже интересно заметить, что есть две крайности: автор топика, который говорит «всё просто, верьте мне», и верит сам. И вы, «всё сложно, верьте мне». А может в это не стоит верить? Вы запутали не только лишь себя.
Плоскость в топологии всё же не аналогична сфере, поэтому я обоснованно усомнился в ваших дальнейших рассуждениях.
И вы, «всё сложно, верьте мне». А может в это не стоит верить?
Я такого не говорил. Я сказал, что всё не так очевидно.
и вопрос гомеоморфности сферы и плоскости никак не связаны,
Это многие вопросы сразу убирает.
Не уверен, потому что если точку не выкалывать, вся дальнейшая модель кажется забывает о существовании бесконечной грани. Возможно, это не так, с учётом вашего замечания о независимости заполнения от выколотых точек.
Вашему черновику доказательства я пока не верю, потому что вы начали с ложного утверждения – так не принято даже в целях упрощения – но точно посмотрю внимательней, интуиции мне здесь не хватает.
Спасибо за аргументированное возражение.
Ок, для укладки планарного графа сфера и плоскость – действительно одно и то же, это элементарно доказывается, в одно соображение, я просто затупил. Считайте мой коммент просто уточнением вашей формулировки.
Коварство задач на доказательство в том, что правильность доказательства тоже еще доказать надо
Теорему доказали, прогнав через компьютер полторы тысячи конфигураций карт, с претензией на существование контрпримера. Но некоторых такое доказательство не убедило, как из-за привлечения компьютера, так и из-за метода подбора карт-кандидатов. Поэтому теорему периодически доказывают (вернее – проверяют) снова и снова. Правда, меняется только мощность компьютеров и эффективность алгоритмов, но суть доказательства остаётся похожей. Кое-кто решил зайти через снарки, но пока, вроде, строгого доказательства нет.
Когда читал это "конструктивное доказательство", ожидал, что в конце будет написано что-то в духе "Но конечно же, всё не так просто. Рассмотрим, что не так с этим как бы доказательством..." Увы, не дождался.
Проблема в том, что в этой статье не показан индуктивный переход, не доказано, что проблем не возникнет и дальше, при усложнении картины.
В качестве примера покажу картинку, которая строилась по неявно предполагаемому в статье конструктивному алгоритму, и в которой на 12-м шаге невозможно выбрать цвет:
Разумеется, эту картинку можно перекрасить так, чтобы проблемы не было: если на 4-м ходу вместо красного закрасить зелёным, на 5-м - красным, на 11-м - зелёным, то на 12-м ходу можно закрасить красным.
Но в статье не предлагается выбор цветов и не доказывается, что он корректный.
И, вообще говоря, Стивен Барр игру такую придумал - "четыре краски" для двух игроков. Первый игрок рисует пустую область, второй её закрашивает одним из цветов и добавляет свою пустую область. Первый игрок также закрашивает её одним из четырёх цветов и в свою очередь рисует пустую область. Выигрывает тот, кто нарисовал пустую область, граничащую со всеми четыремя цветами.
У меня было простое профанное доказательство: представим, что нашлась карта, для которой недостаточно четырех красок. Тогда в ней есть такое место, где каждая страна граничит с четырьмя странами другого цвета. Получился полный K5 граф, который по теореме Понтрягина не планарен, то есть не вложим в плоскость без пересечения ребер, то есть противоречие.
Нужна поправка: "государства на карте" могут иметь анклавы и эксклавы, а это резко усложнит раскрашивание (возможно даже, сделает невозсможным)
Теорема о четырех красках