Проблема 4-краски простой подход

[iig]

Эта проблеме давно решена, но так же неэффективно, как и ВТФ.
Пока мне известно, что для этого понадобилось перебрать почти 2000 вариантов на ЭВМ в 1970-х.
Я предлагаю более простой вариант.
Страны, которые имеют границы с четными соседями, будем называть четными, и, соответственно, других нечетными.
Все четные можно раскрасить в два цвета типа шахматной доски.
Все нечетные можно попарно соединить между собой на планарной поверхности.
Последнее предложение мне не удалось доказать, поэтому кто сделает, тому и карты в руки, но не забудьте меня упомянуть и проставить за подсказку.
Советую использовать способ определения планарности - ножницами на две части.
Этот способ также предполагает конструктивный метод раскраски.

[Xaositect]

iig в сообщении #314479 писал(а):

Страны, которые имеют границы с четными соседями, будем называть четными, и, соответственно, других нечетными.

Поясните подробнее, у Вас тут какая-то рекурсия.

[iig]

Что тут пояснять, у которых стран четное число соседей, можно раскрасить в два цвета, это будет понятно, если почитать в литературе.
А вот с нечетными придется обьединяться в союзники, уже других цветов между собой.
В общем, политика...
p.S. Может, немного неправильно выразился, но точно помню, что четных можно раскрасить в два цвета, а между ними еще в два.
[1]Саркисян А.А. и Колягин Ю.М.
С20 Познакомтесь с топологией. М.,1976
стр. 53

[Xaositect]

iig в сообщении #314493 писал(а):

Что тут пояснять, у которых стран четное число соседей, можно раскрасить в два цвета, это будет понятно, если почитать в литературе.
А вот с нечетными придется обьединяться в союзники, уже других цветов между собой.

На этой карте у каждой страны 2 соседа, т.е. все три страны четные:

Раскрасьте ее, пожалуйста, в два цвета.

[iig]

Наверное, вы не поняли смысла темы - тут двое, которые союзники, должны другого мочить.
Между собой цветами тоже могут различаться, но другим от этого не легче.
P.S. Хочу уточнить - четными странами называю тех, которые имеют четное число соседей или границ.

-- 30 апр 2010, 22:24 --

iig в сообщении #314479 писал(а):

.
Страны, которые имеют границы с четными соседями, будем называть четными, и, соответственно, других нечетными.

Прошу прощения, тут я понял, что неправильно выразился.

[sceptic]

Объясните, пожалуйста, что вы имеете ввиду. Я понял ваше утверждение так же, как и Xaositect (и тоже приготовил карту-контпример, отличную от примера Xaositect'a).

[iig]

Я неправильно выразился в первом посте, исправить уже не могу.
В общем, страны можно разделить на два лагеря, типа хороших и не очень, например, как раньше, коммунисты и капиталисты.
Внутри них тоже было различие - левые и правые, либералы и консерваторы.
Сначала надо разделить союзников, а между собой потом пусть разбираются.
Союзники разделяются по четности - каждую карту с четными странами можно раскрасить в два цвета. Тут могут быть вопросы, но можно свести к простому варианту. Если есть нечетные страны, они попарно соединяются через четных друг с другом и образуют одну четную, а там внутри себя разбираются, так что получаются две группировки со своими проблемами и всего получается четыре цвета типа СССР с Китаем вроде коммунисты, но воевали, да и у америкосов тоже были проблемы.
!Главное - доказать, что на планете всегда можно нечетные страны связать попарно, включая в свой блок четные, если надо, и привязать к блокам, а потом эти блоки раскрасить внутри в два цвета каждый.
Кстати, опять напоминаю, что критерием планарности является разрезание по границам на две не связанные части.

[Circiter]

2iig
А не могли бы вы попробовать выразиться на языке теории графов?

То есть, пусть странам сопоставляются вершины графа; при этом вершины, соответствующие странам-соседям соединяются ребрами. Вершины действительно можно поделить на два класса -- на четные (из которых выходит четное количество ребер) и нечетные.

Что с этим делать дальше? Даже под четностью/нечетностью вы что-то свое имеете ввиду... :)

Вот, например, переформулируйте пожалуйста следующее ваше утверждение, чтобы оно работало для графа:

Цитата:

каждую карту с четными странами можно раскрасить в два цвета.

P.S.: Хадвигер вроде-бы предлагал нечто подобное, мол $n$-хроматический граф должен быть стягиваем к полному $n$-вершиннику $K_n$, причем эта гипотеза (для произвольного $n$) недоказана до сих пор.

[iig]

Можно было бы выразить более точно на языке теории графов, но для этого мне надо на неделю отвлечься, может и найду время.
Вы уж извините, я выдал только идею, если бы доделал, не стал бы излагать на форуме,а послал в журнал.
Если кто использует и докончит, пусть упомянет и проставит.
К сожалению, по поводу ВТФ никаких идей нет и не было, хотя тоже пытался, как и все математики.
Но все-таки я физик, именно этим и занимаюсь.
На моем сайте есть несколько математических тем, добавлю еще, но все зависит от настроения и желания.
Например, проблемы с инетом, надо разобраться, как оформить таблицу 16*16, патентов несколько сделать.
Так что не скоро смогу закончить эту тему.
P.S. Раскрасить в два цвета можно граф с четными вершинами ( узлами).

[Circiter]

Цитата:

Раскрасить в два цвета можно граф с четными вершинами ( узлами).

Раскрасить-то можно, только такая раскраска, вообще говоря, не будет правильной... Кстати, спасибо за ссылку на Саркисяна-Колягина, нашел, скачал, читаю. Надеюсь, теперь разберусь с вашими утверждениями. :)

[iig]

Я представляю так: режем на куски вдоль гракиц (ребер), в которых внутри остаются четные попарно страны.
Если не выходит, выбираем другой вариант разрезания и включаем еще одну нечетную в союзники вместе с подвернувшимися четными.
И так до тех пор, пока не разделимся попарно на блоки НАТО и СЭВ по старой терминологии, а потом внури них разборки.
Эта проблема может легко разрешится, даже умный школьник сделает, не обязательно вникать в политику.
Вот только где найти такого, когда все умники озабочены компутерами а не математикой.
P.S.нашел еще одну статью по теме:
П87 Проблемы современной математики Сборник М., "Знание", 1975.
Вариации на тему четырех красок. Томас Саати стр.5

[Xaositect]

Я вот боюсь, что если все это аккуратно написать, то получится перебор, объем которого сравним с перебором из исходного доказательства.

[iig]

Не спорю, проблема есть, но не на уровне ВТФ.
Сдесь все сводится к связыванию нечетнных стран между собой и к планарности.
Этих положений, полагаю, достаточно.
Планарнность основана на разрывании связей графа, проще говоря, разрезании всегда на две части.
Четность границ исходит из формулы Эйлера.

[Circiter]

Ага, кажется дошло. Оказывается iig имел ввиду раскраску граней графа, двойственного графу смежности стран! То есть речь идет о раскраске именно контурной политической карты. Так в примере Xaositect'а действительно есть одна нечетная вершина на пересечении границ, поэтому его грани не 2-раскрашиваемы. :) А если все вершины четные, то вот тогда грани такого графа и можно будет раскрасить всего двумя цветами. В рекомендованной iig'ом книжке это утверждение доказывается по индукции примерно так. Сначала выводится, что в рассматриваемом графе через любую вершину можно провести простой цикл. Итак, допустим, что вершину и цикл выбрали. Теперь этот цикл аккуратно удаляется, а оставшийся граф пофасеточно раскрашивается двумя красками (рекурсивно). После этого удаленный цикл можно восстановить и просто инвертировав цвета граней, им ограниченных, немедленно получить искомый граф с 2-раскрашенными гранями.

Ok, с этим ясно. Но как быть с нечетными вершинами? Пытаться склеить их в одну особую вершину с четной степенью? И что делать с оставшимися бесцветными странами? В общем, я опять запутался... :)

Кстати, думаю не лишним будет упомянуть ещё парочку известных мне простых наивных доказательств 4CT.

Вот например, некий I.Cahit строит спиральки на графах и успешно их (графы) раскрашивает (arXiv:math/0408247). То есть, он описывает алгоритмы раскраски и пытается показать их правильность, корректность, и т.д. Уровень строгости доказательств какое-то недоверие вызывает, хотя, я, честно говоря, все равно мало чего из его писанины понял. :) Да и вообще странный он какой-то, к примеру, судя по некоторым высказываниям, он не подозревает о необобщаемости 4CT на высшие размерности... :)

Есть ещё один чудик, некий Fayez A.Alhargan, так он вообще 4CT буквально в одну строку "решил". Пожалуй попробую кратко пересказать ход его мыслей.

Сначала он показывает, что если граф содержит подграф, изоморфный $K_n$ с $n>4$, то все, приехали, четырьмя красками не обойтись (в принципе, это очевидно). Затем пытается доказать, что у планарного графа нет и быть не может такого слишком большого полного подграфа.

Делает он это примерно так. Пусть у графа есть $n$ вершин, $m$ ребер и $r$ граней. Fayez замечает, что каждая страна на проблемной карте имеет как минимум три соседа, т.е., у каждой грани графа контурной карты (дуального графу соседства) имеется как минимум три ребра, что с учетом соответствия каждого ребра куску границы между максимум двумя странами приводит к неравенству $3r\leqslant 2m$, которое вместе с формулой Эйлера $n-m+r=2$ дает ещё одно неравенство $m\leqslant 3n-6$ (это известный результат для планарных графов, популярное изложение см. например в А.Ю.Ольшанский, Плоские графы, СОЖ, №11, 96г.).

Теперь Fayez подставляет в это неравенство значение $m=m(n)$ для полного графа, которое может быть получено из комбинаторных соображений; именно, для $K_n$ число $m$ (количество ребер) равно $0,5(n^2-n)$, т.е., количеству единиц над главной диагональю $n\times n$ матрицы забитой единицами. Подстановка в ранее полученную формулу дает квадратное неравенство $n^2-n\leqslant 6n-12$, которое имеет решение $n\in[3;\ 4]$. Из этого результата сразу же и делается вывод о несуществовании у планарного графа более чем 4-вершинного полного подграфа (точнее говоря, вывод о неукладываемости $K_{>4}$, что почти тоже самое). :)

Хм, неужели действительно из последнего вывода следует 4-раскрашиваемость карты? Интуитивно, да, если потребовалась пятая краска при оптимальном раскрашивании полит. карты, значит текущая страна граничит с четырьмя другими, на которые уже растрачена 4-палитра, т.е, с четырьмя странами, граф соседсва для которых полный. Но ведь это не исключает существования какого-нибудь иного сценария неэкономичного использования красок... В общем, мне почему-то кажется, что здесь есть какая-то логическая проблема (типа импликации в одну сторону вместо эквивалентности)... Иначе, какого [вырезано] вокруг 4CT было столько шумихи и горы сгенерированной компьютером макулатуры? :)

Честно говоря, когда-то я тоже пытался одолеть 4CT быстро и просто. Целых две недели мозги ломал. Но стоит ли говорить, что ничего дельного так и не придумал? :) Тем не менее, если вспомню, что именно я тогда накуралесил, то, наверное, напишу сюда... Но мой подход, мягко говоря, сильно отличался от рассуждений iig'а.

[Circiter]

Ранее я грозился привести ещё одно простое "доказательство" гипотезы четырех красок, на этот раз собственноручное. Решил выделить его в отдельную тему: 4CT, надеюсь заинтересует. :) А iig'овскую схему доказательсва предлагаю продолжить обсуждать здесь (я вот, например, его идеи так и не понял).