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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v
i
, G
i
.
A
A
∗
= [a
ji
]
A
∗
:= A A
∗
i := 1 n A
∗
j := 1 n A
∗
a
∗
ji
= 1 (v
j
, v
i
)
k := 1 n A
∗
a
∗
jk
:= a
∗
jk
∨ a
∗
ik
i j
A
∗
A
∗
G
s
v
1
s
v
2
s
v
3
s
v
4
-
-
v
1
v
2
v
3
v
4
A=
v
1
v
2
v
3
v
4
0 1 0 0
0 0 0 1
0 0 0 0
0 0 1 0
v
1
v
2
v
3
v
4
R=
v
1
v
2
v
3
v
4
1 1 1 1
0 1 1 1
0 0 1 0
0 0 1 1
G A
R,
ïóíêòèðîì. Ãðàô, ïîëó÷åííûé â ðåçóëüòàòå ïîäîáíîé îáðà-
áîòêè âåðøèíû vi , îáîçíà÷àåòñÿ Gi .
   Äàäèì ôîðìàëüíîå îïèñàíèå àëãîðèòìà. Ïóñòü A  ìàò-
ðèöà ñìåæíîñòè ãðàôà, A∗ = [aji ]  ìàòðèöà ñìåæíîñòè òðàí-
çèòèâíîãî çàìûêàíèÿ. Òîãäà çàïèñü àëãîðèòìà âûãëÿäèò òàê:
begin                     {ÓÎÐØÎËË}
     A∗  := A                            { Èíèöèàëèçàöèÿ A∗                    }
      for i := 1 to n do                 { Ïåðåáîð ñòîëáöîâ â A∗               }
         for j := 1 to n do              { Ïåðåáîð ñòðîê â A∗                  }
             if a∗ji = 1 then            { Åñëè åñòü äóãà (vj , vi ), òî       }
                 for k := 1 to n do { "ïðèáàâèòü" â A∗                         }
                     a∗jk := a∗jk ∨ a∗ik { ñòðîêó i ê ñòðîêå j                 }
end                    {ÓÎÐØÎËË}
   Îòëè÷èòåëüíîé îñîáåííîñòüþ àëãîðèòìà ÿâëÿåòñÿ ïîðÿäîê
îáðàáîòêè ýëåìåíòîâ A∗ ïî ñòîëáöàì. Ýòî åñòåñòâåííîå ñëåä-
ñòâèå òîãî, ÷òî îáðàáîòêà íîâîé âåðøèíû íå íà÷íåòñÿ, ïîêà íå
ïåðåáåðóòñÿ âñå äóãè, âõîäÿùèå â î÷åðåäíóþ âåðøèíó, ïðè÷åì
ïîðÿäîê ýòîãî ïåðåáîðà ìîæåò áûòü ïðîèçâîëüíûì.
   Êàê ñëåäóåò èç ïðèâåäåííîãî îïèñàíèÿ, àëãîðèòì îáåñïå-
÷èâàåò ïîëó÷åíèå òðàíçèòèâíîãî çàìûêàíèÿ âñåãî çà îäèí ïðî-
õîä (ïðîñìîòð) âåðøèí ãðàôà. Ñóùåñòâåííûì äîñòîèíñòâîì
ÿâëÿåòñÿ è òî, ÷òî ðåçóëüòàò ôîðìèðóåòñÿ ïóòåì ïðåîáðàçî-
âàíèÿ ýëåìåíòîâ ìàòðèöû A∗ áåç èñïîëüçîâàíèÿ âñïîìîãà-
òåëüíûõ äàííûõ, ò. å. àëãîðèòì "ðàáîòàåò íà ìåñòå".
  vs1     -vs2              v1   v2   v3   v4          v1   v2   v3   v4
                         v1 0     1    0    0         v1 1     1    1    1
 G                       v0      0    0    1        v0      1    1    1
                      A= v2 0    0    0    0     R= v2 0    0    1    0
                          3                            3
  s       -s             v4 0     0    1    0         v4 0     0    1    1
  v4       v3
                               Ðèñ. 2.7
    êà÷åñòâå ïðèìåðà íàéäåì òðàíçèòèâíîå çàìûêàíèå äëÿ
ãðàôà G ñ ìàòðèöåé ñìåæíîñòè A è ìàòðèöåé äîñòèæè-
ìîñòè7 R, ïðåäñòàâëåííûõ íà ðèñ 2.7. Ïðèìåíÿÿ àëãîðèòì
  7 Ìàòðèöà      äîñòèæèìîñòè ëåãêî ïîëó÷àåòñÿ íåïîñðåäñòâåííî ïî ãðàôó.



                                            40

Страницы