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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v
5
,
G
2
v
2
,
v
4
, v
5
, v
6
. G
1
G
2
A
B
v
1
v
2
v
3
v
4
v
5
a
1
a
2
a
3
a
4
A =
v
1
v
2
v
3
v
4
v
5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 1
0 0 0 0 0
1 0 0 1 0
B =
v
1
v
2
v
3
v
4
v
5
0 0 −1 0
1 0 0 0
−1 1 0 0
0 0 0 −1
0 −1 1 1
.
(n−1)/n,
(n−1):(n
2
−n+1)≈1/n
2(n−1):(n
2
−2n+2)≈2/n
n×(n−1),
i
i
è v5 , ÷òî íàõîäèòñÿ â ÿâíîì ïðîòèâîðå÷èè ñ îïðåäåëåíèåì
îðäåðåâà. Â ãðàôå G2 òàêàÿ âåðøèíà îäíà  v2 , íî èç íåå
íåò ïóòåé â âåðøèíû v4 , v5 , v6 . Îáùèì äëÿ G1 è G2 ÿâëÿåòñÿ
òî, ÷òî îáà îíè ñëàáîñâÿçíûå, à òàêèå ãðàôû íå ìîãóò èìåòü
îðèåíòèðîâàííîãî îñòîâà.

   3.2. Îïèñàíèå äåðåâüåâ
   Ìàòðè÷íîå ïðåäñòàâëåíèå. Äåðåâî, êàê è ëþáîé äðó-
ãîé ãðàô, ìîæíî îïèñàòü ñ ïîìîùüþ ìàòðèö.  êà÷åñòâå ïðè-
ìåðà íèæå ïðèâåäåíû ìàòðèöû ñìåæíîñòè A è èíöèäåíòíî-
ñòè B äëÿ îðäåðåâà, èçîáðàæåííîãî íà ðèñ. 3.4,ã :
              v1   v2   v3   v4   v5                a1 a2 a3 a4
         v1  0    0    0    0    0          v1   0 0 −1 0      
         v2  0    0    1    0    0          v2  1 0 0 0        
     A = v3 
             0    0    0    0    1     B = v3 
                                                  −1 1 0 0
                                                                  .
                                                                  
         v4   0    0    0    0    0           v4    0 0 0 −1
         v5   1    0    0    1    0           v5    0 −1 1 1

    Îòìåòèì îñîáåííîñòè òàêèõ ìàòðèö äëÿ äåðåâüåâ.
    Îòíîøåíèå ÷èñëà ðåáåð äåðåâà ê ÷èñëó åãî âåðøèí, ðàâíîå
(n−1)/n, ìèíèìàëüíî äëÿ ñâÿçíîãî ãðàôà, ïîýòîìó ìàòðèöà
ñìåæíîñòè äåðåâà âåñüìà ðàçðåæåíà (ñîîòíîøåíèå åäèíèö è
íóëåé â íåé ðàâíî (n−1):(n2 −n+1)≈1/n äëÿ îðèåíòèðîâàííîãî
äåðåâà è 2(n−1):(n2 −2n+2)≈2/n äëÿ íåîðèåíòèðîâàííîãî).
    Ìàòðèöà èíöèäåíòíîñòè äåðåâà èìååò ðàçìåð n×(n−1), ò.
å. áëèçêà ê êâàäðàòíîé, à ôàêòè÷åñêè òàêîâîé è ÿâëÿåòñÿ, åñ-
ëè ïðèíÿòü âî âíèìàíèå åå èçáûòî÷íîñòü ïî ñòðîêàì. Äåéñòâè-
òåëüíî, óäàëèâ ëþáóþ ñòðîêó, ïîëó÷àåì êâàäðàòíóþ ìàòðèöó,
ïî-ïðåæíåìó ïîëíîñòüþ õàðàêòåðèçóþùóþ ãðàô.
    Åùå îäíà îñîáåííîñòü ìàòðèöû èíöèäåíòíîñòè, êîòîðàÿ
áóäåò èñïîëüçîâàíà äàëåå, çàêëþ÷àåòñÿ â ñëåäóþùåì. Ïóòåì
ïåðåóïîðÿäî÷åíèÿ ñòðîê è ñòîëáöîâ ìàòðèöà èíöèäåíòíîñòè
ëþáîãî äåðåâà ìîæåò áûòü ïðèâåäåíà ê íèæíåé òðàïåöèåâèä-
íîé ìàòðèöå, êîãäà îäíà èç åäèíèö ñòîëáöà i íàõîäèòñÿ â
ñòðîêå i , à äðóãàÿ  â îäíîé èç íèæåëåæàùèõ ñòðîê. Â êà-
÷åñòâå îáîñíîâàíèÿ ýòîãî óòâåðæäåíèÿ ìîæíî ðàññìàòðèâàòü
ñëåäóþùèé àëãîðèòì.


                                         46

Страницы