Проблема четырех красок (туплю)

[VAL]

shkolnik в сообщении #766373 писал(а):

VAL в сообщении #766364 писал(а):

А причина Вашего непонимания, насколько я могу судить, в том, что Вы представляете себе произвольный планарный граф несвязным, состоящим из отдельных компонент, не содержащих $K_5$. Так?

Совершенно верно
Если Вы приведете контрпример, я сразу "образумлюсь" .

А Вы сами приведите такой пример!
Возьмите лист бумаги и нарисуйте на нем эдак с полста точек. А затем соединяйте эти точки линиями (не обязательно отрезками). Но так, чтобы:
1. Линии не пересекались нигде, кроме Ваших точек (вершин). Это обеспечит планарность.
2. Из любой вершины в любую можно было бы пройти по ребрам (Вашим линиям). Это обеспечит связность.
3. Ребер было бы как можно больше (пока можно добавлять, добавляйте). А это, чтобы жизнь медом не казалась

Нарисовали? А теперь красьте вершины в 4 цвета. Но так, чтобы смежные (соединенные одной линией) имели разные цвета.
Решение есть. Но оно сразу не очевидно. И это только для одного графа.

Цитата:

Именно так я считаю !
Если граф содержит $K_5$, то он неприметно не планарный, если же он содержит (в смысле в нем есть подграф $K_n, n \in N, n>5$), то он неприменно (по индукции) содержит и $K_5$, следовательно, он не планарный. Иначе (от противного) граф планарный.

В чем я ошибаюсь

Во-вторых, в том, что граф, не содержащий $K_5$ (более аккуратно: подграфа, стягиваемого в $K_5$) всегда планарен (см. пример Someone).
А во-первых - см. выше.

[shkolnik]

VAL в сообщении #766384 писал(а):

Во-вторых, в том, что граф, не содержащий (более аккуратно: подграфа, стягиваемого в ) всегда планарен (см. пример Someone).

А причем здесь пример ув. Someone ?

Я же не говорил, что любой граф, не "содержащий" $K_5$ планарный.

Я говорил, что, если граф содержит $K_5$, то он не планарный.

Это несколько разные утверждения.

Пример, ув. Someone не корректен, т.к. его граф не планарен !

Я не спорю, что граф Someone, не раскрасить четырьмя красками (по предложенным условиям), но причем здесь это, если этот граф (по определению) не планарный (т.е. нет такой плоской карты, которой бы Someone сопоставил предложенный граф).

Предъявите ее, если таковая существует !

Если таковая есть, я расценил бы это, как контрпример.

VAL в сообщении #766384 писал(а):

А Вы сами приведите такой пример!

Так нет его !

VAL в сообщении #766384 писал(а):

Возьмите лист бумаги и нарисуйте на нем эдак с полста точек. А затем соединяйте эти точки линиями (не обязательно отрезками). Но так, чтобы:
1. Линии не пересекались нигде, кроме Ваших точек (вершин). Это обеспечит планарность.
2. Из любой вершины в любую можно было бы пройти по ребрам (Вашим линиям). Это обеспечит связность.
3. Ребер было бы как можно больше (пока можно добавлять, добавляйте). А это, чтобы жизнь медом не казалась

Нарисовали? А теперь красьте вершины в 4 цвета. Но так, чтобы смежные (соединенные одной линией) имели разные цвета.
Решение есть. Но оно сразу не очевидно. И это только для одного графа.

Я это понимаю, пространство решений практически неизмеримо, мягко говоря.

Но, Все это неважно, в проблеме доказательства, достаточно рассмотреть пару $K_n, (n \geqslant 5 \lor n<5)$

[provincialka]

shkolnik в сообщении #766417 писал(а):

Но, Все это неважно, в проблеме доказательства, достаточно рассмотреть пару $K_n, (n \geqslant 5 \lor n<5)$

А с чего вы взяли, что достаточно? Доказательство - в студию!

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

[VAL]

shkolnik в сообщении #766417 писал(а):

VAL в сообщении #766384 писал(а):

Во-вторых, в том, что граф, не содержащий (более аккуратно: подграфа, стягиваемого в ) всегда планарен (см. пример Someone).

А причем здесь пример ув. Someone ?

Я же не говорил, что любой граф, не "содержащий" $K_5$ планарный.

Не знаю, говорили ли, но писали точно:

shkolnik в сообщении #766373 писал(а):

Если граф содержит $K_5$, то он неприметно не планарный, если же он содержит (в смысле в нем есть подграф $K_n, n \in N, n>5$), то он неприменно (по индукции) содержит и $K_5$, следовательно, он не планарный. Иначе (от противного) граф планарный.

Цитата:

Я говорил, что, если граф содержит $K_5$, то он не планарный.
Это несколько разные утверждения.

Я это понимаю. В отличие от Вас.

Цитата:

Пример, ув. Someone не корректен, т.к. его граф не планарен !

Так он и приводил пример непланарного графа, в котором ни каком виде нет $K_5$. Вопреки Вашим утверждениям, что так не бывает.

Цитата:

Я не спорю, что граф Someone, не раскрасить четырьмя красками (по предложенным условиям), но причем здесь это, если этот граф (по определению) не планарный (т.е. нет такой плоской карты, которой бы Someone сопоставил предложенный граф).

Вы не поверите. Его можно раскрасить четырьмя, тремя и даже двумя красками!

Цитата:

Цитата:

Предъявите ее, если таковая существует !

Если таковая есть, я расценил бы это, как контрпример.

Предъявляю: покрасьте вершины в верхнем ряду в зеленый цвет, а нижние в синий.

Цитата:

VAL в сообщении #766384 писал(а):

А Вы сами приведите такой пример!

Так нет его !

Все веселее и веселее. Ниже подробно описано как получить несуществующее!

Цитата:

VAL в сообщении #766384 писал(а):

Возьмите лист бумаги и нарисуйте на нем эдак с полста точек. А затем соединяйте эти точки линиями (не обязательно отрезками). Но так, чтобы:
1. Линии не пересекались нигде, кроме Ваших точек (вершин). Это обеспечит планарность.
2. Из любой вершины в любую можно было бы пройти по ребрам (Вашим линиям). Это обеспечит связность.
3. Ребер было бы как можно больше (пока можно добавлять, добавляйте). А это, чтобы жизнь медом не казалась

Нарисовали? А теперь красьте вершины в 4 цвета. Но так, чтобы смежные (соединенные одной линией) имели разные цвета.
Решение есть. Но оно сразу не очевидно. И это только для одного графа.

Я это понимаю, пространство решений практически неизмеримо, мягко говоря.

Но, Все это неважно, в проблеме доказательства, достаточно рассмотреть пару $K_n, (n \geqslant 5 \lor n<5)$

Подведем итоги:

Зря я (в большей степени), provincialka и Someone (самый прозорливый) взялись помогать Вам разобраться.
Вы, либо тролль (чем дальше, тем больше похоже на то), либо из тех людей, что из всех мнений слышат и уважают только свое.
В любом случае дальнейшая дискуссия бессмысленна.

[Someone]

shkolnik в сообщении #766417 писал(а):

Я же не говорил, что любой граф, не "содержащий" $K_5$ планарный.

Говорили, и совсем недавно:

shkolnik в сообщении #766373 писал(а):

Если граф содержит $K_5$, то он неприметно не планарный, если же он содержит (в смысле в нем есть подграф $K_n, n \in N, n>5$), то он неприменно (по индукции) содержит и $K_5$, следовательно, он не планарный. Иначе (от противного) граф планарный.

(Выделение моё.) Не надо столь нагло врать.

shkolnik в сообщении #766417 писал(а):

Я не спорю, что граф Someone, не раскрасить четырьмя красками

Ы-ы-ы… Прекрасно двумя раскрашивается: все верхние точки — в один цвет, все нижние — в другой.

-- Вс сен 22, 2013 01:08:35 --

Ой, уже VAL всё написал.

[shkolnik]

VAL в сообщении #766455 писал(а):

Подведем итоги:
Зря я (в большей степени), provincialka и Someone (самый прозорливый) взялись помогать Вам разобраться.
Вы, либо тролль (чем дальше, тем больше похоже на то), либо из тех людей, что из всех мнений слышат и уважают только свое.
В любом случае дальнейшая дискуссия бессмысленна.

Я просто запутался, я слышу и уважаю Ваше мнение.
Я действительно сам себе противоречил, теперь вижу это, я был неправ, простите.

provincialka в сообщении #766428 писал(а):

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

Кажется дошло, я прицепился к $K_5$ представляя его вершины разными цветами и пытаясь уложить в плоскость (сделать планарным). Зачем, сам не знаю, мне показалось, что из невозможности этого следует, что планарный граф можно раскрасить 4-мя цветами. Теперь вижу, что это глупость.

Someone в сообщении #766458 писал(а):

Ы-ы-ы… Прекрасно двумя раскрашивается: все верхние точки — в один цвет, все нижние — в другой.

Можно и одним цветом раскрасить (вообще не раскрашивать), просто смежные области будут одного цвета, а для раскраски карты они должны быть разными.

[Someone]

shkolnik в сообщении #766528 писал(а):

Можно и одним цветом раскрасить (вообще не раскрашивать), просто смежные области будут одного цвета, а для раскраски карты они должны быть разными.

Да Вы даже не вникаете в то, что Вам пишут. Граф $K_{3,3}$ правильно раскрашивается двумя красками: любые две смежные вершины будут разного цвета. При этом он не планарный и не содержит подграфа, гомеоморфного $K_5$. И я Вам об этом писал, и VAL, но Вы и не взглянули.

[shkolnik]

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

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

Есть ещё один чудик, некий 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 было столько шумихи и горы сгенерированной компьютером макулатуры? :)

Не я один такой, оказывается.
Это утешает.

[shkolnik]

Someone в сообщении #766458 писал(а):

shkolnik в сообщении #766417 писал(а):

Я же не говорил, что любой граф, не "содержащий" $K_5$ планарный.

Говорили, и совсем недавно:

shkolnik в сообщении #766373 писал(а):

Если граф содержит $K_5$, то он неприметно не планарный, если же он содержит (в смысле в нем есть подграф $K_n, n \in N, n>5$), то он неприменно (по индукции) содержит и $K_5$, следовательно, он не планарный. Иначе (от противного) граф планарный.

(Выделение моё.) Не надо столь нагло врать.

Я не врал, я просто ошибся, перепутал планарность с 4-раскрашиваемостью. Нужно было так:
Если граф содержит $K_5$, то он неприметно не планарный, если же он содержит (в смысле в нем есть подграф $K_n, n \in N, n>5$), то он неприменно (по индукции) содержит и $K_5$, следовательно, он не планарный. Иначе (от противного) граф содержит не более чем $K_4$ (т.е. 4-раскрашиваем).

Someone в сообщении #766532 писал(а):

Да Вы даже не вникаете в то, что Вам пишут. Граф $K_{3,3}$ правильно раскрашивается двумя красками: любые две смежные вершины будут разного цвета. При этом он не планарный и не содержит подграфа, гомеоморфного $K_5$. И я Вам об этом писал, и VAL, но Вы и не взглянули.

Здесь я тоже ошибся. Я просто не воспринимал Ваш пример, как корректный, т.к. граф не планарный, поэтому, действительно, не очень то и вникал. Это просто недоразумение из-за того, что я перепутал раскрашиваемость с планарностью. Этот граф можно раскрасить 2 цветами, да.

[Someone]

shkolnik в сообщении #766548 писал(а):

Если граф содержит $K_5$, то он неприметно не планарный, если же он содержит (в смысле в нем есть подграф $K_n, n \in N, n>5$), то он неприменно (по индукции) содержит и $K_5$, следовательно, он не планарный. Иначе (от противного) граф содержит не более чем $K_4$ (т.е. 4-раскрашиваем).

Индукция здесь ни при чём, то, что $K_m$ содержит подграф $K_n$ при $n\leqslant m$, совершенно очевидно следует просто из определения полного графа. А утверждение, что граф, не содержащий $K_5$, непременно $4$-раскрашиваем, просто неверно. Вот контрпример.

$$\begin{xy}(0,20)*{\circ};(0,-20)*{\circ};**@{.},(-7.1,-7.1)*{\circ};**@{-}, (16.8,-2.2)*{\circ};**@{-},(17.5,5.7)*{\circ};**@{-},(-6,5.7)*{\circ};**@{.}, (-21.2,-2.2)*{\circ};**@{.},(-7.1,-7.1);**@{-},(0,20);**@{-}, (16.8,-2.2);**@{-},(0,-20);**@{-},(17.5,5.7);**@{.},(0,20);**@{-}, (-6,5.7);**@{.},(0,-20);**@{.},(-21.2,-2.2);**@{-},(0,20);**@{-}\end{xy}$$

[shkolnik]

Someone в сообщении #766601 писал(а):

А утверждение, что граф, не содержащий $K_5$, непременно $4$-раскрашиваем, просто неверно. Вот контрпример.

Вот, блин, опять накосячил.

Может быть так: граф не содержащий $K_5$ 4-раскрашиваем, если планарен.

Впрочем, лучше на рассуждения Circiter ссылаться. Если ли в этом доказательстве ошибка, и если да, то в каком именно месте ?
К какому именно утверждению может относится вот это замечание: "В общем, мне почему-то кажется, что здесь есть какая-то логическая проблема (типа импликации в одну сторону вместо эквивалентности)..."

[Someone]

shkolnik в сообщении #766609 писал(а):

Вот, блин, опять накосячил.

Может быть так: граф не содержащий $K_5$ 4-раскрашиваем, если планарен.

И опять накосячили: планарный граф $4$-раскрашиваем. Упоминать здесь ещё и $K_5$ совсем не требуется.

[provincialka]

shkolnik, Вы чего хотите? Свое доказательство придумать? Не получится, это трудная теорема.

[shkolnik]

provincialka в сообщении #766636 писал(а):

shkolnik, Вы чего хотите? Свое доказательство придумать? Не получится, это трудная теорема.

Да, нет же, я теперь просто пытаюсь понять верны ли мои рассуждения. Почему то явно никто не ответил.
Circiter изложил в двух строчках то, что я никак не мог сформулировать:
"Интуитивно, да, если потребовалась пятая краска при оптимальном раскрашивании полит. карты, значит текущая страна граничит с четырьмя другими, на которые уже растрачена 4-палитра, т.е, с четырьмя странами, граф соседсва для которых полный."
Я примерно так и рассуждал. Если при раскраске вдруг потребовалась пятая краска, то очевидно (мне было), что страна граничит с 4-мя другими, иначе раскраска не оптимальна. Т.е. либо конкретная раскраска оказалась не оптимальной, либо граф не планарный. Проблемой мне казалось, как раз доказательство, что $K_{>4}$ не вкладывается в плоскость, которое я пытался геометрически решить (с чего и началась тема). Circiter же указал, как это элементарно доказывается без геометрии.

Ну, так эти рассуждения все-таки верны или нет ? И если нет, то где именно и почему ?

[provincialka]

Неверно там, где вы переходите к полному графу. Действительно, мы не можем раскрасить страну (вершину графа), если четыре ее соседа имеют разные цвета. Но почему они имеют разные цвета? Простейшая причина - что они все касаются друг друга (для графа - все вершины непосредственно соединены). Но может быть и по-другому, существуют цепочки стран (ребер), или более сложные конструкции, которые при раскрашивании приводят к таким цветам? А ведь такие конструкции, такие наборы стран могут быть весьма большими.