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

[shkolnik]

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

[gris]

Если позволите, то я про треугольник. А как определить, какая точка лежит вне треугольника, а какая внутри? Что такое внутренность треугольника?

[shkolnik]

Гм..

(- Щас профессор "завалит" - думает про себя )

В данном случае неважно, какая часть пространства является внутренностью треугольника, а какая внешностью. Я имел в виду, что не существует треугольника навроде листа Мебиуса, когда внутренность плавно переходит во внешность (тогда треугольник не получится). Вроде...

[ewert]

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

В данном случае неважно, какая часть пространства является внутренностью треугольника, а какая внешностью.

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

[shkolnik]

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

[gris]

Одна из точек, Вы хотите сказать. На плоскости и для треугольника (выпуклой фигуры) можно придумать несколько определений внутренней точки, например, для внутренней: любая прямая, проходящая через точку, пересекает границу; для внешней: существует прямая, не пересекающая границу. Вроде бы очевидно, но если Вы попытаетесь встраивать это в аксиоматику Евклида, то встретитесь с большими трудностями.
А в проблеме четырёх красок таких трудностей на порядок больше. И с виду простое сопоставление с графами и рассуждения о их свойствах следует тщательнее продумать.

[VAL]

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

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

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

[shkolnik]

gris в сообщении #766136 писал(а):

Вроде бы очевидно, но если Вы попытаетесь встраивать это в аксиоматику Евклида, то встретитесь с большими трудностями. А в проблеме четырёх красок таких трудностей на порядок больше. И с виду простое сопоставление с графами и рассуждения о их свойствах следует тщательнее продумать.

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

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

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

Тогда в чем проблема ?

Есть плоская карта. Любая область, образованная замкнутой кривой на этой плоскости является областью (вершиной графа). Любой участок кривой, являющийся смежным с другой областью (вершиной графа), является границей (ребром графа). Анклавов нет (по условию).

Вроде бы проблема в доказательстве четырех утверждений:
1) Если граф содержит $K_5$, то он не планарен;
2) Если граф содержит подграф $R_n, n>5$, то он содержит и $K_5$ (по индукции);
3) Граф не содержащий $K_5$ разложим на графы, содержащие не более чем $K_4$;
4) Графы $K_4$ можно раскрасить четырьмя красками;

[VAL]

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

Тогда в чем проблема ?

Есть плоская карта. Любая область, образованная замкнутой кривой на этой плоскости является областью (вершиной графа). Любой участок кривой, являющийся смежным с другой областью (вершиной графа), является границей (ребром графа). Анклавов нет (по условию).

Вроде бы проблема в доказательстве четырех утверждений:
1) Если граф содержит $K_5$, то он не планарен;
2) Если граф содержит подграф $R_n, n>5$, то он содержит и $K_5$ (по индукции);
3) Граф не содержащий $K_5$ разложим на графы, содержащие не более чем $K_4$;

Уточните, в каком смысле разложим?

Цитата:

4) Графы $K_4$ можно раскрасить четырьмя красками;

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

[provincialka]

Если правильно поняла ваши обозначения, $K_4$ - это просто полный граф с 4 вершинами? Ну, его можно раскрасить 4 красками. А причем тут весь граф?

[shkolnik]

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

Уточните, в каком смысле разложим?

В смысле объединения множеств. Когда я говорил "состоит", то имел в виду подмножество, когда говорил "разложим", то имел в виду объединение множеств.

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

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

Я не понимаю этого.
В чем я виноват ?

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

Если правильно поняла ваши обозначения, $K_4$ - это просто полный граф с 4 вершинами? Ну, его можно раскрасить 4 красками. А причем тут весь граф?

Это обозначения ув. VAL.
При чем тут весь граф не знаю. Знаю только, что если подмножеством этого графа является граф минимум $K_5$, то он не планарен (т.е. 4-мя красками его не раскрасить).

[VAL]

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

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

Уточните, в каком смысле разложим?

В смысле объединения множеств. Когда я говорил "состоит", то имел в виду подмножество, когда говорил "разложим", то имел в виду объединение множеств.

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

Цитата:

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

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

Я не понимаю этого.
В чем я виноват ?

Вы не виноваты. Виноват Задорнов!
(Это я серьезно. Вы выносите свое непонимание туда, куда следует - на соответствующий форум. А он...).

Цитата:

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

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

[shkolnik]

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

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

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

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

[provincialka]

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

[Someone]

$$K_{3,3}$$

$$\qquad\begin{xy} (0,0)*{\circ};(20,0)*{\circ};(40,0)*{\circ}; (0,20)*{\circ};(20,20)*{\circ};(40,20)*{\circ}; (0,0);(0,20);**@{-};(0,0);(20,20);**@{-};(0,0);(40,20);**@{-}; (20,0);(0,20);**@{-};(20,0);(20,20);**@{-};(20,0);(40,20);**@{-}; (40,0);(0,20);**@{-};(40,0);(20,20);**@{-};(40,0);(40,20);**@{-}; \end{xy}$$