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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G
tc
G
v w
(v, w).
G
tc
G,
G,
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
B
B
B
B
BN
Z
Z
Z}
+
µ´
¶³
-
k
-
µ´
¶³
-
>
Q
Q
Q
Q
Qs
B
B
BN
G.
R
G
0
v
1
, v
2
, . . . , v
n
.
G
i
i=1, 2, . . ., n G
i−1
G
i
G
n
G
0
G
i
G
i−1
v
i
s
v
j1
s
v
j2
s
v
i
s
v
k1
s
v
k2
W
-
-
Z
Z
Z
Z~
>
>
Z
Z
Z
Z~
G
i−1
(v
j1
, v
i
) (v
j2
, v
i
),
v
i
,
(v
i
, v
k1
) (v
i
, v
k2
),
v
i
(v
j1
, v
k1
) (v
j1
, v
k2
) (v
j2
, v
k1
) (v
j2
, v
k2
),
G
tc
íàçûâàþò òðàíçèòèâíûé ãðàô Gtc , ïîëó÷åííûé ïóòåì äîáàâ-
ëåíèÿ ê G ìèíèìàëüíîãî êîëè÷åñòâà äóã, íåîáõîäèìîãî äëÿ
îáåñïå÷åíèÿ òðàíçèòèâíîñòè. Èç îïðå-              vs1
äåëåíèÿ ñëåäóåò, ÷òî åñëè â òðàíçèòèâ-          
                                                >BZ
                                                   }
íîì ãðàôå èìååòñÿ öåïü, ñâÿçûâàþùàÿ v5 s  B ZZsv2
âåðøèíó v ñ âåðøèíîé w , òî ñóùåñòâó-    Q
                                         B Q B
åò òàêæå è äóãà (v, w). Ïîýòîìó, åñ-      B Q    B 
                                        ¶³      + Q
                                                
                                           BN s   sBN¶³
                                                    Q
                                                    -  s
ëè Gtc ÿâëÿåòñÿ ãðàôîì òðàíçèòèâíî-      v4 k            v3
ãî çàìûêàíèÿ ãðàôà G, òî åãî ìàòðè-     -
                                        µ´              -
                                                       µ´
öà ñìåæíîñòè ïðàêòè÷åñêè ñîâïàäàåò ñ
ìàòðèöåé äîñòèæèìîñòè ãðàôà G, îò-           Ðèñ. 2.5
ëè÷àÿñü òîëüêî ýëåìåíòàìè ãëàâíîé äèàãîíàëè, ñîîòâåòñòâó-
þùèìè îäíîâåðøèííûì ñèëüíûì êîìïîíåíòàì6 G. Ñëåäîâà-
òåëüíî, äëÿ íàõîæäåíèÿ R ìîæíî èñïîëüçîâàòü àëãîðèòìû
îòûñêàíèÿ òðàíçèòèâíîãî çàìûêàíèÿ. Ðàññìîòðèì îäèí èç òà-
êèõ àëãîðèòìîâ.

    2.7. Àëãîðèòì Óîðøîëëà
    Ïóñòü G0  îðãðàô ñ ìíîæåñòâîì âåðøèí v1 , v2 , . . . , vn .
Àëãîðèòì Óîðøîëëà ïîçâîëÿåò ïîëó÷èòü ïîñëåäîâàòåëüíîñòü
ãðàôîâ Gi , i=1, 2, . . ., n , òàêèõ, ÷òî Gi−1 ÿâëÿåòñÿ ïîäãðà-
ôîì Gi , ïðè÷åì Gn ýòî ãðàô òðàíçèòèâíîãî çàìûêàíèÿ G0 .
Ãðàô Gi ïîëó÷àåòñÿ èç Gi−1 ïîñëå îáðàáîòêè âåðøèíû vi â
ñîîòâåòñòâèè ñî ñõåìîé, ïðåäñòàâëåííîé íà ðèñ. 2.6.
    vj1                  vk1           Ïóñòü, íàïðèìåð, â ãðàôå Gi−1
        s
        Z
                     -s          ñóùåñòâóþò äóãè (vj1 , vi ) è (vj2 , vi ),
                    
                     >
          Z                     âõîäÿùèå â âåðøèíó vi , è äóãè
            Z
            Z
            ~ s                 (vi , vk1 ) è (vi , vk2 ), âûõîäÿùèå èç
            >vZ
            
              i Z               íåå. Òîãäà ïðè îáðàáîòêå âåðøèíû
                   Z
        
        s            ~Ws
                     Z
                     -           vi êàæäàÿ ïàðà äóã (îäíà âõîäÿùàÿ,
    vj2                  vk2     äðóãàÿ èñõîäÿùàÿ) "ïîðîæäàåò" òðå-
           Ðèñ. 2.6              òüþ äóãó, êîòîðàÿ ñîåäèíÿåò íà÷àëî
                                 ïåðâîé äóãè ïàðû ñ êîíöîì âòîðîé
äóãè.  ïðåäñòàâëåííûé íà ðèñóíêå ãðàô äîáàâëÿþòñÿ ÷åòû-
ðå äóãè (vj1 , vk1 ) , (vj1 , vk2 ) , (vj2 , vk1 ) è (vj2 , vk2 ), èçîáðàæåíûå
   6Â   ìàòðèöå ñìåæíîñòè ãðàôà Gtc ýòè ýëåìåíòû ðàâíû íóëþ.


                                     39

Страницы