286
правок
Изменения
Нет описания правки
[[Файл:Раскраска_планарного_графа_в_4_цвета.png|230px|thumb|right|4-раскраска планарного графа]]
В таком виде в <tex>1977</tex> году проблема четырех красок была доказана К. Аппелем и У. Хакеном. Значительную часть проверок выполнил компьютер, из-за чего доказательство было принято не всеми математиками. Доказательство необычайно велико. ''"Читатель должен разобраться в <tex>50</tex> страницах текста Само доказательство имеет невероятные размеры, и диаграмм, <tex>85</tex> страницах с почти <tex>2500</tex> дополнительными диаграммами, <tex>400</tex> страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в <tex>24</tex> леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала <tex>1200</tex> часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше."'' Очевидно, что из-за его сложности доказательства мы не сможем рассмотреть его целиком, но посмотрим на общие идеи, которые в нем используются.
Во-первых, если [[Укладка графа на плоскости|грани]] образованные нашим планарным графом не триангуляция (то есть имеют не ровно три ребра у их границ), мы можем добавлять ребра без внедрения новых вершин до тех пор, пока все грани не станут триангулированными. Если полученный граф является раскрашиваемым в не более чем <tex>4</tex> цвета, то и исходный граф раскрашиваем так же (так как удаление ребер не увеличивает хроматическое число). Поэтому достаточно доказать теорему для триангулированных графов, и без потери общности мы предполагаем, что граф триангулирован.
