Теорема о пяти красках

В § 2 уже встречалась задача о раскраске графов. Напомним ее постановку. Пусть дана географическая карта страны, в которой имеется несколько областей. Требуется окрасить каждую область так, чтобы любые две области, граничащие между собой, были окрашены в различные цвета. При этом «граничащими» областями называются области, которые граничат по некоторой линии (а не в точке). Во введении было показано, что эта задача может быть сведена к задаче о раскраске плоского графа: имея некоторое число красок, раскрасить каждую вершину одной из этих красок таким образом, чтобы любые две смежные вершины имели различную окраску.

Задача об определении минимального числа красок, нужных для правильной раскраски графа, которую мы здесь рассмотрим, является одной из первых задач теории графов. В этой главе слово «граф» будет обозначать полностью неориентированный граф без кратных ребер.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



double arrow
Сейчас читают про: