Элементы теории графов. Сюсюкалов А.И - 21 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

Составители: 

Рубрика: 

16
4. ПЛАНАРНЫЕ ГРАФЫ
4.1. Определения и свойства
Определение 4.1. Граф называется планарным или плоским,
если его можно изобразить на плоскости так, что никакие его
два ребра (за исключением рёбер, выходящих из общей верши-
ны) не имеют общих точек.
Граф, изображенный на рис. 13, а, – плоский, а на рис. 13, б
– неплоский (см. теорему 4.3).
а б
Рис. 13
Определение 4.2. Области, ограниченные ребрами графа,
называются гранями.
Число граней обозначим через
F
, число вершин
V
, а ре-
бер
E
.
Теорема 4.1 (Эйлера). Для планарного связного графа име-
ет место равенство
2
FEV
(формула Эйлера).
Д о к а з а т е л ь с т в о. Пусть граф
G
содержит циклы.
Будем удалять ребра, сохраняя связность графа, пока не полу-
чим дерево. При этом число вершин
V
не меняется, а количест-
во ребер уменьшается на одну единицу. Число граней также
уменьшается на одну единицу. То есть
FEV не меняется.
А для дерева
1
EV
и
1
F
, поэтому
2
FEV
. Теоре-
ма доказана.
Теорема 4.2. Для любого плоского графа
FE 32
.
Д о к а з а т е л ь с т в о. Пусть для
i
-й грани есть
i
E ребер,
тогда
EE
F
i
i
2
1
, так как каждое ребро учитывается дважды, но у
каждой грани не менее трех сторон, поэтому 3
i
E и
FEE
F
i
F
i
i
332
11
. Теорема доказана.

Страницы