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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Q=[q
ij
]
|G| q
ij
=1,
v
i
v
j
, q
ij
=0
Q, R,
Q
R. Q(v
i
)
q
ij
=1, v
j
∈Q(v
i
), q
ij
=0
Q(v
1
) = {v
1
, v
5
, v
6
},
Q(v
2
) = {v
1
, v
2
, v
5
, v
6
},
Q(v
3
) = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
Q(v
4
) = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
},
Q(v
5
) = {v
1
, v
5
, v
6
},
Q(v
6
) = {v
1
, v
5
, v
6
},
=⇒
v
i
Q
v
i
R, Q = R
T
⊗ R⊗Q
v
1
v
2
v
3
v
4
v
5
v
6
v
1
v
5
v
6
v
2
v
3
v
4
R⊗Q =
v
1
v
2
v
3
v
4
v
5
v
6
∼
v
1
v
5
v
6
v
2
v
3
v
4
.
v
i
v
j
v
i
v
i
R⊗Q
   Ìàòðèöó îáðàòíûõ äîñòèæèìîñòåé Q=[qij ] îïðåäåëèì
êàê êâàäðàòíóþ (0,1)-ìàòðèöó ïîðÿäêà |G| , â êîòîðîé qij =1,
åñëè âåðøèíà vi äîñòèæèìà èç vj , è qij =0  â ïðîòèâíîì
ñëó÷àå. Äèàãîíàëüíûå ýëåìåíòû â Q, êàê è â R, ðàâíû 1.
   Ìàòðèöà Q ìîæåò áûòü ïîëó÷åíà òåì æå ñïîñîáîì, ÷òî è
ìàòðèöà R. Èùåì ìíîæåñòâà Q(vi ) äëÿ âñåõ âåðøèí ãðàôà è
ïîëàãàåì qij =1, åñëè vj ∈Q(vi ), è qij =0  â ïðîòèâíîì ñëó÷àå:
                                          
 Q(v1 ) = {v1 , v5 , v6 },                        
                                                     1 0 0 0 1 1
                                                                 
 Q(v2 ) = {v1 , v2 , v5 , v6 },           
                                          
                                          
                                                  1 1 0 0 1 1 
 Q(v3 ) = {v1 , v2 , v3 , v4 , v5 , v6 },          1 1 1 1 1 1 
                                            =⇒ Q =              
                                                    1 1 1 1 1 1 .
 Q(v4 ) = {v1 , v2 , v3 , v4 , v5 , v6 }, 
                                                               
 Q(v5 ) = {v1 , v5 , v6 },                
                                                    1 0 0 0 1 1
                                                    1 0 0 0 1 1
 Q(v6 ) = {v1 , v5 , v6 },
   Îäíàêî èç îïðåäåëåíèé ÿñíî, ÷òî ñòîëáåö vi â ìàòðèöå Q
ñîâïàäàåò ñî ñòðîêîé vi â ìàòðèöå R, ïîýòîìó Q = RT .
   Ïðîöåäóðà îòûñêàíèÿ ñèëüíûõ êîìïîíåíò ìîæåò áûòü ñäå-
ëàíà áîëåå íàãëÿäíîé è ýôôåêòèâíîé, åñëè èñïîëüçîâàòü ââå-
äåííûå âûøå ìàòðèöû è îïåðàöèþ èõ ïîýëåìåíòíîãî óìíîæå-
íèÿ ⊗ . Ìàòðèöà R⊗Q íåñåò èíôîðìàöèþ îáî âñåõ ñèëüíûõ
êîìïîíåíòàõ ãðàôà:
                    v1 v2   v3   v4   v5   v6                  v1 v5 v6 v2   v3   v4
                                                                                    
          v1        1 0     0    0    1    1          v1       1 1 1 0       0    0
          v2       0 1     0    0    0    0         v5      1 1 1 0       0    0    
          v        0 0     1    1    0    0         v6      1 1 1 0       0    0    
    R⊗Q = v3                                    ∼                                   .
            4   
                   0 0     1    1    0    0    
                                                     v2   
                                                              0 0 0 1       0    0    
                                                                                       
          v5        1 0     0    0    1    1          v3       0 0 0 0       1 1
          v6        1 0     0    0    1    1          v4       0 0 0 0       1 1
   Äåéñòâèòåëüíî, ñòðîêà vi ñîäåðæèò åäèíèöû â òåõ ñòîëá-
öàõ vj , äëÿ êîòîðûõ âûïîëíÿåòñÿ óñëîâèå âçàèìíîé äîñòè-
æèìîñòè ñ vi è êîòîðûå íàðÿäó ñ vi âõîäÿò â ñîñòàâ îäíîé
è òîé æå ñèëüíîé êîìïîíåíòû. ßñíî, ÷òî ñòðîêè (è ñòîëáöû)
ìàòðèöû, ñîîòâåòñòâóþùèå âåðøèíàì îäíîé è òîé æå ñèëüíîé
êîìïîíåíòû, äîëæíû áûòü èäåíòè÷íû. Ïîýòîìó ïóòåì ïåðå-
ñòàíîâêè ñòðîê è ñòîëáöîâ ìàòðèöó R⊗Q ìîæíî ïðèâåñòè ê
áëî÷íî-äèàãîíàëüíîìó âèäó, êîãäà êàæäàÿ äèàãîíàëüíàÿ ïîä-


                                                37

Страницы