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

UptoLike

103
Граф типа А Граф типа B
Рис. 5.7. Примеры неплоских графов
с минимальным числом вершин
На рис. 5.7 приведены два графа, которые не являются плоскими.
Назовем их графами типа A и типа B.
Для произвольных графов введем операцию сжатия на графе. Пусть
между двумя вершинами графа имеется путь, проходящий только че
рез вершины степени 2 (рис. 5.8)
Заменим этот путь одним ребром, соединяющим А с В. Такая про
цедура называется сжатием на графе. Куратовский показал, что про
цедура сжатия на графе не меняет свойство графа быть плоским, то
есть: если граф был плоским, то после сжатия он останется плоским,
а если был не плоским, то останется не плоским.
Теорема Куратовского. Для того чтобы граф G был плоским, не+
обходимо и достаточно, чтобы после всех операций сжатия на гра+
фе внутри графа G не было бы графов типа A или типа B.
5.14. Проецирование графа на сферу
Для плоских графов сформулировано несколько очень интересных
теорем, например такая.
Теорема о прямых ребрах плоского графа. Любой плоский граф мо+
жет быть расположен на плоскости так, чтобы все его ребра были
прямыми.
Рис. 5.8. Сжатие графа