Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 66 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Для нахождения кратчайшего пути между вершинами, например x
2
и начальной x
1
последовательно используем соотношение (**):
L(x
2
’) + c(x
2
’, x
2
) = L(x
2
) = 5,
где вершина x
2
’ - это вершина, непосредственно предшествующая x
2
в
кратчайшем пути от x
1
к x
2
. Единственной такой вершиной является вершина x
7
.
Далее соотношение (**) применяем второй раз:
L(x
7
’) + c(x
7
’, x
7
) = L(x
7
) = 3.
Единственной такой вершиной является вершина x
1
. Поэтому кратчайший путь от
x
1
к x
2
есть (x
1
, x
7
, x
2
). Вершина x
1
, называемая базой и дающая все кратчайшие
пути от x
1
представляет дерево, показанное на рис. 31.
. Упражнения к п. 5.4 .
1. Найти кратчайшие пути от вершины x1 ко всем другим вершинам графа,
представленного на рисунке. Построить также базу для вершины x1.
Решение.
Построим матрицу расстояний между вершинами
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X1 0 5 14 10 0 0 0 0 0 0
X2 5 0 19 0 0 3 0 0 0 0
X3 14 19 0 6 6 5 8 0 0 0
X4 10 0 6 0 11 0 0 0 0 0
X5 0 0 6 11 0 0 10 0 7 0
X6 0 3 5 0 0 0 9 8 0 0
X7 0 0 8 0 10 9 0 3 8 14
X8 0 0 0 0 0 8 3 0 0 2
X9 0 0 0 0 7 0 8 0 0 3
X10 0 0 0 0 0 0 14 2 3 0
ШАГ1. L(x
1
)=0 , L(x
2
)= ∞, L(x
3
)= ∞, L(x
4
)= ∞ ,L(x
5
)= ∞ ,L(x
6
)= ∞, L(x
7
)= ∞ ,L(x
8
)= ∞
,L(x
9
)= ∞ ,L(x
10
)= ∞
x
4
x
3
x
2
x
1
x
5
x
6
x
7
x
8
x
9
x
10
5
14
7 11
3
8
3
2
19
5
9
3
10
6
6
10
8 14
8 
Для нахождения кратчайшего пути между вершинами, например x2 и начальной x1
последовательно используем соотношение                                            (**): L(x2’) + c(x2’, x2) = L(x2) = 5,
    где вершина x2’ - это вершина,                                 непосредственно предшествующая x2 в
кратчайшем пути от x1 к x2. Единственной такой вершиной является вершина x7.
Далее соотношение (**) применяем второй раз: L(x7’) + c(x7’, x7) = L(x7) = 3.
Единственной такой вершиной является вершина x1. Поэтому кратчайший путь от
x1 к x2 есть (x1, x7, x2). Вершина x1, называемая базой и дающая все кратчайшие
пути от x1 представляет дерево, показанное на рис. 31.
.       Упражнения к п. 5.4                                                                              .

1. Найти кратчайшие пути от вершины x1 ко всем другим вершинам графа,
представленного на рисунке. Построить также базу для вершины x1.

                                                              Решение.




                        x2         3            x6        8        x8
               5             19        5             9        3          2
                                  x3                     x7
          x1        14                         8                    14           x10
               10            6             6             10    8             3

                   x4             11           x5         7        x9



Построим матрицу расстояний между вершинами

        X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X1      0     5      14 10     0     0     0      0     0      0
X2      5     0      19 0      0     3     0      0     0      0
X3      14    19     0  6      6     5     8      0     0      0
X4      10    0      6  0      11    0     0      0     0      0
X5      0     0      6  11     0     0     10     0     7      0
X6      0     3      5  0      0     0     9      8     0      0
X7      0     0      8  0      10    9     0      3     8      14
X8      0     0      0  0      0     8     3      0     0      2
X9      0     0      0  0      7     0     8      0     0      3
X10 0         0      0  0      0     0     14     2     3      0
ШАГ1. L(x1)=0 , L(x2)= ∞, L(x3)= ∞, L(x4)= ∞ ,L(x5)= ∞ ,L(x6)= ∞, L(x7)= ∞ ,L(x8)= ∞
,L(x9)= ∞ ,L(x10)= ∞

Страницы