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

Автор темы dmix 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
26.11.2019 12:39
Теорема Френсиса Гутри о 4-х красках
Доказательство гипотезы (теоремы) Френсиса Гутри о четырех красках
без использования компьютерных вычислений и перебора.

Максимальное (max) количество цветов для раскраски областей требуется только в случае, когда каждая из областей на плоскости или поверхности шара (глобуса) имеет с каждой оставшейся общую границу, т.е. соблюдается принцип – “все со всеми”.
Данному принципу соответствует лишь одна форма соединения областей - “треугольник”:

рис: Доказательство
Дополненная версия доказательства с уточнением формулировок

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

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



Редактировалось 7 раз(а). Последний 04.12.2019 13:28.
26.11.2019 14:14
хм
аж умилился от подобной святой простоты. сразу понял, как доказывать теорему ферма: заменим в уравнении степень двойки на другое число. тогда равенство нарушится, что и требовалось доказать)
26.11.2019 15:10
Теорема Френсиса Гутри о 4ех красках
Не нравиться простое решение - решайте сложно :)

По существу доказательства есть вопросы ?
Есть возражение по поводу принципа "все со всеми" и формы соединения "треугольник" ?



Редактировалось 1 раз(а). Последний 26.11.2019 15:12.
26.11.2019 15:30
хм
Цитата
dmix
По существу доказательства есть вопросы ?

легко - докажите этот перл:
Цитата
dmix
Максимальное (max) количество цветов для раскраски областей требуется только в случае, когда каждая из областей на плоскости или поверхности шара (глобуса) имеет с каждой оставшейся общую границу, т.е. соблюдается принцип – “все со всеми”.
26.11.2019 16:08
Теорема Френсиса Гутри о 4ех красках
Когда есть общая граница каждой области с каждой, только тогда требуется "новый" цвет.
Если нет общей границы то и "новый" цвет не требуется - т.е. не требуется увеличивать количество цветов.



Редактировалось 1 раз(а). Последний 26.11.2019 16:10.
26.11.2019 16:24
хм
совершенно не понятно - что такое "новый" цвет, но да ладно. вот как раз то, что
Цитата
dmix
Если нет общей границы то и "новый" цвет не требуется - т.е. не требуется увеличивать количество цветов.
вам и надо доказать.
26.11.2019 16:41
Теорема Френсиса Гутри о 4ех красках
Цитата
zklb (Дмитрий)
совершенно не понятно - что такое "новый" цвет, но да ладно. вот как раз то, что
Цитата
dmix
Если нет общей границы то и "новый" цвет не требуется - т.е. не требуется увеличивать количество цветов.
вам и надо доказать.
На количество цветов раскраски влияют только граничащие между собой области, причем в соответствии с принципом "все со всеми".
Если какая либо область не граничит со всеми остальными то зачем ей(области) "новый"(дополнительный) цвет.

(подскажите - здесь рисунки как прикреплять ? было бы нагляднее)



Редактировалось 1 раз(а). Последний 26.11.2019 16:42.
26.11.2019 17:13
хм
Цитата
dmix
Если какая либо область не граничит со всеми остальными то зачем ей(области) "новый"(дополнительный) цвет.
затем, что граничащие с ней области могут быть раскрашены уже во все имеющиеся цвета, и чтобы её закрасить, нужен дополнительный цвет.
Цитата
dmix
(подскажите - здесь рисунки как прикреплять ? было бы нагляднее)
см. пункт 5: http://www.mathforum.ru/forum/read/1/17818/
26.11.2019 18:26
Теорема Френсиса Гутри о 4ех красках
Цитата
zklb (Дмитрий)
Цитата
dmix
Если какая либо область не граничит со всеми остальными то зачем ей(области) "новый"(дополнительный) цвет.
затем, что граничащие с ней области могут быть раскрашены уже во все имеющиеся цвета, и чтобы её закрасить, нужен дополнительный цвет.
Не могут - возвращаемся к началу беседы.

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

И если мы добавляем еще одну область, то нарушается принцип "все со всеми" и уже в этом случае не возникает
необходимости в дополнительном цвете.

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

Спасибо за помощь.



Редактировалось 4 раз(а). Последний 29.11.2019 06:56.
27.11.2019 00:23
хм
Цитата
dmix
Цитата
zklb (Дмитрий)
Цитата
dmix
Если какая либо область не граничит со всеми остальными то зачем ей(области) "новый"(дополнительный) цвет.
затем, что граничащие с ней области могут быть раскрашены уже во все имеющиеся цвета, и чтобы её закрасить, нужен дополнительный цвет.
Не могут - возвращаемся к началу беседы.

Единственная существующая форма соединения областей, обеспечивающая
соприкосновение по принципу "все со всеми" это "треугольник" - см. ссылку на рис. в начале темы.
http://www.sciteclibrary.ru/yabb26/Attachments/R_R_R_R_R_R_S_R_R_S_S_S_R_R__R_RjoR_R_S_R_R_S__R_S_R_R_S_RjoS_R__R_S_S_S_Rjo_R__4R_S__R_S_R_S_R_R_S__S_S_S_.pdf

И если мы добавляем еще одну область, то нарушается принцип "все со всеми" и уже в этом случае не возникает
необходимости в дополнительном цвете.

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



Спасибо за помощь.

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



Редактировалось 1 раз(а). Последний 27.11.2019 00:24.
27.11.2019 09:33
хм
впрочем, всё равно вам надо доказать именно это:
Цитата
dmix
И если мы добавляем еще одну область, то нарушается принцип "все со всеми" и уже в этом случае не возникает
необходимости в дополнительном цвете.
27.11.2019 12:46
Теорема Френсиса Гутри о 4ех красках
Цитата
zklb (Дмитрий)
вы просто в этом вопросе дилетант. можно добавлять к существующей карте сколько угодно треугольных и четырёхугольных областей и там принцип 4 красок работает. но на любой карте всегда есть либо трёх-, четырёх-, либо пятиугольная область и вот с последней и возникает самая сложность. в ней то и вся проблема.
Добрый день.

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

А в случае нарушения данного принципа уже не требуется увеличивать количество цветов для раскраски,
достаточно цветов из имеющегося набора в 4 цвета.

Принцип "все со всеми" реализуется только в форме соединения "треугольник".
см.рис Простое доказательство теоремы Френсиса Гутри

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

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

Объяснял детям - сразу поняли доказательство :)



Редактировалось 5 раз(а). Последний 29.11.2019 06:56.
27.11.2019 13:45
.
Цитата
dmix
Максимальное (max) количество цветов для раскраски областей требуется только в случае, когда каждая из областей на плоскости или поверхности шара (глобуса) имеет с каждой оставшейся общую границу, т.е. соблюдается принцип – “все со всеми”.
Данному принципу соответствует лишь одна форма соединения областей - “треугольник”:

Если карта состоит из n областей и все граничат со всеми, то требуется n красок. Это так. И в этом смысле кроме конфигурации "все со всеми" никакая другая карта не потребует n красок. Но эта конструкция не интересна, так как "все со всеми" для n > 4 не бывает.

Цитата
dmix
В случае добавления одной или более областей к форме соединения “треугольник”, нарушается принцип соединения “все со всеми” и уже не возникает необходимости увеличивать количество цветов для раскраски.

В случае добавления одной области к этой форме "треугольник" не возникает необходимости увеличивать количество цветов для раскраски. Но мы будем добавлять еще и еще; и где гарантия, что в какой-то момент времени добавляемая i-ая область не будет граничить с какими-то областями, покрашенными во все четыре цвета a, b, c, d?
27.11.2019 14:29
Теорема Френсиса Гутри о 4ех красках
Цитата
r-aax
Цитата
dmix
Максимальное (max) количество цветов для раскраски областей требуется только в случае, когда каждая из областей на плоскости или поверхности шара (глобуса) имеет с каждой оставшейся общую границу, т.е. соблюдается принцип – “все со всеми”.
Данному принципу соответствует лишь одна форма соединения областей - “треугольник”:

Если карта состоит из n областей и все граничат со всеми, то требуется n красок. Это так. И в этом смысле кроме конфигурации "все со всеми" никакая другая карта не потребует n красок. Но эта конструкция не интересна, так как "все со всеми" для n > 4 не бывает.
Совершенно верно.
Цитата
r-aax
Цитата
dmix
В случае добавления одной или более областей к форме соединения “треугольник”, нарушается принцип соединения “все со всеми” и уже не возникает необходимости увеличивать количество цветов для раскраски.

В случае добавления одной области к этой форме "треугольник" не возникает необходимости увеличивать количество цветов для раскраски. Но мы будем добавлять еще и еще; и где гарантия, что в какой-то момент времени добавляемая i-ая область не будет граничить с какими-то областями, покрашенными во все четыре цвета a, b, c, d?
Возвращаемся к началу.

Только лишь принцип "все со всеми" заставляет нас увеличивать количество цветов в наборе.
Но как и вы, в том числе, заметили, что для n > 4 "все со всеми" не бывает, где n количество областей
соединенных по вышеуказанному принципу - одна внутренняя и три внешних - т.е. форма соединения "треугольник".
см. рис. Простое доказательство теоремы Френсиса Гутри



Редактировалось 1 раз(а). Последний 29.11.2019 05:17.
27.11.2019 14:46
.
Цитата
dmix
Только лишь принцип "все со всеми" заставляет нас увеличивать количество цветов в наборе.

Это утверждение не доказано.

Цитата
r-aax
Но мы будем добавлять еще и еще; и где гарантия, что в какой-то момент времени добавляемая i-ая область не будет граничить с какими-то областями, покрашенными во все четыре цвета a, b, c, d?

Такой гарантии, кстати, нет. Возможно такая ситуация встретится, и для сохранения 4-хцветной раскраски нам придется заново перекрашивать всю карту.
27.11.2019 14:54
Теорема Френсиса Гутри о 4ех красках
Расскажу другими словами.

1. Фигура с наименьшим количеством граней, имеющая площадь, т.е. удовлетворяющая условию "область" - это "треугольник".
Точка и отрезок не имеют площади.

2. И только форма соединения областей "треугольник" требует максимального количества цветов из набора, а именно 4.
Одна внутренняя область и три внешних.
см. рис.Простое доказательство теоремы Френсиса Гутри

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

Для примера увеличим число граней на 1 - т.е. создадим четырехгранную внутреннюю область:
см.рис. Четырехгранник

Здесь мы совершенно отчетливо видим нарушение принципа "все со всеми":
добавленная область e не имеет общей границы с областью b и может принять ее цвет.
Т.е. не требуется увеличивать число цветов в наборе.
И т.д.



Редактировалось 3 раз(а). Последний 29.11.2019 05:17.
27.11.2019 15:07
.
1. Количество граней в данной теореме не при чем. Области и границы между ними могут быть произвольно криволинейными.
2. Ваша форма "треугольник" действительно требует 4 цвета.
3. Добавляя одну грань к форме "треугольник", можно не увеличивать количество цветов, их останется 4.

Про последующее добавление других граней ничего не доказано.
27.11.2019 15:10
хм
Цитата
dmix
Увеличивая количество граней мы выходим из принципа "все со всеми" и в этом случае уже не требуется еще один цвет для набора,
т.е. обходимся 4 цветами.

пока Вы не перестанете повторять эту фразу, и не докажете её - доказательства нет.
27.11.2019 15:23
Теорема Френсиса Гутри о 4ех красках
Цитата
r-aax
1. Количество граней в данной теореме не при чем. Области и границы между ними могут быть произвольно криволинейными.
2. Ваша форма "треугольник" действительно требует 4 цвета.
3. Добавляя одну грань к форме "треугольник", можно не увеличивать количество цветов, их останется 4.

Про последующее добавление других граней ничего не доказано.
Форма соединения "треугольник" специально взята в кавычки - рисуйте криволинейно, от этого суть не меняется.

Как же не доказано !?
1. При увеличении количества граней нарушается принцип "все со всеми", что вы и сами подметили.
А именно данный принцип требует увеличивать количество цветов до максимального, а именно до 4ех.

2. Вы можете бесконечно наращивать число граней, но без соблюдения принципа "все со всеми" вам не понадобится новый
цвет из набора см.п.1 поста.
27.11.2019 15:32
Браво, Михайлов
Гениально простое доказательство теоремы
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

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