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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

A
A
2
=A×A=[a
(2)
ij
],
a
(2)
ij
=
n
W
k=1
a
ik
a
kj
,
A
A
3
, A
4
, A
5
q.
R
q
.
R
1
=A+I, ”+”
I R
2
=R
1
+A
2
=I+A+A
2
=
=(I+A)
2
=R
2
1
R
q
=I+A+A
2
+ . . . +A
q
=(I+A)
q
=R
q
1
.
R
2
, R
3
, . . . , R
q
R
2
, R
4
, R
8
R
2
l
1
=R
2
(l−1)
1
R
2
(l−1)
1
,
l=1, 2, 3, . . .
R
q
. q
R
7
R
7
= R
4
×R
2
×R
1
=
= R
4
1
×R
2
1
×R
1
.
(v
i
, v
k
) (v
k
, v
j
)
(v
i
, v
j
).
G
ìàòðèöà ñîîòâåòñòâóåò ñèëüíîé êîìïîíåíòå è ñîñòîèò èç îäíèõ
åäèíèö, à âñå îñòàëüíûå ýëåìåíòû  íóëè.

   2.6. Ïîëó÷åíèå ìàòðèöû äîñòèæèìîñòåé
    Åñòåñòâåííûìè êîëè÷åñòâåííûìè õàðàêòåðèñòèêàìè äîñòè-
æèìîñòè ÿâëÿþòñÿ äëèíû ïóòåé ìåæäó âåðøèíàìè Ïðè ýòîì
ìàòðèöó ñìåæíîñòè A ìîæíî òðàêòîâàòü êàê ìàòðèöó äîñòè-
                                                   (2)
æèìîñòè ïðè äëèíå ïóòåé 1, à ìàòðèöó A2 =A×A=[aij ], ãäå
 (2) W
      n
aij = aik akj , êàê ìàòðèöó äîñòèæèìîñòè ïðè äëèíå ïóòåé 2
    k=1
(çäåñü è äàëåå ìàòðèöà A ðàññìàòðèâàåòñÿ êàê áóëåâñêàÿ).
Ñîîòâåòñòâåííî ìàòðèöû A3, A4, A5 è ò. ä. ìîæíî ðàññìàòðè-
âàòü êàê ìàòðèöû äîñòèæèìîñòè ïðè äëèíå ïóòåé 3, 4, 5 è ò. ä.
   Îïðåäåëèì îãðàíè÷åííóþ äîñòèæèìîñòü êàê äîñòèæè-
ìîñòü ïðè äëèíå ïóòåé íå áîëåå ÷åì q. Ñîîòâåòñòâóþùàÿ ìàò-
ðèöà íàçûâàåòñÿ ìàòðèöåé îãðàíè÷åííîé äîñòèæèìîñòè Rq .
Î÷åâèäíî, ÷òî R1 =A+I, ãäå ”+”  áóëåâñêîå ñëîæåíèå,
I  åäèíè÷íàÿ ìàòðèöà, àíàëîãè÷íî R2 =R1 +A2 =I+A+A2 =
=(I+A)2 =R21 è âîîáùå Rq =I+A+A2 + . . . +Aq =(I+A)q =Rq1 .
Âìåñòî ïîñëåäîâàòåëüíîãî âû÷èñëåíèÿ R2 , R3 , . . . , Rq ýêîíî-
ìè÷íåå ïîëó÷àòü R2 , R4 , R8 è ò. ä., èñïîëüçóÿ ñîîòíîøåíèå:
                         l    (l−1)   (l−1)
                         R21 =R21  R21   ,
ãäå l=1, 2, 3, . . . Âîçâåäåíèå â êâàäðàò ïîâòîðÿåòñÿ, ïîêà íå
áóäåò ïîëó÷åíî Rq . Åñëè q íå ÿâëÿåòñÿ ñòåïåíüþ äâîéêè, ïî-
òðåáóåòñÿ ðÿä äîïîëíèòåëüíûõ óìíîæåíèé. Íàïðèìåð, ìàò-
ðèöà R7 ìîæåò áûòü ïîëó÷åíà òàê: R7 = R4 ×R2 ×R1 =
= R41 ×R21 ×R1 .  òîì ñëó÷àå, êîãäà òðåáóåòñÿ îòûñêàòü ìàò-
ðèöó äîñòèæèìîñòè, âîçâåäåíèå â êâàäðàò ñëåäóåò âûïîëíÿòü,
ïîêà ðåçóëüòàò îïåðàöèè íå ïåðåñòàíåò èçìåíÿòüñÿ.
   Áîëåå ýôôåêòèâíîå ðåøåíèå çàäà÷è îñíîâàíî íà èñïîëü-
çîâàíèè òðàíçèòèâíîãî çàìûêàíèÿ. Ãðàô íàçûâàåòñÿ òðàíçè-
òèâíûì, åñëè ïðè íàëè÷èè äóã âèäà (vi , vk ) è (vk , vj ) â íåì
îáÿçàòåëüíî åñòü è äóãà âèäà (vi , vj ). Ïðèìåð òðàíçèòèâíîãî
ãðàôà äàí íà ðèñ. 2.5. Òðàíçèòèâíûì çàìûêàíèåì ãðàôà G


                              38

Страницы