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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

deg v
i
/2
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
@
@
@
@
@
@
@
@
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
-
¡
¡ª
¡
¡ª
6
@
@R
@
@R
@
@
@
@
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
-
¡
¡ª
¡
¡ª
6
@
@R
@
@R
¡
¡µ
@
@I
?
¾@
@I
¡
¡µ
v
1
.
v
2
{v
1
, v
2
}
v
4
{v
2
, v
4
}, v
6
, {v
4
, v
6
},
v
1
, v
4
v
7
v
4
{v
7
, v
6
}
v
2
v
5
. v
5
, {v
7
, v
5
},
   5.2.2. Àëãîðèòì ïîèñêà ýéëåðîâà öèêëà
    Ñóùåñòâóåò î÷åíü ïðîñòàÿ è íàãëÿäíàÿ ïðîöåäóðà îòûñ-
êàíèÿ ýéëåðîâà öèêëà, èçâåñòíàÿ êàê àëãîðèòì Ôëåðè, êîòî-
ðàÿ çàêëþ÷àåòñÿ â ñëåäóþùåì. Íà÷èíàÿ ñ íåêîòîðîé âåðøè-
íû, ïðîèçâîëüíûì îáðàçîì "èäåì" ïî ñìåæíûì ðåáðàì ãðàôà,
óäàëÿÿ ïðîéäåííîå ðåáðî è âåðøèíó, ñòàâøóþ ïîñëå óäàëå-
íèÿ ðåáðà èçîëèðîâàííîé. Íå ïðîõîäèì ïî ðåáðó, åñëè ïîñëå
åãî óäàëåíèÿ ãðàô ñòàíîâèòñÿ íåñâÿçíûì. Íåòðóäíî ïîêàçàòü,
÷òî ïðîöåññ çàâåðøàåòñÿ ïîñëå îáõîäà (óäàëåíèÿ) âñåõ ðåáåð,
à çíà÷èò, è âåðøèí ãðàôà, è îáÿçàòåëüíî â èñõîäíîé âåðøèíå,
ñòåïåíü êîòîðîé ê ýòîìó ìîìåíòó ñòàíîâèòñÿ íóëåâîé. Îòìå-
òèì, ÷òî êàæäàÿ âåðøèíà (â îòëè÷èå îò ðåáåð, ïðîõîäèìûõ îä-
íîêðàòíî), âîîáùå ãîâîðÿ, ìîæåò áûòü ïðîéäåíà íåîäíîêðàò-
íî, òî÷íåå  deg vi /2 ðàç. Ïîðÿäîê, â êîòîðîì áûëè ïðîéäåíû
ðåáðà, îïðåäåëÿåò êîíôèãóðàöèþ íàéäåííîãî öèêëà.
    Ïóñòü, íàïðèìåð, òðåáóåòñÿ íàéòè ýéëåðîâ öèêë â ãðàôå,
ïðåäñòàâëåííîì íà ðèñ. 5.9,à. Íåïîñðåäñòâåííîé ïðîâåðêîé
       vr 1     vr 2          vr 1 1- vr 2             vr 1 - vr 2
        @        @             @
                               6@ 5 2 ¡@             µ@
                                                     ¡  6R r¡  ¡@I
 v3 r      @r v4 @r v5     r     R
                         v3 4 3 r¡  ªv4 @r v5   v3 r¡ @      ªv4 @r v5
    @       @              @ ¡@                     @
                                                    I ¡    ¡@ ?¡
      @r       @r            @r¡ª 6@ Rr              @rª ¾ @  R r¡µ
       v6       v7            v6       v7              v6       v7
            a                      á                        â
                               Ðèñ. 5.9
óáåæäàåìñÿ, ÷òî ñòåïåíè âñåõ âåðøèí ÷åòíû, ò. å. ãðàô ýéëå-
ðîâ.  êà÷åñòâå íà÷àëüíîé âåðøèíû âûáåðåì v1 . Íà ïåðâîé
èòåðàöèè ïåðåéäåì â âåðøèíó v2 è óäàëèì ðåáðî {v1 , v2 } 18 .
Íà âòîðîé èòåðàöèè ïåðåéäåì â âåðøèíó v4 è óäàëèì ðåá-
ðî {v2 , v4 }, íà òðåòüåé  â v6 , óäàëèâ {v4 , v6 }, çàòåì âíîâü
ïîïàäàåì â v1 , ïîòîì åùå ðàç â v4 è, íàêîíåö, â v7 . Òî,
÷òî ïîëó÷èòñÿ ïîñëå ýòîãî, ïðåäñòàâëåíî íà ðèñ. 5.9,á. Âåðøè-
íà v4 îêàçàëàñü èçîëèðîâàííîé è ìîæåò áûòü óäàëåíà. Ðåá-
ðî {v7 , v6 } ñòàëî ìîñòîì. Ïîýòîìó äîïóñòèì ïåðåõîä òîëüêî â
v2 èëè â v5 . Ïåðåéäåì â âåðøèíó v5 , óäàëèâ ðåáðî {v7 , v5 },
 18 Óäàëåííûå  ðåáðà ïðîíóìåðîâàíû è îòîîáðàæåíû òîíêèìè ëèíèÿìè
ñî ñòðåëêàìè, ïîêàçûâàþùèìè íàïðàâëåíèå îáõîäà.



                                 105

Страницы