Изображения страниц
Текст статьи Беве Л. Любая карта может быть раскрашена в четыре цвета // Квант. — 1977. — № 1. — С. 60.
Так называется заметка, появившаяся в сентябре 1976 года в журнале Американского математического общества «Bulletin of American Mathematical Society». Это сообщение обратило на себя внимание профессиональных математиков и любителей математики всего мира: знаменитая проблема четырёх красок решена!
Более ста лет эта проблема дразнила воображение математиков своей формулировкой — не менее простой, чем формулировка Великой теоремы Ферма, и при этом более наглядной; работа над этой проблемой стимулировала создание столь популярной сейчас и важной для приложений теории графов.
Наш журнал неоднократно рассказывал о проблеме четырёх красок.
Вот несколько эпизодов из столетней истории этой проблемы.
1840 год. Немецкий астроном и геометр А. Мёбиус доказал, что «на плоскости нельзя начертить пять областей так, чтобы каждые две из них имели общую границу». Эта нетрудная теорема — прелюдия к проблеме четырёх красок.
1852 год. Английский математик Де Морган пишет своему другу и коллеге В. Гамильтону о задаче, придуманной одним из его студентов: «Любую карту на сфере можно раскрасить не более чем в четыре цвета так, чтобы любые две соседние страны были раскрашены в разные цвета». Четверть века об этой задаче никто не вспоминал.
1878 год. С трибуны Британского географического общества известный английский математик А. Кэли вновь формулирует проблему четырёх красок (и добавляет, что сам вот уже несколько дней как не может решить её — это происходило почти сто лет тому назад!).
С тех пор эта проблема (или гипотеза) приобрела широкую и до некоторой степени нездоровую известность. «Гипотезу четырёх красок можно с полным правом назвать ещё «болезнью четырёх красок», так как она во многом похожа на заболевание...» Ею «переболели» тысячи любителей и математиков, в том числе весьма известных (О. Веблен, Ф. Франклин и т. д.).
1880 год. Одна из первых «жертв» эпидемии — английский адвокат А. Кемпе публикует доказательство гипотезы четырёх красок в серьёзном математическом журнале, и в течение 10 лет (!) проблема считается решённой.
1890 год. П. Хивуд находит в работе Кемпе ошибку и доказывает, что любая карта на сфере может быть правильно раскрашена пятью красками («правильно» означает «так, чтобы никакие две соседние страны не были окрашены в один цвет»). Одновременно Хивуд ставит общую задачу о раскраске карт на более сложных поверхностях, чем сфера, — на «сферах с ручками» (на торе, «кренделе» и т. п.), находит формулу для числа красок в зависимссти от числа «ручек» и доказывает (как выяснилось, неверно) эту формулу. Случай тора был однако рассмотрен Хивудом до конца и безошибочно.
Хотя история доказательства формулы Хивуда растянулась на 70 лет, всё же в 1968 году оно было завершено для всех поверхностей — кроме сферы! Проблема четырёх красок по-прежнему казалась неприступной.
Разумеется, упомянутая выше работа американских математиков Аппеля и Хакена, доказавших знаменитую гипотезу (замечательно, что в доказательстве «принимала участие», и весьма существенное, ЭВМ), будет подвергнута учёными многих стран тщательной проверке. Мы надеемся вернуться к этой теме в будущем.