Теорема 4-х красок
В 1852 году при раскрашивании карты Британии студент Ф. Гутри выдвинул гипотезу: что любую карту можно раскрасить четырьмя цветами, при условии, чтобы никакие две смежные области (имеющие общую границу) не оказались окрашенными в один и тот же цвет.
После многих неудачных попыток доказательства гипотезы для любого числа стран, математики решили доказать её, начиная с малых натуральных чисел. П. Франклин в 1913 году доказал гипотезу для карты в которой не более чем 25 стран, со временем он увеличил это число до 38. С увеличением числа стран лавинообразно росло и число различных вариантов их взаимного расположения, и число вариантов раскраски карт. Проблема становилась совершенно неприступной.
Её удалось решить только в 1976 году.
В1976 г. К. Аппель и В. Хакен из Иллинойского университета совершили революцию – в доказательстве математической теоремы они применили компьютер. Потратив свыше тысячи часов машинного времени, перебрав громадное число вариантов, компьютер подтвердил справедливость гипотезы о 4-х красках.
Вековая проблема была решена.
Проблему 4-х красок можно сформулировать в терминах графов, если заменить карту
графом, расположенным на плоскости
Будем изображать страны кружками,
а границы – отрезками.
