Большая советская энциклопедия

Четырёх красок задача



Четырёх красок задача, задача, заключающаяся в доказательстве (или опровержении) следующего предложения: четырёх различных красок достаточно для того, чтобы раскрасить любую карту так, чтобы никакие две области, имеющие общий участок границы, не были окрашены в один и тот же цвет. Это предложение подтверждается во всех известных частных случаях (сообщение о его доказательстве было опубликовано лишь в 1976).

В качестве математической задачи оно было сформулировано впервые в середине 19 в. и получило широкую известность благодаря лекциям английского математика О. де Моргана. Чтобы поставить задачу с полной строгостью, надо потребовать, чтобы рассматриваемые области были ограничены простыми замкнутыми контурами (замкнутыми жордановыми кривыми). Без труда можно доказать, что пяти красок всегда достаточно для раскраски такого рода "карты". Если же соответствующую задачу формулировать для пространства, то здесь никакое число "красок" не окажется достаточным.

Лит.: Appel К., Haken W., "Bulletin of the American Mathematical Society", 1976, v. 82, ? 5, p. 711-12.


Смотрите также: