Основные понятия теории графов. Гладких О.Б - 30 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

30
Определение 1.36. Четверка (M, R, f, g) называется
помеченным графом, где пара функций f, g – по-
метка или распределение меток графа G = (M, R) и
f: M → S
M
(распределение меток вершин),
g: R → S
R
(распределение меток дуг).
Для вершины а
∈ M элемент f (а) называется
весом вершины а, для дуги u
∈ R элемент g (u) –
весом дуги u.
Пример 1.16.
Рис. 13.
Для графа, изображенного на рис. 13, матри-
ца C имеет вид:
C =
1 2 4
5
3
6
∞∞
⎛⎞
⎜⎟
∞∞∞∞
⎜⎟
⎜⎟
∞∞∞ ∞
⎜⎟
∞∞∞∞∞
⎜⎟
⎜⎟
∞∞∞ ∞
⎝⎠
Длина пути (x
1
, x
2
, x
5
, x
4
) равна 1 + 5 + 6 = 12.
147
тельно пересечет одну из дуг. В доказательстве
есть элементы интуитивности. Строгость достига-
ется, если пользоваться теоремой Жордана: Пусть
К – непрерывная замкнутая линия на плоскости.
Линия К делит плоскость на внешнюю и внутрен-
нюю области так, что любая непрерывная кривая,
соединяющая любую точку внутренней области с
некоторой точкой внешней области, пересекает
К.
Другое доказательство основано на следую-
щей теореме Л.Эйлера (1752), справедливой для
любого конечного плоского связанного графа:
b + r = р + 2, где b – порядок графа, р – число
его ребер и r – число его граней.
В графе b = 6, р = 9. Если бы граф был бы
плоским, то r = 11 – 6 = 5. Обозначим через
Q
k
–
число k-угольных граней графа. Тогда
r =
Q
2
+
Q
3
+ …,
2 р = 2
Q
2
+ 3
Q
3
+ …,
так как каждое ребро принадлежит двум граням.
Следовательно,
5 =
Q
2
+
Q
3
+ …,
2р = 18 = 2
Q
2
+ 3
Q
3
+ …,
Так как
Q
2
=
Q
3
= 0, то
5 =
Q
4
+
Q
5
+ …,
18 = 4
Q
4
+ 5
Q
5
+ 6
Q
6
+ …,
20 = 4
Q
4
+ 4
Q
5
+ 4
Q
6
+ …
Откуда следует, что 18 > 20. Получили противоре-
чие. 
Определение 1.36. Четверка (M, R, f, g) называется   тельно пересечет одну из дуг. В доказательстве
помеченным графом, где пара функций f, g – по-       есть элементы интуитивности. Строгость достига-
метка или распределение меток графа G = (M, R) и     ется, если пользоваться теоремой Жордана: Пусть
     f: M → SM (распределение меток вершин),         К – непрерывная замкнутая линия на плоскости.
     g: R → SR (распределение меток дуг).            Линия К делит плоскость на внешнюю и внутрен-
     Для вершины а ∈ M элемент f (а) называется      нюю области так, что любая непрерывная кривая,
весом вершины а, для дуги u ∈ R элемент g (u) –      соединяющая любую точку внутренней области с
весом дуги u.                                        некоторой точкой внешней области, пересекает К.
                                                            Другое доказательство основано на следую-
                     Пример 1.16.                    щей теореме Л.Эйлера (1752), справедливой для
                                                     любого конечного плоского связанного графа:
                                                            b + r = р + 2, где b – порядок графа, р – число
                                                     его ребер и r – число его граней.
                                                            В графе b = 6, р = 9. Если бы граф был бы
                                                     плоским, то r = 11 – 6 = 5. Обозначим через Q k –
                                                     число k-угольных граней графа. Тогда
                                                                     r = Q 2 + Q 3 + …,
                                                                     2 р = 2Q 2 + 3Q 3 + …,
                          Рис. 13.                   так как каждое ребро принадлежит двум граням.
      Для графа, изображенного на рис. 13, матри-    Следовательно,
ца C имеет вид:                                                      5 = Q 2 + Q 3 + …,
                     ⎛∞    1   2     4 ∞ ⎞                           2р = 18 = 2Q 2 + 3Q 3 + …,
                     ⎜∞    ∞   ∞     ∞ 5 ⎟⎟          Так как Q 2 =Q 3 = 0, то
                C=   ⎜
                                                                     5 = Q 4 + Q 5 + …,
                     ⎜∞    ∞   ∞     3 ∞⎟
                     ⎜                    ⎟                          18 = 4Q 4 + 5Q 5 + 6Q 6 + …,
                     ⎜∞    ∞   ∞     ∞ ∞⎟
                     ⎜∞    ∞   ∞     6 ∞ ⎟⎠                          20 = 4Q 4 + 4Q 5 + 4Q 6 + …
                     ⎝
                                                     Откуда следует, что 18 > 20. Получили противоре-
Длина пути (x1, x2, x5, x4) равна 1 + 5 + 6 = 12.    чие.

                                30                                               147

Страницы