2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Проблема четырёх красок
Сообщение14.08.2017, 15:55 


09/03/14
11
Всем привет.

Не могу понять в чём заключается проблема доказательства, что его проводят только на компьютере. Ведь если формализовать задачу, то её можно привести к теории графов. Тогда доказательство становится элементарным: полный граф K₅ невозможно распутать (по меньшей мере 2 его ребра всегда будут пересекаться), а значит области карты не могут граничить между собой по принципу "каждая с каждой" и если взять любые 5 областей на карте, то 2 из них обязательно не будут соприкасаться, что позволит их покрасить в один цвет. Таким образом достаточно четырёх красок для закраски абсолютно любой карты.

Как доказать что граф K₅ нельзя распутать? Элементарно: распутав граф K₄, мы получим 4 области, разделённые рёбрами графа. Но каждая из этих областей граничит только с тремя точками, а значит в какую бы область мы не поставили пятую точку, не пересекая уже существующих рёбер мы можем соединить её только с тремя точками графа K₄. Что бы соединить её с четвёртой точкой нужно пересечь одно из рёбер.

Так в чём проблема, почему до сих пор эту задачу решают только перебором на компьютере? Или я что-то упустил и в задаче есть ещё какое-то условие?

 Профиль  
                  
 
 Re: Проблема четырёх красок
Сообщение14.08.2017, 16:06 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Недостаточно отсутствия 5 соприкасающихся областей. Возьмите два полных графа на 4 вершинах - ABCD и EFGH, возьмите дополнительно точку X, соедините XA, XB, XC, DE,DF, DG, XH, и попробуйте это раскрасить в четыре цвета.

 Профиль  
                  
 
 Re: Проблема четырёх красок
Сообщение14.08.2017, 17:06 


09/03/14
11
хм, аргумент. Пошёл думать как бы переформулировать. Кстати Вы свой граф тоже распутать не сможете, как и K₅, а потому карты по такому графу не нарисовать :)

 Профиль  
                  
 
 Re: Проблема четырёх красок
Сообщение14.08.2017, 17:09 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
programer19, было бы очень странно, если бы я сумел привести планарный граф, для которого 4х красок недостаточно:)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group