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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

T
K
T
S
T
K
T
S
+ −
e
1
e
i−1
T
K
T
S
T
K
T
S
e
1
+
+
e
2
+
+
e
3
+
+
e
4
−
−
e
5
+
+
. . .
. . .
. . .
e
i
+
−
. . .
. . .
. . .
e
k
−
+
. . .
. . .
. . .
e
i
.
±e
i
∓e
i
.
e
i
T
K
,
T
S
.
∓e
i
. e
i
T
S
T
K
.
T
S
±e
i
,
e
i
T
K
T
S
.
a b. T
S
a b.
T
K
T
K
e
k
. e
k
e
i
,
e
i
e
k
. T
S
,
e
k
e
i
.
T
S
e
i
e
k
T
S
T
0
S
,
   Îáîñíîâàíèå àëãîðèòìà. Ïóñòü TK  îñòîâíîå äåðå-
âî, ïîëó÷åííîå ñ ïîìîùüþ àëãîðèòìà Êðàñêàëà, à TS  êðàò-
÷àéøèé îñòîâ. Ñîñòàâèì óïîðÿäî÷åííûé ñïèñîê ðåáåð ãðàôà,
îòîáðàçèâ âõîæäåíèå èëè íåâõîæäåíèå ðåáðà â TK è TS çíà-
êîì + èëè − , êàê ïîêàçàíî íà ðèñ. 3.12. Ïðåäïîëîæèì, ÷òî
ó ðåáåð ñ e1 ïî ei−1 âêëþ÷èòåëüíî çíàêè äëÿ TK è TS èäåí-

         TK + + + − + . . .          + ...      − ...
            e1 e2 e3 e4 e5 . . .     ei . . .   ek . . .
         TS + + + − + . . .          − ...      + ...

                         Ðèñ. 3.12

òè÷íû, à ïåðâîå íåñîâïàäåíèå èìååò ìåñòî äëÿ ei . Õàðàêòåð
íåñîâïàäåíèÿ ìîæåò áûòü ±ei èëè ∓ei . Âåðõíèé çíàê ñîîò-
âåòñòâóåò âõîæäåíèþ (èëè íåâõîæäåíèþ) ðåáðà ei â TK , à
íèæíèé  â TS . Äîïóñòèì, ÷òî ñî÷åòàíèå çíàêîâ èìååò âèä
∓ei . Ýòî çíà÷èò, ÷òî ðåáðî ei âõîäèò â TS è íå âõîäèò â
TK . Ïîñêîëüêó â ñîîòâåòñòâèè ñ àëãîðèòìîì Êðàñêàëà î÷å-
ðåäíîå ðåáðî ïðîïóñêàåòñÿ, åñëè îíî îáðàçóåò öèêë ñ ïðåä-
øåñòâóþùèìè ðåáðàìè, ñðåäè ðåáåð TS åãî òàêæå áûòü íå
ìîæåò. Òàêèì îáðàçîì, åäèíñòâåííî âîçìîæíûì ñî÷åòàíèåì
çíàêîâ (ïðè ïåðâîì íåñîâïàäåíèè) ìîæåò áûòü ±ei , ò. å. ðåá-
ðî ei ïðèñóòñòâóåò â TK è îòñóòñòâóåò â TS . Ïóñòü êîíöàìè
ýòîãî ðåáðà ÿâëÿþòñÿ âåðøèíû a è b. Ïîñêîëüêó TS ÿâëÿ-
åòñÿ äåðåâîì, â íåì äîëæíà ñóùåñòâîâàòü åäèíñòâåííàÿ öåïü,
ñîåäèíÿþùàÿ a è b. Ñðåäè çâåíüåâ ýòîé öåïè èìååòñÿ, ïî
êðàéíåé ìåðå, îäíî ðåáðî, íå âõîäÿùåå â TK (â ïðîòèâíîì
ñëó÷àå â TK åñòü öèêë, ÷òî íåâîçìîæíî). Îáîçíà÷èì ýòî ðåá-
ðî ek .  ïîñëåäîâàòåëüíîñòè óïîðÿäî÷åííûõ ðåáåð ek ìîæåò
íàõîäèòüñÿ òîëüêî "ñïðàâà" îò ei , à ýòî çíà÷èò, ÷òî äëèíà
ei íå áîëüøå, ÷åì äëèíà ek . Ïåðåñòðîèì TS , óäàëèâ èç íåãî
ek è âêëþ÷èâ ei .  ñèëó ïîðÿäêà ñëåäîâàíèÿ ðåáåð ýòà ïåðå-
ñòðîéêà íå ìîæåò óäëèíèòü îñòîâ, à áîëåå êîðîòêèé ÷åì TS
îñòîâ ïîëó÷èòü íåâîçìîæíî. Ýòî çíà÷èò, ÷òî ei è ek èìåþò
îäèíàêîâóþ äëèíó. Â ðåçóëüòàòå ïåðåñòðîéêè âìåñòî TS ïî-
ëó÷åí îñòîâ TS0 , òàêæå ÿâëÿþùèéñÿ êðàò÷àéøèì, â êîòîðîì



                              60

Страницы