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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

¤ T
v
T
1
=T −v
u
T
2
=T
1
−u
T,
n−1
T
n−1
n−1 n. ¢
s
v
3
s
v
4
s
v
2
s
v
1
s
v
5
s
v
7
s
v
6
A
A
A
s
u
2
s
u
3
s
u
1
s
u
7
s
u
4
s
u
5
s
u
6
A
A
A
e
1
e
2
e
3
e
4
e
5
e
6
e
1
e
4
e
2
e
5
e
6
e
3
B =
v
1
v
2
v
3
v
4
v
5
v
6
v
7
1 1 1 0 0 0
1 0 0 0 0 0
0 0 0 1 0 0
0 1 0 1 0 0
0 0 0 0 1 0
0 0 1 0 1 1
0 0 0 0 0 1
B =
u
1
(v
2
)
u
2
(v
3
)
u
3
(v
4
)
u
4
(v
5
)
u
5
(v
7
)
u
6
(v
6
)
u
7
(v
1
)
1 0 0 0 0 0
0 1 0 0 0 0
0 1 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 1 1 1
1 0 1 0 0 1
B B
1→7, 2→1, 3→2, 4→3, 5→4, 7→5
2→3, 3→6, 4→2, 5→4, 6→5.
T
1
=T −v T
1
v T.
    ¤ Ïóñòü T  çàäàííîå äåðåâî. Âûáèðàåì ëþáóþ âèñÿ÷óþ
âåðøèíó v è ïðèñâèâàåì åé (è èíöèäåíòíîìó ðåáðó) íîìåð 1.
Çàòåì ðàññìàòðèâàåì äåðåâî8 T1 =T −v è âûïîëíÿåì ñ íèì òó
æå îïåðàöèþ. Òåïåðü óæå äðóãàÿ âèñÿ÷àÿ âåðøèíà u ïîëó÷àåò
âìåñòå ñ èíöèäåíòíûì åé ðåáðîì íîìåð 2. Íà ñëåäóþùåì øà-
ãå èìååì äåðåâî T2 =T1 −u è ò.ä. Îäíîâðåìåííî ñ îáðàáîòêîé
âåðøèí è ðåáåð ôîðìèðóåì ñòîëáöû ìàòðèöû èíöèäåíòíîñòè.
Âûáðàííîé âåðøèíå ñîîòâåòñòâóåò åäèíèöà íà ãëàâíîé äèàãî-
íàëè. Âòîðàÿ (íèæåëåæàùàÿ) åäèíèöà â ñòîëáöå ïîÿâëÿåòñÿ,
êîãäà ñîîòâåòñòâóþùàÿ âåðøèíà äåðåâà T, ñòàâøàÿ âèñÿ÷åé,
âûáèðàåòñÿ íà î÷åðåäíîì øàãå. Ïðîöåññ çàâåðøàåòñÿ çà n−1
øàãîâ, ïðè÷åì íà ïîñëåäíåì øàãå äåðåâî Tn−1 ñîñòîèò èç îä-
íîãî ðåáðà, êîíöû êîòîðîãî ïîëó÷àþò íîìåðà n−1 è n. ¢
    êà÷åñòâå ïðèìåðà íà ðèñ. 3.6 äàíû äâà âàðèàíòà íóìåðà-
öèè îäíîãî è òîãî æå ãðàôà: íà ðèñ. 3.6,à  ïåðâîíà÷àëüíàÿ,
                      vs3  vs4                       us 2  us 3
                                                         
                v2 s    sv1 sv5     u1 s               su7 su4
                        A                               A 
                     s A s                          s A s
                     v7 v6                           u5 u6
                       à                               á
                               Ðèñ. 3.6
à íà ðèñ. 3.6,á  íóìåðàöèÿ, ïîëó÷åííàÿ îïèñàííûì ñïîñîáîì.
Ñîîòâåòñòâóþùèå ìàòðèöû èíöèäåíòíîñòè ïðèâåäåíû íèæå:
                e1   e2   e3   e4   e5   e6                            e1   e4   e2   e5   e6   e3
                                                                                                
      v1        1    1    1    0    0    0            u1 (v2 )         1    0    0    0    0    0
      v2       1    0    0    0    0    0           u2 (v3 )        0    1    0    0    0    0 
      v3       0    0    0    1    0    0           u3 (v4 )        0    1    1    0    0    0 
                                                                                                
 Bà = v 4      0    1    0    1    0    0      Bá = u4 (v5 )        0    0    0    1    0    0 
                                                                                                
      v5       0    0    0    0    1    0           u5 (v7 )        0    0    0    0    1    0 
      v6       0    0    1    0    1    1           u6 (v6 )        0    0    0    1    1    1 
      v7        0    0    0    0    0    1            u7 (v1 )         1    0    1    0    0    1
Ôàêòè÷åñêè, äëÿ ïîëó÷åíèÿ Bá â ìàòðèöå Bà âûïîëíåíà ïå-
ðåñòàíîâêà ñòðîê ïî ñõåìå: 1→7, 2→1, 3→2, 4→3, 5→4, 7→5
è ïåðåñòàíîâêà ñòîëáöîâ ïî ñõåìå: 2→3, 3→6, 4→2, 5→4, 6→5.
  8 Çäåñüè äàëåå çàïèñü T1 =T −v îçíà÷àåò, ÷òî äåðåâî T1 ïîëó÷åíî
ïóòåì óäàëåíèÿ âåðøèíû v è èíöèäåíòíîãî åé ðåáðà â äåðåâå T.


                                                47

Страницы