Comments 14
интересно, почему никто не расскажет об эффективном алгоритме раскраски карты в цвета которые не соприкасаются? Сколько цветов используется в таких алгоритмах? Это вроде гораздо интереснее чистой теории о пределах.
О пределах знать конечно полезно, но куда важнее знать алгоритмы которые действительно и эффективно работают.
Для раскраски в минимальное количество цветорв надо делать перебор с откатом. Реализовывать алгоритм из теореммы о 4 красках будет сложновато.
Какая-нибудь жадность может с большой вероятностью найти хорошую раскраску.
Если же подходит не самый оптимальный варинат, то можно весьма просто гарантировать 5 цветов, взяв школьное доказательство теоремы о 5 красках (или факт из статьи): Берем любую вершину v степени <= 5 (а она всегда есть), удаляем из графа, красим оставшейся граф рекурсивно. Добавляем вершину назад. если у нее было <= 4 соседей, или 5 соседей не все разного цвета, то тупо красим новую вершину каким-то допустимым цветом из 5. Иначе пусть цвета вдоль графа (в порядке обхода по углу) a,b,c,d,e. Тогда запустим обход в глубину от вершины цвета a чередуясь a-c. Если не дошли до соседа новой вершины цвета c, то можно всю обйденную компоненту перекрасить a<->с и освободить себе цвет a. если же дошли, то тогда точно так же можно обойти с вершины цвета b чередуя b-d или b-e, ведь путь v->a->..->c->v на плоскости отрезает вершину цвета b от вершин d, e.
Если граф планарен, но не нарисован на плоскости, т.е. мы не знаем обход по углу, то можно перебрать 10 пар цветов и попробовать перекрасить кадого соседа в каждый другой цвет. Если dfs не вернулся к новой вершине, то перекраска возможна. Фактически мы перебираем, в какой цвет красим новую вершину, и в какой цвет красим конфликтного соседа.
Это работает за O(n^2). Можно сделать даже не рекурсивно, сначала находим порядок добавления новых вершин, потом перекрашиваем. Dfs можно заменить на Bfs.
если оказывается что все достаточно просто с 5-ю цветами с точки зрения алгоритма, то возникает другой интересный практический вопрос:
а на сколько это сложнее иметь 5 красок вместо 4 , видимо с точки зрения материальных ресурсов / расходов на их поддержание/ ...?
То есть если алгоритм на 4-е краски существует, но он невероятно сложный (это ресурс времени фактически в первую очередь, видимо + электричество на вычисления, наверно), сколько стоит просто перейти на 5-ть красок, без учета этого ресурса времени?
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/map.html - игра про раскраску карты в 4 цвета (см. описание)
Какой бы ни была причина, математики снова и снова возвращаются к делу, которое формально уже считается закрытым.
Причина очень проста — избыток свободного времени и работа в которой платят не за результат, а за процесс.
Полученное математическое знание и есть результат.
Нет. Если бы решения не было, им бы всё равно заплатили.
насколько я понял решения которое можно использовать на практике так и нет! Есть какие-то инсинуации о том что:
Оказалось, что для правильного доказательства необходимо найти гораздо более крупный и сложный набор из 8900 конфигураций и показать, что каждая из них редуцируема. Сделать это вручную было невозможно. Нужны были компьютеры.
И это только для доказательства! Заметьте, ничего не говорится о том что это доказательство хотя бы теоретически можно было проверить! И я в общем не очень понял есть доказательство или нет или есть доказательство которое просчитывается на компьютерах и оно, наверно(!) все доказывает. Ну а о том чтобы использовать такой результат, который нельзя проверить, видимо речь вообще не идет, ну как я это понимаю.
Но платили возможно все таки за результат! Результат в виде: настоящим математикам с компьютерами верят на слово! Сказал доказал, значит доказал!
Но скорее всего на практике эта задача смысла не имеет, например потому, что кроме стран, в географии, есть еще океан, у которого цвет предопределен.
В том-то и прикол, в математике о практическом применении вообще, насколько я знаю, речи не идёт никогда.
То есть в математике как самостоятельной науке процесс выглядит примерно так: "уважаемый доктор наук, вот вам зарплата, вот вам задачка, будет прикольно если вы найдете решение".
я помню нам профессор математики на лекции говорил: Но вот Коши например, он примерно граф какой-то, он между балами вот теоремками баловался- математикой.
Или взять какого-нибудь Максвела, например, если почитать, тоже не простой чувак и родители у него не простые были. Простые работяги почему-то математикой не занимаются, не любят что ли математику?
Очень интересная у них там система мотивации я бы сказал, нам бы не мешало приглядеться, мне кажется. У них там как-то получается направить эту энергию в направлении пользы в прикладных задачах. А у нас все больше восхищаются задачами которые ни для чего не нужны и никакой практической ценности не представляют.
Мне кажется вы где-то в своём мире живёте. Никто так не делает, есть всяческие kpi, отчётность и прочее, всё как всех.
Теорема о четырёх красках получила новое редкое доказательство