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

UptoLike

ВУЗ: 

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

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

Рубрика: 

140
Дана матрица
1
0 2 0 0
2
0 0 1 0
3
1 0 0 1
4
3 1 0 0
1 2 3 4
Постройте орграф, для которого данная мат-
рица является матрицей смежности. Найдите мат-
рицу инцидентности орграфа.
Решение.
Для построения орграфа его вершине одно-
значно сопоставим точку на плоскости. Данная
матрица смежности имеет четыре строки и четыре
столбца, следовательно, в орграфе четыре верши-
ны: 1, 2, 3, 4.
Проанализируем элементы матрицы:
а
11
= 0 – при вершине 1 нет петель;
а
12
= 2 – из вершины 1 выходят две стрелки к вер-
шине 2;
а
13
= 0 – из 1 не выходит ни одной стрелки к вер-
шине 3;
а
14
= 0 – из 1 не выходит ни одной стрелки к вер-
шине 4;
а
21
= 0 – из 2 не выходит ни одной стрелки к вер-
шине 1;
а
22
= 0 – при 2 не петель;
37
Рассмотрим подробно работу алгоритма
Форда – Беллмана для этого примера. Значения
индексов
λ
i
(k) будем заносить в таблицу индексов
(табл. 1.2).
Шаг 1. Введем число вершин графа n = 5. Матрица
весов этого графа имеет вид:
C =
1 3
8 7 1
1 5
2
4
∞
∞∞
⎛⎞
⎜⎟
∞∞
⎜⎟
⎜⎟
∞
∞∞ −
⎜⎟
∞
∞∞∞
⎜⎟
⎜⎟
∞
∞∞ ∞
⎝⎠
.
Шаг 2. Положим Uk = 0U,
λ
1
(0) = 0,
λ
2
(0) =
λ
3
(0) =
λ
4
(0) =
λ
5
(0) = ∞.
Эти значения занесем в первый столбец табл. 1.2.
Шаг 3.
Uk = 1U.
λ
1
(1) = 0.
Равенство (1) для k = 1 имеет вид:
λ
i
(1) =
51
min
≤≤ j
{
λ
j
(0) + c
ji
}.
λ
2
(1) = min{
λ
1
(0) + c
12
;
λ
2
(0) + c
22
;
λ
3
(0) + c
32
;
λ
4
(0) + c
42
;
λ
5
(0) + c
52
;} =
= min{0 + 1;
∞ + ∞; ∞ + ∞; ∞ + ∞; ∞ + ∞} = 1.
λ
3
(1) = min{
λ
1
(0) + c
13
;
λ
2
(0) + c
23
;
λ
3
(0) +
+ c
33
;
λ
4
(0) + c
43
;
λ
5
(0) + c
53
;} =
= min{0 +
∞ ; ∞ + 8; ∞ + ∞; ∞ + 2; ∞ + ∞} = ∞ . 
     Дана матрица                                         Рассмотрим подробно работу алгоритма
                                                    Форда – Беллмана для этого примера. Значения
                1   0   2     0   0
                                                    индексов λi (k) будем заносить в таблицу индексов
                2   0   0     1   0
                                                    (табл. 1.2).
                3   1   0     0   1
                                                    Шаг 1. Введем число вершин графа n = 5. Матрица
                4   3   1     0   0
                    1   2     3   4
                                                    весов этого графа имеет вид:
                                                                          ⎛∞        1   ∞    ∞    3⎞
     Постройте орграф, для которого данная мат-                           ⎜∞        ∞   8    7    1 ⎟⎟
рица является матрицей смежности. Найдите мат-                       C = ⎜⎜ ∞       ∞   ∞ 1      −5 ⎟
                                                                                                       .
рицу инцидентности орграфа.                                               ⎜                          ⎟
                                                                          ⎜∞        ∞   2 ∞       ∞⎟
                      Решение.                                            ⎜∞        ∞   ∞    4    ∞ ⎟⎠
                                                                          ⎝
       Для построения орграфа его вершине одно-
значно сопоставим точку на плоскости. Данная        Шаг 2. Положим k = 0,
                                                                        U       U




матрица смежности имеет четыре строки и четыре          λ1 (0) = 0, λ2 (0) = λ3 (0) = λ4 (0) = λ5 (0) = ∞.
столбца, следовательно, в орграфе четыре верши-     Эти значения занесем в первый столбец табл. 1.2.
ны: 1, 2, 3, 4.                                     Шаг 3. k = 1.
                                                            U    U




       Проанализируем элементы матрицы:                   λ1 (1) = 0.
а11 = 0 – при вершине 1 нет петель;                 Равенство (1) для k = 1 имеет вид:
а12 = 2 – из вершины 1 выходят две стрелки к вер-                   λi (1) = 1min    {λj (0) + cji}.
                                                                              ≤ j ≤5
          шине 2;
а13 = 0 – из 1 не выходит ни одной стрелки к вер-        λ2(1) = min{λ1(0) + c12; λ2(0) + c22;
          шине 3;                                        λ3(0) + c32; λ4(0) + c42; λ5(0) + c52;} =
а14 = 0 – из 1 не выходит ни одной стрелки к вер-        = min{0 + 1; ∞ + ∞; ∞ + ∞; ∞ + ∞; ∞ + ∞} = 1.
          шине 4;                                        λ3(1) = min{λ1(0) + c13; λ2(0) + c23; λ3(0) +
а21 = 0 – из 2 не выходит ни одной стрелки к вер-        + c33; λ4(0) + c43; λ5(0) + c53;} =
          шине 1;
                                                         = min{0 + ∞ ; ∞ + 8; ∞ + ∞; ∞ + 2; ∞ + ∞} = ∞ .
а22 = 0 – при 2 не петель;


                            140                                                         37

Страницы