Математическое моделирование на графах. Часть 1. Берцун В.Н. - 49 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Глава 2. Плоские и планарные графы 49
они имеют хотя бы одно общее ребро.
В качестве грани можно рассматривать
и часть плоскости, расположенную вне
плоского графа. Такую плоскость на-
зывают бесконечной или внешней гра-
нью. Грань может содержать дерево.
На рис. 2.2 изображена бесконечная
грань. Примеры граней приведены на
рис. 2.3.
F
E
H
C
A
F
x
z
C
D
A
B
D
B
E
P
(A, D, C) – не грань,
(A, B, C) – грань
z – грань степени 4,
x – грань степени 6
(A, B, C, D, P) –
внешняя грань
Рис. 2.3
Утверждение 2.1 (формула Эйлера). Если плоский связный граф
имеет n вершин, m ребер и f граней, то
n – m + f = 2. (1)
Доказательство. Рассмотрим плоский связный граф. Преобразу-
ем его в дерево, содержащее все его вершины. Для этого будем уда-
лять те ребра, которые разомкнут простые
циклы (см., например, рис. 2.4).
Тогда получится граф без перегородок
и связный. Каждое удаление ребра
уменьшает число граней на I, так как раз-
мыкается простой цикл либо из двух цик-
лов образуется один. Таким образом, раз-
ность m – f сохраняется. В полученном
дереве пусть n
1
– число вершин, m
1
– число ребер, f
1
– число граней.
Тогда m – f = m
1
– f
1
= m
1
– 1, так как в дереве одна грань. По опреде-
CD
A
B
Рис. 2.2
Рис. 2.4

Страницы