Глава 4. ПЛОСКИЕ И НЕПЛОСКИЕ ГРАФЫ. ТЕОРЕМА О РАСКРАСКЕ

4.1. Введение

Настоящая глава преследует две основные цели. Первая заключается в том, чтобы найти и описать условия, при которых граф является плоским, т. е. может быть отображен на плоскость. Широко известное условие существования плоского графа задается теоремой Понтрягина — Куратовского, в которой утверждается, что плоский греф не должен содержать в качестве подграфов два графа специального типа. Другое интересное необходимое условие существования плоского графа заключается в том, чтобы он был изоморфен графу, ребра которого являются прямыми линиями. Вторая цель главы состоит в том, чтобы изучить хроматические графы и сформулировать некоторые теоремы о раскраске.

При этом будут рассматриваться задачи следующих типов.

1) Задана некоторая карта, т. е. плоский граф вместе с областями, на которые циклы графа разбивают плоскость. Определить, можно ли раскрасить этот граф цветами таким образом, чтобы ни одна пара смежных областей не была окрашена одним цветом.

2) Имеются красок. Найти условия, которым должна удовлетворять карта, - чтобы было минимальным хроматическим числом. В процессе изложения основное внимание будет уделяться вопросам существования,

а не фактическому построению схем раскраски. Понятие двойственного графа позволяет дать другое определение плоского графа. Оно оказывается также полезным при изучении задачи раскраски.