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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

2. Построить базу относительно вершины x7 для того же самого графа.
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
)= ∞ , L(x
2
)= ∞, L(x
3
)= ∞, L(x
4
)= ∞ ,L(x
5
)= ∞ ,L(x
6
)= ∞, L(x
7
)=0, L(x
8
)= ∞ ,
L(x
9
)= ∞ , L(x
10
)= ∞
x
7
=р,
ШАГ2.
Г(р)={x
3
, x
5
, x
6
x
8
, x
9
, x
10
},
L(x
3
)=min[∞, 0+. . .]=. . . ,
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 
2. Построить базу относительно вершины x7 для того же самого графа.
                                       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)= ∞ , L(x2)= ∞, L(x3)= ∞, L(x4)= ∞ ,L(x5)= ∞ ,L(x6)= ∞, L(x7)=0, L(x8)= ∞ ,
L(x9)= ∞ , L(x10)= ∞
x7=р,
ШАГ2.
 Г(р)={x3, x5, x6 x8, x9, x10},
L(x3)=min[∞, 0+. . .]=. . . ,

Страницы