Изменения

Перейти к: навигация, поиск

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

75 байт добавлено, 21:22, 11 ноября 2018
Нет описания правки
Очевидно, что мы не сможем рассмотреть доказательство целиком, но посмотрим на общие идеи, которые в нем используются.
Во-первых, если [[Укладка графа на плоскости|грани]] образованные нашим планарным графом не триангуляция, то есть имеют не ровно три ребра у их границ, мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут триангулированными. Если эта триангуляция графа является раскрашиваемой в <tex>4</tex> и менее цветов, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему четырех цветов для триангулированных графов, чтобы доказать это ее для всех плоских графов, и без потери общности мы предполагаем, что граф триангулирован.
Для дальнейших рассуждений нам понадобится следующее утверждение:
Из данного утверждения следует, что в графе существует вершина степени <tex>\leqslant 5</tex>.
Вернемся к доказательству нашей теоремы. Будем пытаться доказать от противного. Пусть у нас существует граф, который требует хотя бы <tex>5 </tex> цветов для раскраски. Среди всех таких графов существует минимальный, то есть такой, что удаление любой вершины из него делает его <tex>4</tex>-раскрашиваемым. Тогда в таком графе не может быть вершины степени <tex> \leqslant 3</tex>, так как иначе мы может просто удалить ее из графа, раскрасить полученный граф в <tex>4</tex> цвета, вернуть удаленную вершину и покрасить ее в один из цветов, не занятых соседями. Аналогично [[Хроматическое_число_планарного_графа#Раскраска_в_5_цветов|теореме Хивуда]] доказывается, что удалив вершину степени <tex>4</tex> также всегда можно раскрасить граф в <tex>4</tex> цвета. Следовательно и таких вершин в искомом графе нет. Для вершины степени <tex>5</tex> Кемпе попытался доказать аналогичное утверждение, но это утверждение и было опровергнуто Хивудом.
На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело с случаем вершины степени <tex>5</tex>, требуются более сложные операции, чем удаление вершины. Тогда вместо <tex>1</tex> вершины будем рассматривать связанный подграф из нескольких вершин (назовем его '''конфигурацией'''). Тогда для некоторых случаев, как и прежде, достаточно продемонстрировать, что если при удалении конфигурации граф <tex>4</tex>-раскрашиваемый, то окраска может быть изменена таким образом, что при возвращении конфигурации граф также можно раскрасить в <tex>4</tex> цвета. Конфигурации для которых это возможно назовем '''сводимыми'''. Например, конфигурация состоящая из <tex>1</tex> вершины степени <tex>\leqslant 4</tex> является сводимой (было доказано выше). '''Неизбежными ''' конфигурациями назовем такие '''множества ''' конфигураций, что хотя бы одна из конфигураций этого множества обязана быть в нашем графе.
Следовательно, Если нам осталось удастся найти набор всех неизбежных конфигураций и доказать, что с ними граф все равно <tex>4</tex>-раскрашиваем, доказательство будет завершено. Основным методом, используемым, чтобы обнаружить такой набор , является [https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) метод разрядки]
Приведем пример нахождения неизбежной конфигурации:
}}
Подобными операциями Аппелем и Хакеном было получено <tex>487</tex> неизбежных конфигураций. Некоторые из них являются сводимыми, а другие требуют механической проверки возможности <tex>4</tex>-раскраски. С помощью избавления от сводимых конфигураций и еще ряда эвристик Аппель и Хакен получили <tex>1482</tex> конфигурации, раскрашиванием которых и занимался компьютер.
== Примeчания ==
<references/>
286
правок

Навигация