Теорема Френсиса Гутри о 4-х красках

Автор темы dmix 
ОбъявленияПоследний пост
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеВ марте в МГУ имени М.В. Ломоносова пройдет II Кубок Москвы по Го среди студентов ВУЗов14.02.2020 11:44
11.12.2019 12:32
.
Цитата
dmix
1. Мы ищем такую конфигурацию G из множества Gn плоских графов, которая бы заведомо требовала M цветов для раскраски всех своих вершин.

Слово "конфигурация" - мусорное, слово "заведомо" - мусорное.
Мы просто ищем такой плоский граф, который требует для раскраски $M$ цветов ($\chi(G) = M$).
И как раз этим все и занимались.
Так как давно известно, что $M \le 5$, то все усиленно искали плоские графы, для раскраски которых требуется $5$ цветов. Когда стало понятно, что таких плоских графов не существует, то получилось сделать вывод, что $M = 4$.

Цитата
dmix
Вопрос: в каком случае мы можем быть заведомо, на 100% уверены в том, что это и есть M ?
Ответ: когда все вершины G раскрашены в разный цвет (k = v).

Эти два предложения не связаны между собой.
$M$ - максимум хроматического числа графа на множестве плоских графов.
$k$ - просто количество цветов, в которые можно раскрасить граф (не требуется, а именно просто можно раскрасить).
Я снова наблюдаю признаки подмены, на этот раз $\chi(G)$ vs. $k$.

Цитата
dmix
Вопрос: в каком случае мы можем быть заведомо, на 100% уверены в том, что это и есть M ?
Ответ: когда все вершины G раскрашены в разный цвет (k = v).

Не забивайте голову этим $M$ в общем случае.
Вместо него можно использовать 5 и ничего не поменяется.
Вот мы пытаемся найти плоский граф $G$, которому требуется 5 цветов ($\chi(G) = 5$).
Допустим, что нашли. Тогда что про него можно сказать? Что он полный и содержит 5 вершин?
11.12.2019 13:53
Все вершины в разный цвет
Цитата
r-aax
Цитата
dmix
Вопрос: в каком случае мы можем быть заведомо, на 100% уверены в том, что это и есть M ?
Ответ: когда все вершины G раскрашены в разный цвет (k = v).

Не забивайте голову этим $M$ в общем случае.
Вместо него можно использовать 5 и ничего не поменяется.
Вот мы пытаемся найти плоский граф $G$, которому требуется 5 цветов ($\chi(G) = 5$).
Допустим, что нашли. Тогда что про него можно сказать? Что он полный и содержит 5 вершин?
Зачем вы уходите сторону от вопроса ?

Повторю вопрос:
в каком случае мы можем быть заведомо, на 100% уверены в том, что это и есть M ?
Ответ: когда все вершины G раскрашены в разный цвет (k = v).

Если мы допускаем, что в искомом графе есть хотя бы одна вершина, использующая один и тот же цвет с другой,
то никогда не будем уверены на 100%, что нашли М.



Редактировалось 1 раз(а). Последний 11.12.2019 13:53.
11.12.2019 14:04
.
Цитата
dmix
Если мы допускаем, что в искомом графе есть хотя бы одна вершина, использующая один и тот же цвет с другой,
то никогда не будем уверены на 100%, что нашли М.

Почему?
11.12.2019 14:27
Все вершины в разный цвет
Цитата
r-aax
Цитата
dmix
Если мы допускаем, что в искомом графе есть хотя бы одна вершина, использующая один и тот же цвет с другой,
то никогда не будем уверены на 100%, что нашли М.

Почему?
Потому что, когда все вершины окрашены в разный цвет - искомый граф задействовал всё количество цветов.
Нечего больше раскрашивать - уже все вершины раскрашены (к = v)
100% вершин раскрашены в разный цвет.

В противном случае, остается неопределенность - есть, хотя бы одна, вершина, использующая один и тот же цвет с другой.



Редактировалось 2 раз(а). Последний 11.12.2019 14:31.
11.12.2019 14:40
.
Цитата
dmix
Цитата
r-aax
Цитата
dmix
Если мы допускаем, что в искомом графе есть хотя бы одна вершина, использующая один и тот же цвет с другой,
то никогда не будем уверены на 100%, что нашли М.

Почему?
Потому что, когда все вершины окрашены в разный цвет - искомый граф задействовал всё количество цветов.
Нечего больше раскрашивать - уже все вершины раскрашены (к = v)
100% вершин раскрашены в разный цвет.

В противном случае, остается неопределенность - есть, хотя бы одна, вершина, использующая один и тот же цвет с другой.

Это наивный ответ.
Представьте ситуацию: я нарисовал плоский граф из 10 вершин и обнаружил, что в четыре цвета раскрасить его не могу, но в 5 могу.
Я точно уверен, что мне не нужно его красить в 6 цветов или тем более в 10, как вы предлагаете для какой-то 100-процентной уверенности.
Так вот, для достижения $M = 5$ мне вполне хватит такого графа.
Почему я не смогу его построить?
11.12.2019 19:23
Доказательство методом строительства снизу
Цитата
r-aax
Цитата
dmix
Цитата
r-aax
Цитата
dmix
Если мы допускаем, что в искомом графе есть хотя бы одна вершина, использующая один и тот же цвет с другой,
то никогда не будем уверены на 100%, что нашли М.

Почему?
Потому что, когда все вершины окрашены в разный цвет - искомый граф задействовал всё количество цветов.
Нечего больше раскрашивать - уже все вершины раскрашены (к = v)
100% вершин раскрашены в разный цвет.

В противном случае, остается неопределенность - есть, хотя бы одна, вершина, использующая один и тот же цвет с другой.

Это наивный ответ.
Представьте ситуацию: я нарисовал плоский граф из 10 вершин и обнаружил, что в четыре цвета раскрасить его не могу, но в 5 могу.
Я точно уверен, что мне не нужно его красить в 6 цветов или тем более в 10, как вы предлагаете для какой-то 100-процентной уверенности.
Так вот, для достижения $M = 5$ мне вполне хватит такого графа.
Почему я не смогу его построить?
:) Сформулирую вопрос иначе.

Я раскрасил все вершины графа G в разные цвета и получил к - цветов раскраски.
Вы сможете раскрасить этот граф так, чтобы у вас получилось k+1 цвет ?
Ответ нет - потому как уже к = v.

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

Для этого не потребуются суперкомпьютеры, так как количество итераций невелико.
Соединяем первую пару вершин - получили K2.

Добавляем еще вершину и, соблюдая требования условий теоремы, соединяем ее ребрами с другими вершинами.
Затем еще и еще и ... упираемся в K5, который невозможно построить.
Все - вот вам еще один вариант доказательства.
11.12.2019 20:49
.
Цитата
dmix
:) Сформулирую вопрос иначе.

Я раскрасил все вершины графа G в разные цвета и получил к - цветов раскраски.
Вы сможете раскрасить этот граф так, чтобы у вас получилось k+1 цвет ?
Ответ нет - потому как уже к = v.[/math]

Мне не нужен ваш k+1 цвет, мне хватит 5. Желание раскрасить все вершины в разные цвета эти ваши необоснованные фантазии, в погоне за которыми вы выходите за пределы множества плоских графов, и все ваши рассуждения теряют смысл.

Цитата
dmix
Рассмотрим еще один вариант доказательства - будем строить теоретический граф снизу.
Начнем соединять вершины ребрами так, что любые две вершины были смежны между собой.

Для этого не потребуются суперкомпьютеры, так как количество итераций невелико.
Соединяем первую пару вершин - получили K2.

Добавляем еще вершину и, соблюдая требования условий теоремы, соединяем ее ребрами с другими вершинами.
Затем еще и еще и ... упираемся в K5, который невозможно построить.
Все - вот вам еще один вариант доказательства.

Не выдумывайте, в теореме никто не заставляет новую вершину соединять со всеми старыми.
12.12.2019 14:03
Доказательство
Цитата
r-aax
Цитата
dmix
:) Сформулирую вопрос иначе.

Я раскрасил все вершины графа G в разные цвета и получил к - цветов раскраски.
Вы сможете раскрасить этот граф так, чтобы у вас получилось k+1 цвет ?
Ответ нет - потому как уже к = v.[/math]

Мне не нужен ваш k+1 цвет, мне хватит 5. Желание раскрасить все вершины в разные цвета эти ваши необоснованные фантазии, в погоне за которыми вы выходите за пределы множества плоских графов, и все ваши рассуждения теряют смысл.

Цитата
dmix
Рассмотрим еще один вариант доказательства - будем строить теоретический граф снизу.
Начнем соединять вершины ребрами так, что любые две вершины были смежны между собой.

Для этого не потребуются суперкомпьютеры, так как количество итераций невелико.
Соединяем первую пару вершин - получили K2.

Добавляем еще вершину и, соблюдая требования условий теоремы, соединяем ее ребрами с другими вершинами.
Затем еще и еще и ... упираемся в K5, который невозможно построить.
Все - вот вам еще один вариант доказательства.

Не выдумывайте, в теореме никто не заставляет новую вершину соединять со всеми старыми.
Добрый день.

Первый Ваш тезис: "Желание раскрасить все вершины в разные цвета эти ваши необоснованные фантазии"
Второй Ваш тезис: "в теореме никто не заставляет новую вершину соединять со всеми старыми"

А теперь обратимся к тому, что сказано в первоисточнике - к условиям теоремы:
"любые две области, имеющие общую границу, должны быть окрашены в разный цвет".
1. "любые две области ... в разный цвет"
2. "любые две области, имеющие общую границу ... "

Как мы видим из условий теоремы, ваши высказывания не корректны.

Теперь, строго выполняя условия теоремы, мы и ищем теоретический граф с наибольшим количеством вершин, который бы удовлетворял данным условиям.

1. "любые две области ... в разный цвет"
Строим граф, в котором все вершины окрашены в разный цвет, т.е. данный граф, теоретически, задействует максимально возможное число цветов из набора для раскраски всех своих вершин; ведь мы пытаемся найти возможность раскраски более чем 4 цветами.

2. "любые две области, имеющие общую границу ... "
Значит, в данном графе, все области должны иметь общую границу между собой, другими словами, все вершины графа должны быть смежны между собой.
Отсюда следует то, что данный граф полный, так как при n = const. rKn > rGn, где r - количество ребер графа.

3. А так как полных планарных графов Kn, где n > 4 не существует, то искомое число M = 4.

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



Редактировалось 1 раз(а). Последний 12.12.2019 14:09.
12.12.2019 17:01
.
Пожалуй, закреплю это здесь.

Цитата
dmix
А теперь обратимся к тому, что сказано в первоисточнике - к условиям теоремы:
"любые две области, имеющие общую границу, должны быть окрашены в разный цвет".
1. "любые две области ... в разный цвет"
2. "любые две области, имеющие общую границу ... "

Цитата
dmix
1. "любые две области ... в разный цвет"
Строим граф, в котором все вершины окрашены в разный цвет...

Цитата
dmix
2. "любые две области, имеющие общую границу ... "
Значит, в данном графе, все области должны иметь общую границу между собой...

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

Повторяю.

Цитата
r-aax
Желание раскрасить все вершины в разные цвета это ваши необоснованные фантазии, в погоне за которыми вы выходите за пределы множества плоских графов, и все ваши рассуждения теряют смысл.

Цитата
r-aax
Не выдумывайте, в теореме никто не заставляет новую вершину соединять со всеми старыми.
12.12.2019 18:51
Любые две области ... окрашены в разный цвет
Цитата
r-aax
Пожалуй, закреплю это здесь.

Цитата
dmix
А теперь обратимся к тому, что сказано в первоисточнике - к условиям теоремы:
"любые две области, имеющие общую границу, должны быть окрашены в разный цвет".
1. "любые две области ... в разный цвет"
2. "любые две области, имеющие общую границу ... "

Цитата
dmix
1. "любые две области ... в разный цвет"
Строим граф, в котором все вершины окрашены в разный цвет...

Цитата
dmix
2. "любые две области, имеющие общую границу ... "
Значит, в данном графе, все области должны иметь общую границу между собой...

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

Повторяю.
Цитата
r-aax
Желание раскрасить все вершины в разные цвета это ваши необоснованные фантазии, в погоне за которыми вы выходите за пределы множества плоских графов, и все ваши рассуждения теряют смысл.

Цитата
r-aax
Не выдумывайте, в теореме никто не заставляет новую вершину соединять со всеми старыми.
Конечно не заставляет - вы или решаете задачу, следуя условиям, или блуждаете в неопределенности.
Возможно, второе как-то связано с финансовыми аспектами.

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

В противном случае, приведите, пожалуйста, пример плоского графа, где выполняется указанное условие, но не все вершины окрашены в разный цвет.

P.S. Ваши постоянные попытки дать оценку("посудить"; например, в виде фразы: "Что за лютый бред?"),
говорят о том, что у вас наблюдается ярко выраженный когнитивный диссонанс.



Редактировалось 2 раз(а). Последний 12.12.2019 19:35.
13.12.2019 00:41
Еще один вариант доказательства теоремы Френсиса Гутри о четырех цветах
Но, перед тем, как приступить к изложению доказательства, сделаю небольшое отступление.

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

Итак, данный вариант доказательства назовем "Контрольный граф".

1. Условие теоремы Френсиса Гутри звучит так:
"любые две области, имеющие общую границу, должны быть окрашены в разный цвет".

Какое условие в данном высказывании общее, а какое уточняющее ?
Деепричастный оборот: "имеющие общую границу" - есть уточнение.

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

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

2. Теперь, мы применяем дополнительное условие к данному графу: "любые две области, имеющие общую границу".
Т.е. все вершины "контрольного графа" должны быть смежны между собой.
Другими словами, данный граф должен быть полным.

3. А так как полных планарных графов Kn, где n > 4 не существует (критерий Понтрягина - Куратовского),
то максимальная величина n = 4, а значит и M=4.

Граф К4 и есть наш "Контрольный граф".
На произвольной карте может потребоваться и менее 4 цветов для раскраски.
Теорема доказана.

А вот почему, она не была доказана до сего дня, читаем в самом начале поста.
Доказательство 1976 года (перебором) - не совсем доказательство.



Редактировалось 16 раз(а). Последний 13.12.2019 01:25.
13.12.2019 09:29
вот и ответ
Цитата
dmix
Добрый день всем.
Цитата
zklb (Дмитрий)
автор часом не путает фразы: "любые две области, имеющие общую границу" и "любые две области имеют общую границу"?
Будьте добры пояснить ваше сомнение на, приведенном вами, примере.
Цитата
dmix
2. "любые две области, имеющие общую границу ... "
Значит, в данном графе, все области должны иметь общую границу между собой, другими словами, все вершины графа должны быть смежны между собой.
Отсюда следует то, что данный граф полный, так как при n = const. rKn > rGn, где r - количество ребер графа.
13.12.2019 09:33
.
Цитата
dmix
Но, перед тем, как приступить к изложению доказательства, сделаю небольшое отступление.

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

Все не так.
Когда вы вынуждены записывать свое "доказательство" не словами, а формулами со строгими определениями, то вы теряете поле для жульничества, что вас конечно не устраивает.
А с "пластами, переданными через слово" вам не в математику, а в философию.

Цитата
dmix
1. Условие теоремы Френсиса Гутри звучит так:
"любые две области, имеющие общую границу, должны быть окрашены в разный цвет".

Цитата
dmix
Само же условие: "любые две области ... должны быть окрашены в разный цвет" определяет граф, где все вершины окрашены в разный цвет.

Это прекрасно.

1) Сначала вы пытались подменить при поиске своих максимумов множество плоских графов на множество любых графов ($M$ vs. $m^{*}(n)$).
2) Когда были пойманы, попытались подменить хроматическое число на просто число цветов для раскраски ($\chi(G)$ vs. $k$).
3) Когда были пойманы, решили не мелочиться и подменяете условие теоремы, ограничиваясь полными графами ("любые две области, имеющие общую границу, должны быть окрашены в разный цвет" vs. "любые две области ... должны быть окрашены в разный цвет").

Тройное жульничество.

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



Редактировалось 1 раз(а). Последний 13.12.2019 09:34.
13.12.2019 14:21
Механизм мышления или "смотрят и не видят, слушают и не слышат"
Всем добрый день.

Цитата
r-aax
Мы просто ищем такой плоский граф, который требует для раскраски $M$ цветов ($\chi(G) = M$).
И как раз этим все и занимались.
Так как давно известно, что $M \le 5$, то все усиленно искали плоские графы, для раскраски которых требуется $5$ цветов. Когда стало понятно, что таких плоских графов не существует, то получилось сделать вывод, что $M = 4$.
"ищем", "этим все занимались", "все усиленно искали".

Хорошо, вот Вы нашли 1ый граф, затем 2ой .... nый и что вы с ними делаете ?

Рассмотрим это на примере одного графа.
Вот вы нашли его (или компьютер вам выдал вариант) и что дальше происходит ?
Есть картинка графа с раскраской его вершин и ....

Что происходит дальше ?



Редактировалось 1 раз(а). Последний 13.12.2019 14:41.
13.12.2019 15:47
.
Я не понял, вам рассказать, как графы перебирали в компьютерном доказательстве?
Так все в открытом доступе
https://projecteuclid.org/euclid.ijm/1256049011
https://projecteuclid.org/euclid.ijm/1256049012
13.12.2019 15:58
Механизм мышления
Цитата
r-aax
Я не понял, вам рассказать, как графы перебирали в компьютерном доказательстве?
Так все в открытом доступе
https://projecteuclid.org/euclid.ijm/1256049011
https://projecteuclid.org/euclid.ijm/1256049012
Да - расскажите, пожалуйста, сами - своими словами.
Вот Вы выбрали один граф и ...
Что происходит дальше ?
13.12.2019 17:19
.
Цитата
dmix
Да - расскажите, пожалуйста, сами - своими словами.
Вот Вы выбрали один граф и ...
Что происходит дальше ?

Простите, боюсь у меня нет времени заниматься вашим образованием.
Статьи по предыдущим ссылкам читать, наверное, не стоит, это старье.
А вот эта свежая, и в ней описано, как осуществляется перебор.
http://www.ams.org/notices/200811/tx081101382p.pdf
13.12.2019 17:54
Продолжаем исследовать метод "перебор"
Цитата
r-aax
Цитата
dmix
Да - расскажите, пожалуйста, сами - своими словами.
Вот Вы выбрали один граф и ...
Что происходит дальше ?

Простите, боюсь у меня нет времени заниматься вашим образованием.
...
А вот эта свежая, и в ней описано, как осуществляется перебор.
http://www.ams.org/notices/200811/tx081101382p.pdf
Ключевое слово "перебор".

Вижу, вы не понимаете меня - понижу частоту вибраций.
В любом цикле for(), for ... next, do() while(), как вы выразились "переборе",
внутри цикла существует условие ! Надеюсь это для вас не новость :)

Вы же не ради перебора, как такового, делаете перебор !?
Так вот, мой вопрос, другими словами, звучит так: что за условие стоит в цикле ?

Рассмотрим одну итерацию.
Вы выбрали граф и ... какое условие(я) Вы к нему применяете ?
13.12.2019 19:48
запахло жареным !?
Добрый вечер.

Ввиду того, что простой вопрос ввел в ступор уважаемого r-aax, отвечу на него сам.
Рассмотрение идет на множестве плоских графов.

Есть всего два условия для искомого графа и они сформулированы в теореме:
1. Любые две области должны иметь общую границу
2. Любые две области должны быть окрашены в разный цвет.
Все !!! (можно переставлять их местами)

В прошлом, очередном варианте доказательства, я не просто так намекнул - ввел наименование "контрольный граф".
И именно граф, удовлетворяющий данным условиям и есть наш искомый граф.

По сути, эти два условия и есть алгоритм строительства данного графа.
А равно, как и дорожная карта доказательства.

О каком "переборе" может идти речь !?



Редактировалось 1 раз(а). Последний 13.12.2019 19:49.
13.12.2019 19:57
.
Цитата
dmix
Есть всего два условия для искомого графа и они сформулированы в теореме:
1. Любые две области должны иметь общую границу
2. Любые две области должны быть окрашены в разный цвет.

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

Цитата
dmix
О каком "переборе" может идти речь !?

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

Кликните здесь, чтобы войти