Элементы теории графов. Домнин Л.Н. - 95 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

s
(37)
s
(30)
s
(44)
s
(22)
s
(13)
s
(19)
s
(37)
s
(19)
s
(7)
s
(5)
s
(14)
s
(10)
s
(0)
-
-
-
-
-
@
@
@
@I 666
¾ @
@
@
@I
-
6
6 6
@
@
@
@I
@
@
@
@I
@
@
@
@I
6
¾ -
6
6
¢
¢
¢
¢
¢
¢
¢
¢¸
¡
¡
¡
¡µ
@
@
@
@I 6
¡
¡
¡
¡µ
¡
¡
¡
¡µ
¡
¡
¡
¡µ
¾
min[14+5]=
min[19;11+10]=
min[7; 16+5]=
min[9+5]=
min[8+5; 11+7]=
min[26+10; 3+19; 13+13]=
min[18+19; 30+14]=
min[30+10; 15+22]=
min[21+19; 17+13; 19+37]=
min[8+37; 12+37; 14+30]=
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
v
1
5
∗
10
∗
19
∗
7
∗
v
2
14
∗
16 9
∗
8
∗
v
3
11 26 30
v
4
18
∗
21
v
5
3
∗
v
6
11
v
7
30
v
8
13 17
∗
v
9
15
∗
v
10
8
v
11
19 12
v
12
14
∗
v
13
Ñòðîêà, â êîòîðîé îí íàõîäèòñÿ, îïðåäåëÿåò ïðåäïîñëåäíþþ
âåðøèíó êðàò÷àéøåãî ïóòè.  ñòîëáöå, ñîîòâåòñòâóþùåì ýòîé
âåðøèíå, âíîâü èùåì ïîìå÷åííûé ýëåìåíò  ïîëó÷àåì òðåòüþ
                                 12
                                  -
                (37)
                   s            -(30)
                                  s                 -(44)
                                                      s
                   I
                   @
                   6         19       6I
                                       @      14      6
                     @ 15              17@ 21          8
                       @                  @
                          @(22)s¾     s(13) @(19)
                                               s    - s(37)
                                  13 6         6 18 6
  à                30      ¢¢̧ 63
                                       I
                                       @
                                        @ 8 14
                                       11              30
                         ¢                @
                      26¢ s(19)        (7) @ s(5) - s(14)
                                      s¾
                       ¢ ¡
                         µ@     I     6 16¡¡µ     9
                      ¢ ¡11 @ 19 7          5
                     ¢¡           @      ¡
                 s¢¡
                   ¾         10     @s¡
                (10)                 (0)

            v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12              v13
      v1     0 5∗ 10∗        19∗ 7∗
      v2         5       14∗      16 9∗ 8∗
      v3            10        11              26      30
      v4    min[14+5]= 19                        18 ∗
                                                          21
      v5    min[19;11+10]= 19                 3∗

      v6          min[7; 16+5]= 7         11
  á
      v7                  min[9+5]= 14            30
      v8               min[8+5; 11+7]= 13 13              17∗
      v9         min[26+10; 3+19; 13+13]= 22          15∗
      v10                    min[18+19; 30+14]= 37               8
      v11                        min[30+10; 15+22]= 37 19       12
      v12                     min[21+19; 17+13; 19+37]= 30      14∗
      v13                          min[8+37; 12+37; 14+30]=     44

                               Ðèñ. 4.14
(îò êîíöà) âåðøèíó êðàò÷àéøåãî ïóòè è ò. ä., ïîêà ïîìå÷åí-
íûì íå îêàæåòñÿ ýëåìåíò â ïåðâîé ñòðîêå ìàòðèöû.



                                      95

Страницы