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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

A
∗
:
0 1 0 0
0 0 0 1
0 0 0 0
0 0 1 0
⇒
0 1 0 1
0 0 0 1
0 0 0 0
0 0 1 0
⇒
0 1 0 1
0 0 0 1
0 0 0 0
0 0 1 0
⇒
0 1 1 1
0 0 1 1
0 0 0 0
0 0 1 0
.
A(G
1
) A(G
2
) A(G
3
) A(G
4
)
s
v
1
s
v
2
s
v
3
s
v
4
-
-
G
1
s
v
1
s
v
2
s
v
3
s
v
4
-
?
-
G
2
s
v
1
s
v
2
s
v
3
s
v
4
-
?
-
G
3
s
v
1
s
v
2
s
v
3
s
v
4
-
@
@
@
@R? ?
-
G
4
G
4
A
∗
(G)=A(G
4
)
G(V, Γ)
B⊂V, R(B)=V, ∀(B
0
⊂B) R(B
0
)6=V.
Óîðøîëëà, ïîëó÷èì ñëåäóþùèé ðÿä ìàòðèö, èëëþñòðèðóþ-
ùèé ïðîöåññ ôîðìèðîâàíèÿ ìàòðèöû òðàíçèòèâíîãî çàìûêà-
íèÿ A∗:
                                                   
   0 1 0      0       0 1 0 1       0 1 0 1       0 1 1 1
  0 0 0      1    0 0 0 1     0 0 0 1     0 0 1 1
  0 0 0      0  ⇒  0 0 0 0  ⇒  0 0 0 0  ⇒  0 0 0 0 .
   0 0 1      0       0 0 1 0       0 0 1 0       0 0 1 0
   A(G1 )             A(G2 )         A(G3 )        A(G4 )

   Ñîîòâåòñòóþùèå èì ãðàôû èçîáðàæåíû íà ðèñ. 2.8.
   vs1    -vs2       vs1    -vs2           vs1    -vs2   vs1      -vs2
                                                          @
                                                              @
   s      -s         ?
                     s      -s             ?
                                           s      -s     ?
                                                         s      @
                                                                @
                                                                R?
                                                                - s
   v4      v3        v4      v3            v4      v3    v4       v3
         G1                G2                    G3            G4
                                Ðèñ. 2.8

   Ïîñëåäíèé èç ýòèõ ãðàôîâ G4 ÿâëÿåòñÿ ãðàôîì òðàíçèòèâ-
íîãî çàìûêàíèÿ äëÿ ãðàôà íà ðèñ. 2.7. Òåïåðü, ÷òîáû ïîëó÷èòü
ìàòðèöó äîñòèæèìîñòè, äîñòàòî÷íî ðàññòàâèòü íåäîñòàþùèå
åäèíèöû íà ãëàâíîé äèàãîíàëè â ìàòðèöå A∗ (G)=A(G4 ) .


   2.8. Áàçà ãðàôà
   Áàçîé íàçûâàþò ìíîæåñòâî âåðøèí, èç êîòîðîãî äîñòèæè-
ìû âñå âåðøèíû ãðàôà, ïðè÷åì â áàçå íåò ïîäìíîæåñòâ, îá-
ëàäàþùèõ òàêèì æå ñâîéñòâîì äîñòèæèìîñòè.
   Ôîðìàëüíî áàçó ãðàôà G(V, Γ) ìîæíî îïðåäåëèòü êàê ìíî-
æåñòâî B⊂V, òàêîå, ÷òî R(B)=V, à ∀(B 0 ⊂B) R(B 0 )6=V.
   Èòàê, áàçà óäîâëåòâîðÿåò äâóì óñëîâèÿì:
    êàæäàÿ âåðøèíà ãðàôà äîñòèæèìà, ïî êðàéíåé ìåðå, èç
îäíîé âåðøèíû áàçû;
    â áàçå íåò âåðøèí, äîñòèæèìûõ èç äðóãèõ âåðøèí áàçû.
   Ïîýòîìó ìîæíî óòâåðæäàòü, ÷òî â àöèêëè÷åñêîì ãðàôå ñó-
ùåñòâóåò òîëüêî îäíà áàçà. Îíà ñîñòîèò èç âñåõ âåðøèí ñ ïîëó-


                                      41

Страницы