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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G A
G
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
s
v
6
s
v
7
s
v
8
s
v
9
s
v
10
@
@
@R
@
@
@
H
H
H
H
H
HY
?
Y
O
1
A
A
A
A
A
AK
1
?
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
A =
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 0 0
0 1 0 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1 0
0 1 0 0 1 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
V
i
v
3
, v
6
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
V
i
1 3 3 0 2 3 0 2 2 3 2 V
0
={v
3
, v
6
}
2 3 3 0 3 0 0 3 2 V
1
={v
4
, v
7
, v
8
}
3 3 1 0 2 0 V
2
={v
5
, v
10
}
4 2 1 0 V
3
={v
9
}
5 1 0 V
4
={v
2
}
6 0 V
5
={v
1
}
O(v
i
) 5 4 0 1 2 0 1 1 3 2
V
i
v
4
, v
7
, v
8
   Ïîêàæåì íà ïðèìåðå ñïîñîá îòûñêàíèÿ ïîðÿäêîâîé ôóíê-
öèè, îñíîâàííûé íà èñïîëüçîâàíèè ìàòðèöû ñìåæíîñòè è èç-
âåñòíûé êàê àëãîðèòì Äåìóêðîíà.
   Ïóñòü ãðàô G è åãî ìàòðèöà ñìåæíîñòè A âûãëÿäÿò, êàê
ïîêàçàíî íà ðèñ. 1.19. Ïîäñ÷èòàåì ÷èñëî åäèíèö â êàæäîì
ñòîëáöå ìàòðèöû è çàïèøåì íàéäåííûå çíà÷åíèÿ â ïåðâîé
                   v1           vs2           vs3                         v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
              1 s                                                                                    
                                 Y
                                 HH @                            v1      0 0 0 0 0 0 0 0 0 0
                                    HH                      v2     1 0 0 0 0 0 0 0 0 0
                                             H    @
  v10 s                                          @
                                                     R
                                                     @
                                                     Hsv4         v3    0 0 0 1 0 0 1 1 0 0         
       AK                                                    v4     0 1 0 0 1 0 0 0 0 1
         A                                                                                         
 G                                                               v5     0 0 0 0 0 0 0 0 1 0
      sA                                          s?     A=   v6     0 0 0 1 0 0 1 1 0 0
   v9 ?                                            
                                                    1
                                                        v5                                          
      O A                                                  v7    0 0 0 0 1 0 0 0 1 0         
               A                                            v8     0 1 0 0 1 0 0 0 0 1
                  As  s                   s                 v9
                                                                      
                                                                          1 1 0 0 0 0 0 0 0 0
                                                                                                       
                  v8Y v7                       v6
                                                                  v10     1 0 0 0 0 0 0 0 1 0
                                                 Ðèñ. 1.19
ñòðîêå òàáë. 1.1. Çàôèêñèðóåì â ñòîëáöå Vi âåðøèíû v3 , v6 ñ
íóëåâîé ñóììîé è îòìåòèì òðåòüþ è øåñòóþ ñòðîêè ìàòðè-
öû. Âíîâü ïîäñ÷èòàåì ÷èñëî åäèíèö â ñòîëáöàõ, íå ó÷èòûâàÿ
                                                                           Òàáëèöà 1.1
                Èòå-
                ðàöèè      v1   v2 v3 v4      v5 v6 v7 v8
                                                 v10       Vi     v9
                  1        3    3 0 2         3 0 2 2
                                                  2 V0 ={v3 , v6 }3
                  2        3    3     0       3     0 0           3
                                                  2 V1 ={v4 , v7 , v8 }
                  3        3    1             0                   2
                                                  0 V2 ={v5 , v10 }
                  4        2    1                    V3 ={v9 }    0
                  5        1    0                    V4 ={v2 }
                  6        0                         V5 ={v1 }
                O(vi )     5     4 0 1 2 0 1 1 3 2

ïðè ýòîì ñîäåðæèìîå îòìå÷åíûõ ñòðîê. Ðåçóëüòàòû çàïèøåì
âî âòîðîé ñòðîêå òàáëèöû, îïóñêàÿ íóëè, ïîëó÷åííûå íà ïåð-
âîì øàãå. Â ñòîëáåö Vi çàíîñèì âåðøèíû ñ íóëåâîé ñóììîé
v4 , v7 , v8 è îòìå÷àåì â ìàòðèöå ñîîòâåòñòâóþùèå ñòðîêè. Ïî-
âòîðÿåì îïèñàííûå äåéñòâèÿ, ïîêà íå áóäóò îáðàáîòàíû âñå
âåðøèíû. Äëÿ çàâåðøåíèÿ ïðîöåññà òðåáóåòñÿ åùå ÷åòûðå èòå-
ðàöèè (ñì. òàáë. 1.1). Â ðåçóëüòàòå ïîñëåäíèé ñòîëáåö òàáëèöû


                                                      29

Страницы