Изменения

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

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

359 байт убрано, 21:54, 11 ноября 2018
Общие идеи доказательства
На этом этапе мы и натыкаемся на самую сложную часть доказательства. Имея дело со случаем вершины степени <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> конфигурации, раскрашиванием которых и занимался компьютер.
== См. также ==
286
правок

Навигация