Дискретная математика. Ерош И.Л - 108 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

108
5.18. «Задача о четырех красках»
Каждой политической или административной карте можно сопо
ставить некоторый многоугольный граф. Обычно такие карты раскра
шиваются так, чтобы граничащие друг с другом два государства были
раскрашены в разные цвета. Поскольку форма ребра значения не име
ет, то плоские графы, соответствующих фрагментам таких карт, мож
но представить как графы с прямыми ребрами. Так, например, граф,
изображенный на рис. 5.11, мог бы соответствовать некоторому фраг
менту политической карты региона.
Существует мнение, что любую по
литическую карту, так же, как и лю
бой плоский граф, можно раскрасить
с использованием 4х красок, при
этом никакие две соседние страны
(или никакие две соседние грани) не
будут окрашены в один цвет. Эта за
дача называется «Задача о четырех
красках». Достаточно просто пока
зать, что четыре краски необходимы
для раскрашивания произвольного
графа. Пусть, например, имеется
фрагмент графа (рис 5.15).
Пусть некоторая область раскрашена в цвет a, тогда соседняя с ней
область должна будет раскрашиваться в другой цвет, например b, тре
тья область, соседняя и с первой и со второй, должна будет раскраши
ваться в третий цвет g. Однако есть еще четвертая область, которая
граничит со всеми тремя областями, и ее нужно раскрасить в четвер
тый цвет d. Таким образом, четыре краски необходимы для раскраши
вания произвольной карты. Но достаточно ли их? Несложно доказы
вается, что пяти красок достаточно для раскрашивания любой карты,
однако не найдено ни одного графа, для раскрашивания которого по
требовалось бы использовать пять красок. Похоже, что четыре крас
ки и необходимы, и достаточны для раскрашивания любого графа, а
следовательно, и любой политической карты.
5.19. Теорема о направленных графах
Результаты турнира, в котором отсутствуют ничьи, можно предста
вить в виде направленного графа, в котором каждой вершине соответ
ствует команда, а направление стрелки показывает, какая команда
выиграла. Пусть, например, в турнире участвуют 7 команд, а резуль
таты игр выглядят так, как это показано на рис. 5.16.
Рис. 5.15. Рисунок, поясняющий
необходимость 4Qх красок
для раскрашивания карт

Страницы