3.07.4. Гомеоморфные графы. Критерий планарности

Рассмотрим две новые операции на графах.

Подразбиением ребра графа называется операция удаления ребра с добавлением новой вершины и двух ребер и . На рисунке графа это означает, что добавляется новая вершина на ребре , которое, таким образом, разбивается на два ребра (рис. 1).

Стягивание смежных вершин и графа означает удаление ребра и замена двух вершин И одной вершиной, которая соединяется ребрами со всеми вершинами графа , с которыми были смежны вершины и (рис. 2).

Графы и называются Гомеоморфными, если они могут быть получены друг из друга с помощью операций подразбиения ребер и стягивания вершин степени 2 (см. следующий рис.).

Гомеоморфными являются, в частности, любые две простые цепи, любые два простых цикла.

Теорема (Понтрягин – Куратовский). Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных или .

Теорема (Вагнер). Граф планарен тогда и только тогда, когда в нем нет подграфов, стягиваемых к графам или .

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

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