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

UptoLike

ВУЗ: 

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

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

Рубрика: 

48
Подставим в (8) последовательно r = 2, r = 3 и r = 5,
чтобы определить, для какого r это равенство вы-
полняется:
λ
2
(1) + c
24
= 1 + 7 =
λ
4
(3) = 8,
λ
5
(1) + c
54
= 3 + 4 ≠
λ
4
(3) = 8,
Таким образом, вершиной, предшествующей
вершине x
4
, является вершина x
2
.
Для вершины x
2
предшествующая ей верши-
на x
r
определяется из соотношения (2) полученно-
го при s = 2:
λ
r
(0) + c
r2
=
λ
2
(1), x
r
∈ G
–1
(x
2
), (9)
где G
–1
(x
2
) – прообраз вершины x
2
.
G
–1
(x
2
) = {x
1
}.
Подставим в (9) r = 1, чтобы определить, выполня-
ется ли это равенство:
λ
1
(1) + c
12
= 0 + 1 =
λ
2
(1) = 1.
Таким образом, вершиной, предшествующей
вершине x
2
, является вершина x
1
.
Итак, найден максимальный путь – x
1
, x
2
, x
4
,
x
3
, его длина равна 10.
10B1.10. Деревья
Определение 1.37. Неориентированным деревом
(или просто деревом) называется связный граф без
циклов. Этому определению эквивалентны, как
легко показать, следующие определения:
129
Рис. 5.10.
по всем путям ранга, не превосходящего k. Ее эле-
мент
()k
ij
c содержит стоимость прохождения из
вершины v
i
в вершину v
j
по всем путям рангов 0, 1,
..., k – 1, k.
Выведем формулу для вычисления элемента
()k
ij
c матрицы C
(k)
. По пути ранга, не большего k, из
вершины v
i
в вершину v
j
можно пройти следую-
щими способами:
1) идя из вершины v
i
в вершину v
j
по некоторому
пути ранга, не превосходящего k – 1, т.е. минуя
вершину v
k
;
2) сначала идя из v
i
в v
k
по пути ранга, не большего
k – 1, затем «покрутившись» любое число раз (а
может быть, и ни разу) по какому-либо контуру
или любому замкнутому пути из v
k
в v
k
ранга, не
большего k – 1, и, наконец, идя из вершины v
k
в
вершину v
j
по пути ранга, не большего k – 1 (см.
рисунок). 
Подставим в (8) последовательно r = 2, r = 3 и r = 5,
чтобы определить, для какого r это равенство вы-
полняется:
             λ2 (1) + c24 = 1 + 7 = λ4 (3) = 8,
             λ5 (1) + c54 = 3 + 4 ≠ λ4 (3) = 8,
       Таким образом, вершиной, предшествующей
вершине x4, является вершина x2.                                               Рис. 5.10.
       Для вершины x2 предшествующая ей верши-          по всем путям ранга, не превосходящего k. Ее эле-
на xr определяется из соотношения (2) полученно-        мент cij( k ) содержит стоимость прохождения из
го при s = 2:
                                                        вершины vi в вершину vj по всем путям рангов 0, 1,
         λr (0) + cr2 = λ2 (1), xr ∈ G –1(x2), (9)
                                                        ..., k – 1, k.
где G –1(x2) – прообраз вершины x2.
                                                                  Выведем формулу для вычисления элемента
                      G –1(x2) = {x1}.                                      (k)
                                                        cij матрицы C . По пути ранга, не большего k, из
                                                          (k )
Подставим в (9) r = 1, чтобы определить, выполня-
ется ли это равенство:                                  вершины vi в вершину vj можно пройти следую-
             λ1 (1) + c12 = 0 + 1 = λ2 (1) = 1.         щими способами:
       Таким образом, вершиной, предшествующей          1) идя из вершины vi в вершину vj по некоторому
вершине x2, является вершина x1.                               пути ранга, не превосходящего k – 1, т.е. минуя
       Итак, найден максимальный путь – x1, x2, x4,            вершину vk;
x3, его длина равна 10.                                 2) сначала идя из vi в vk по пути ранга, не большего
                                                               k – 1, затем «покрутившись» любое число раз (а
                   1.10. Деревья
                   10B
                                                               может быть, и ни разу) по какому-либо контуру
Определение 1.37. Неориентированным деревом                    или любому замкнутому пути из vk в vk ранга, не
(или просто деревом) называется связный граф без               большего k – 1, и, наконец, идя из вершины vk в
циклов. Этому определению эквивалентны, как                    вершину vj по пути ранга, не большего k – 1 (см.
легко показать, следующие определения:                         рисунок).




                            48                                                       129

Страницы