2. Планарность и изоморфизм графов
Геометрическим графом называется граф, у которого множество вершин – множество отмеченных точек (на плоскости или в пространстве), множество дуг – множество параметризированных отрезков непрерывных кривых (на плоскости или в пространстве), концами которых является соответствующие им вершины графа.
Все графы, приведенные в этой главе на рисунках, являются геометрическими.
Теорема. Для любого графа существует изоморфный ему геометрический граф(на плоскости или в пространстве), называемый его геометрической реализацией.
Геометрический граф называется правильно реализованным (правильным), если его дуги не имеют общих точек, отличных от вершин графа. Граф называется планарным, если он допускает правильную реализацию на плоскости.
Похожесть и непохожесть однотипных объектов в математике обозначают понятием «изоморфизм»
Графы G1 = (X1,
A1) и G2 = (X2,
A2) изоморфны, если существует
взаимно однозначное соответствие между
множествами вершин X1 и
X2, такое, что любые две вершины
одного графа соединены тогда и только
тогда, когда соответствующие вершины
соединены в другом графе. Обозначают
G1
G2
Изоморфные графы отличаются только нумерацией вершин.
Пример
Графы, изображенные на рис. 15 являются изоморфными.
Рисунок 15
Теорема. Изоморфизм – отношение эквивалентности на множестве графов, т.е. оно рефлексивно, симметрично, транзитивно.
На основании приведенной теоремы очевидно, что изоморфизм определяет на множестве всех графов классы эквивалентности, так что каждому классу принадлежат взаимно изоморфные графы.
Изоморфизм является частным случаем другого более общего отношения – гомеоморфизма.
Пусть некоторый граф обладает ребром (a, b). Назовем операцией подразделения этого ребра операцию, соответствующую замене данного ребра парой ребер (a, x) и (x, b), где x – новая, не принадлежавшая данному графу, вершина.
Говорят, что граф G1 является подразделением графа G2, если G1 может быть получен из G2 выполнением 0 или более операций подразделения ребер.
Два графа G1 и G2 называются гомеоморфными, если существует общее для них подразделение G3.
Пример.
G1 |
G2 |
G3 |
Рис. 16.
На рис. 16 графы G1 и G2 не изоморфны друг другу. Они являются гомеоморфными, так как G3 является подразделением, общим для них.
Критерий планарности (теорема Понтрягина-Куратовского). Граф G планарен тогда и только тогда, когда ни один из его подграфов не гомеоморфен ни К3,3, ни К5 (рис. 17).
Граф К5. |
Граф К3,3 |
Рис. 17. Графы К5 и К3,3 Куратовского.
Назовем замкнутую область плоского графа, ограниченную ребрами и не имеющую внутри себя никаких фрагментов графа, гранью. Грани плоского графа будет соответствовать грань многогранника, построенного путем проецирования плоского графа на сферу. Эйлер доказал, что в любом плоском графе (так же, как и в любом многограннике) число вершин В минус число ребер Р, плюс число граней равняется Г 2, т. е. В-Р+Г=2 (2).
Рассмотрим некоторый плоский граф (рис. 18).
Рис. 18. Плоский граф с отмеченными гранями
Подсчитаем число ребер, вершин и граней плоского графа: P=17, B=12, Г= 7. Тогда по формуле (2) имеем 12 – 17 + 7 = 2.
Формула (2) справедлива и для графов с кратными ребрами, с петлями и с вложенными петлями (рис. 19).
Рис. 19 Произвольный плоский граф.
В этом графе имеются грани степени 1, т. е. ограниченные только одним ребром.