3.07.4. Гомеоморфные графы. Критерий планарности
Рассмотрим две новые операции на графах.
Подразбиением ребра графа называется операция удаления ребра с добавлением новой вершины и двух ребер и . На рисунке графа это означает, что добавляется новая вершина на ребре , которое, таким образом, разбивается на два ребра (рис. 1).
Стягивание смежных вершин и графа означает удаление ребра и замена двух вершин И одной вершиной, которая соединяется ребрами со всеми вершинами графа , с которыми были смежны вершины и (рис. 2).
Графы и называются Гомеоморфными, если они могут быть получены друг из друга с помощью операций подразбиения ребер и стягивания вершин степени 2 (см. следующий рис.).
Гомеоморфными являются, в частности, любые две простые цепи, любые два простых цикла.
Теорема (Понтрягин – Куратовский). Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных или .
Теорема (Вагнер). Граф планарен тогда и только тогда, когда в нем нет подграфов, стягиваемых к графам или .
Отметим в заключение, что стягивая любое ребро планарного графа, вновь получим планарный граф. Если же дан непланарный граф, то стянув одно или несколько ребер можно получить планарный граф.
< Предыдущая | Следующая > |
---|