3.08.2. Задача о раскраске географической карты

Дана географическая карта, на которой изображены страны, разделяемые границами. Требуется раскрасить карту так, чтобы страны, имеющие общие участки границы, были окрашены в разные цвета, и чтобы при этом было использовано минимальное количество цветов.

По данной карте построим граф следующим образом. Поставим в соответствие странам карты вершины графа. Если какие-то две страны имеют общий участок границы, то соответствующие им вершины соединим ребром, в противном случае – нет.

Легко видеть, что раскраске карты соответствует правильная раскраска вершин полученного графа, а минимальное количество необходимых красок равно хроматическому числу этого графа.

< Предыдущая		Следующая >