2014 dxdy logo

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

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




 
 Проблема четырёх красок
Сообщение14.08.2017, 15:55 
Всем привет.

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

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

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

 
 
 
 Re: Проблема четырёх красок
Сообщение14.08.2017, 16:06 
Аватара пользователя
Недостаточно отсутствия 5 соприкасающихся областей. Возьмите два полных графа на 4 вершинах - ABCD и EFGH, возьмите дополнительно точку X, соедините XA, XB, XC, DE,DF, DG, XH, и попробуйте это раскрасить в четыре цвета.

 
 
 
 Re: Проблема четырёх красок
Сообщение14.08.2017, 17:06 
хм, аргумент. Пошёл думать как бы переформулировать. Кстати Вы свой граф тоже распутать не сможете, как и K₅, а потому карты по такому графу не нарисовать :)

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group