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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

C.
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
C
=
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
∞ 34 ∞ 7 2 38 ∞ ∞ ∞ ∞
34 ∞ 5 ∞ 30 ∞ 22 ∞ ∞ ∞
∞ 5 ∞ ∞ ∞ 25 17 ∞ ∞ ∞
7 ∞ ∞ ∞ 3 ∞ ∞ 13 23 ∞
2 30 ∞ 3 ∞ 20 ∞ 10 ∞ ∞
38 ∞ 25 ∞ 20 ∞ ∞ ∞ 14 14
∞ 22 17 ∞ ∞ ∞ ∞ ∞ ∞ 35
∞ ∞ ∞ 13 10 ∞ ∞ ∞ 23 ∞
∞ ∞ ∞ 23 ∞ 14 ∞ 23 ∞ 8
∞ ∞ ∞ ∞ ∞ 14 35 ∞ 8 ∞
.
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
p
1 34 ∞ 7 2 38 ∞ ∞ ∞ ∞ v
1
2 30 ∞ 3 20 ∞ 10 ∞ ∞ v
5
3 30 ∞ 20 ∞ 10 23 ∞ v
4
4 30 ∞ 20 ∞ 23 ∞ v
8
5 30 25 ∞ 14 14 v
6
6 30 25 ∞ 8 v
9
7 30 25 35 v
10
8 5 17 v
3
9 17 v
2
6v
1
6v
1
6v
1
v
1
6v
1
6v
1
6v
1
6v
1
6v
1
6v
5
v
6
v
5
v
5
6v
10
v
5
6v
4
6v
6
v
3
v
3
v
6
v
9
v
i
,
v
i
   Ðàññìîòðèì åùå îäèí âàðèàíò ðåàëèçàöèè àëãîðèòìà, îñíî-
âàííûé íà òåõíèêå ïîìåòîê âåðøèí, íå òðåáóþùèé ïðåäâàðè-
òåëüíîé ñîðòèðîâêè ðåáåð è èñïîëüçóþùèé ìàòðèöó âåñîâ C.
Ïîêàæåì ýòó òåõíèêó íà ïðèìåðå ãðàôà, èçîáðàæåííîãî íà
ðèñ. 3.10. Ìàòðèöà âåñîâ ýòîãî ãðàôà èìååò âèä:
                         v1     v2   v3     v4   v5   v6     v7   v8   v9     v10
                                                                                
                 v1      ∞      34   ∞       7    2   38     ∞    ∞    ∞      ∞
                 v2     34     ∞     5     ∞    30   ∞      22   ∞    ∞      ∞
                 v3    ∞        5   ∞      ∞    ∞    25     17   ∞    ∞      ∞
                                                                                
                 v4     7      ∞    ∞      ∞     3   ∞      ∞    13   23     ∞
                                                                                
                 v      2      30   ∞       3   ∞    20     ∞    10   ∞      ∞
             C = v5     38     ∞    25     ∞    20   ∞      ∞    ∞    14     14  .
                   6                                                            
                 v7    ∞       22   17     ∞    ∞    ∞      ∞    ∞    ∞      35 
                                                                                
                 v8    ∞       ∞    ∞      13   10   ∞      ∞    ∞    23     ∞
                                                                                
                 v9      ∞      ∞    ∞      23   ∞    14     ∞    23   ∞       8
                 v10     ∞      ∞    ∞      ∞    ∞    14     35   ∞     8     ∞
   Ïðîöåññ ïîëó÷åíèÿ îñòîâà îòîáðàæåí â òàáë. 3.7. Ñòîëáöû
òàáëèöû ñîäåðæàò ÷èñëîâûå ïîìåòêè (âðåìåííûå è ïîñòîÿí-
íûå), ïðèñâàèâàåìûå âåðøèíàì ïðè âûïîëíåíèè àëãîðèòìà.

                                                                                Òàáëèöà 3.7
     Èòåðà-
      öèè       v1   v2      v3      v4      v5       v6       v7      v8       v9      v10     p
       1             34      ∞       7       2        38         ∞     ∞        ∞       ∞       v1
       2             30      ∞       3                20         ∞     10       ∞       ∞       v5
       3             30      ∞                        20         ∞     10       23      ∞       v4
       4             30      ∞                        20         ∞              23      ∞       v8
       5             30      25                                  ∞              14      14      v6
       6             30      25                                  ∞                      8       v9
       7             30      25                                  35                             v10
       8             5                                           17                             v3
       9                                                        17                              v2
                     6 v1    6 v1    6 v1    v1       6 v1      6 v1   6 v1     6 v1    6 v1
      pred            6 v5     v6      v5              v5     6 v10     v5       6 v4    6 v6
                       v3                                         v3              v6      v9

   Çíà÷åíèå ïîìåòêè ëþáîé âåðøèíû vi , åùå íå âêëþ÷åííîé
â îñòîâ, ðàâíî äëèíå ðåáðà, ñâÿçûâàþùåãî vi ñ áëèæàéøåé
âåðøèíîé, óæå âîøåäøåé â îñòîâ. Íà êàæäîé èòåðàöèè â îñòîâ


                                            67

Страницы