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

[iig]

Очень приятно, что вы пытались понять, у меня были проблемы с инетом, потому не светился.
В сущности, все сводится к разделению на "своих" и "чужих", внутри которых тоже происходят разборки.
Если бы более четко мог выразится, не стал бы советоваться на форуме.
Далее, главным тут считаю определение планарности как разрезание на два не связанных куска. К примеру, с тором такое не проделаешь, и мне не очень понятно сведение к двум каким-то графам.

[Circiter]

2iig
Вам как-нибудь может помочь наблюдение о четности количества нечетных вершин?

[iig]

Именно четность нечетных вершин я имел в виду.
Нечетные надо попарно соединить, если не смыкаются - через четные, включив их и подходящих соседей в "союзники", а затем внутри них раскрасить вдругие два цвета.
Другое дело, что на картинке получается, а в общем доказать не получается, хотя в основе две аксиомы - планарность разрезанием и четность нечетных из формулы эйлера.
Это даже умный школьник может доказать, каким я был, если бы тогда это знал..

[Circiter]

Цитата:

Другое дело, что на картинке получается

О, а может быть нарисуете картинку с последовательностью действий для простого случая? Ну пожалста... :)

[Circiter]

Кажется откопал что-то очень похожее на идею iig'а: А.А.Зыков, О некоторых свойствах линейных комплексов, Мат.сб. 24(66):2 (1949), 163-188. Хотелось бы услышать какие-нибудь комментарии ко второму параграфу этой статьи (заметьте, конец сороковых!).

[iig]

Circiter в сообщении #327463 писал(а):

Цитата:

Другое дело, что на картинке получается

О, а может быть нарисуете картинку с последовательностью действий для простого случая? Ну пожалста... :)

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

[pavka_1]

Можно решить проблему красок геометрически очень просто. Почему все используют графы?

[iig]

Графы наиболее простой и экономичный способ описания проблемы.
Геометрия привлекает много ненужных понятий типа длины, углов, параллельности и т.д.

В моем предложении считаю главным определение планарности как несвязности при дюбых способах разрезания. В общем виде эту тему развил Урысон,
но во всех учебниках по теории графов приводятся малопонятные формулировки типа несводимости к некоторым комбинациям.

[Circiter]

2pavka_1

Цитата:

Можно решить проблему красок геометрически очень просто

Поделитесь идеей. Очень интересно. Заранее спасибо. :)

[iig]

Наглядно и конструктивно вроде просто, но у меня нет четкого доказательства.
В начале поста я опиывал идею, попытаюсь повториьб.

Есть страны с четными и нечетными границами или четные или нечетные вершины.
Разрезаем карту так, чтобы четность сохранялась.
В пределе получим четную карту с регионами, внутри которых могут содержатся по паре нечетных.
Четную карту можно раскрасить в два цвета, которые внутри себя могут содержать два подцвета.
Таким образом 2х2=4!
Детально доказательство и алгоритм я не разработал, предоставляю всем желающим, мне некогда этим заниматься, но желательно на меня сослаться, если что получится из этого.
В любом случае не буду ругаться за плагиат, моя цель - не дать пропасть идее и стимулировать интерес.

[Kallikanzarid]

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

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

Опа, а откуда у нас двудольность?

[Circiter]

Откопал ещё такую заметку (из вестника пермского универа): Чечулин В.Л., Об одном варианте доказательства 4-раскрашиваемости плоских графов. Кто что об этом "доказательстве" думает?

P.S.: Кстати, я недавно построил ещё одно игрушечное доказательство 4CT, существенно опирающееся на классические результаты Зыкова (на этот раз работа ведется в направлении представления планарных графов в виде суммы двудольного графа и леса) и принципиально отличное от предыдущей попытки (основанной на недоработанной концепции цветовой редукции с привлечением ещё в большей степени недоработанной теории локальности операций над укладками графов; впрочем этот фреймворк я припас для атаки на гипотезу Хадвигера, во какие планы :) ). Скоро выложу, наверное. :)