Проблема четырёх красок

Краткая история

Раскрашивая географическую карту естественно пользоваться по возможности меньшим количеством цветов, однако так, чтобы две страны, имеющие общую часть границы (не только общую точку), были окрашены по-разному. В 1852 году Френсис Гутри, составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану, а тот – математической общественности. Точная формулировка гипотезы опубликована А. Кэли в 1878 году. Первое доказательство появилось год спустя и принадлежало В. Кемпе. Одиннадцать лет спустя П. Хивуд обнаружил в нем ошибку. (Однако из доказательства Хивуд понял, что пяти красок действительно достаточно). За первым ошибочным доказательством последовало множество других. До середины XX века, хотя проблемой четырех красок занимались многие выдающиеся математики, положение с доказательством изменилось несущественно: идеи Дж. Д. Биркгофа позволили П. Франклину в 1913 году доказать гипотезу для карты с не более чем 25 странами. Позже это число было увеличено до 38. В 1977 году доказательство гипотезы четырех красок было наконец получено К. Аппелем и У. Хакеном и опубликовано в двух статьях. Значительную часть рутинных проверок выполнил компьютер, и это революционное нововведение в сложившуюся практику дедуктивных рассуждений в чистой математике служит основанием для некоторого естественного скептицизма по отношению к данному доказательству и по сей день.

Формулировка проблемы

Теорема (Проблема четырех красок):

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

Карта России раскрашенная в [math]4[/math] цвета

Проблема четырех красок кажется на первый взгляд изолированной задачей, мало связанной с другими разделами математики и практическими задачами. На самом деле это не так. Известно более 20 ее переформулировок, которые связывают эту проблему с задачами алгебры, статистической механики и задачами планирования.

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

Теорема (Хроматическое число планарного графа):

Хроматическое число планарного графа не превосходит 4.

4-раскраска планарного графа

Доказательство Аппеля и Хакена, в целом хотя и принято математическим сообществом, но как было сказано выше вызывает до сих пор определенный скептицизм. Дело в том, что даже сами авторы доказательства пишут следующее:

"Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно"

Говоря прямо, компьютерную часть доказательства почти невозможно проверить вручную, а традиционная часть доказательства длинна и сложна настолько, что ее никто целиком и не проверял. Не так давно появилось новое доказательство , причем та часть, которая выполнена не на компьютере, уже поддается проверке. Однако компьютерная часть все еще остается скорее предметом веры.