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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

v
2
{v
1
, v
2
}.
v
1
v
2
,
v
2
v
1
.
v
2
.
v
2
v
1
.
{v
2
, v
1
}.
v
1
,
v
1
,
v
3
, v
4
, v
2
,
v
1
, v
2
, v
3
, v
4
, v
2
,
v
2
.
(v
1
,v
2
,v
4
,v
3
,v
2
,v
1
)
(v
1
,v
2
,v
3
,v
4
,v
2
,v
1
).
íó (â äàííîì ñëó÷àå ýòî ìîæåò áûòü òîëüêî v2 ) è çàíîñèì
åå â ñòåê. Óäàëÿåì ïðîéäåííîå ðåáðî {v1 , v2 }. Äëÿ ýòîãî èç
ñïèñêà ñìåæíîñòè äëÿ v1 èñêëþ÷àåì âåðøèíó v2 , à èç ñïèñ-
êà ñìåæíîñòè äëÿ v2 âåðøèíó v1 . Òåïåðü ñîñòîÿíèå ñòåêà ñî-
îòâåòñòâóåò âòîðîé ñòðîêå òàáë. 5.1, à âèä ñïèñêà ñìåæíîñòè
 âòîðîìó ñòîëáöó òàáë. 5.2. Íà âòîðîé èòåðàöèè â âåðøèíå
ñòåêà ñîäåðæèòñÿ v2 . Òåïåðü âûáèðàåì âåðøèíó èç òåêóùå-
ãî ñïèñêà ñìåæíîñòè äëÿ v2 (ñì. âòîðîé ñòîëáåö òàáë. 5.2).
Ïóñòü ýòî áóäåò âåðøèíà v1 . Çàíåñåì åå â ñòåê è óäàëèì ðåá-
ðî {v2 , v1 }. Â ðåçóëüòàòå íîâîå ñîñòîÿíèå ñòåêà ñîîòâåòñòâóåò
òðåòüåé ñòðîêå òàáë. 5.1, à âèä ñïèñêà ñìåæíîñòè  òðåòüå-
ìó ñòîëáöó òàáë. 5.2. Íà òðåòüåé èòåðàöèè ñïèñîê ñìåæíîñòè
äëÿ âåðøèíû v1 , íàõîäÿùåéñÿ â âåðõóøêå ñòåêà, îêàçàëñÿ ïó-
ñòûì. Âûòàëêèâàåì åå èç ñòåêà. Ýòî îçíà÷àåò, ÷òî â ãðàôå
íàéäåí öèêë, ñîäåðæàùèé âñå ðåáðà, èíöèäåíòíûå v1 , íî íå
ÿâëÿþùèéñÿ ýéëåðîâûì.
     Íà òðåõ ïîñëåäóþùèõ èòåðàöèÿõ â ñòåê çàíîñÿòñÿ âåðøèíû
v3 , v4 , v2 , à èç ñïèñêîâ ñìåæíîñòè óäàëÿþòñÿ âñå îñòàâøèåñÿ
ýëåìåíòû. Òàêèì îáðàçîì, ê íà÷àëó ñåäüìîé èòåðàöèè ñîäåð-
æèìîå ñòåêà âûãëÿäèò òàê: v1 , v2 , v3 , v4 , v2 , ïðè÷åì âåðøèíå
ñîîòâåòñòâóåò ñàìûé ïðàâûé ýëåìåíò v2 . Òàê êàê âñå ñïèñêè
ñìåæíîñòè òåïåðü ïóñòû, â òå÷åíèå ïîñëåäíèõ ïÿòè èòåðàöèé
(7  11) âûïîëíÿåòñÿ òîëüêî âûòàëêèâàíèå âåðøèí èç ñòåêà.
Ñïèñîê âñåõ âåðøèí, âûäàííûõ èç ñòåêà (â ïîðÿäêå âûäà÷è),
èìååò âèä (v1 ,v2 ,v4 ,v3 ,v2 ,v1 ) è, êàê íåòðóäíî çàìåòèòü, ñîîò-
âåòñòâóåò ýéëåðîâó öèêëó äàííîãî ãðàôà.
     Â ýòîì ãðàôå åñòü åùå îäèí ýéëåðîâ öèêë (v1 ,v2 ,v3 ,v4 ,v2 ,v1 ).
ßñíî, ÷òî ëþáûå äâà òàêèõ öèêëà îòëè÷àþòñÿ äðóã îò äðóãà
òîëüêî ïîðÿäêîì îáõîäà ðåáåð.

   5.2.3. Î êîëè÷åñòâå ýéëåðîâûõ ãðàôîâ
   Çàäà÷à îïðåäåëåíèÿ ÷èñëà ýéëåðîâûõ ãðàôîâ ÿâëÿåòñÿ äî-
ñòàòî÷íî ñëîæíîé. Ðàññìîòðåíèþ ýòîé, à òàêæå äðóãèõ çà-
äà÷ ïåðåñ÷åòà è ïåðå÷èñëåíèÿ ãðàôîâ ïîñâÿùåíà ðàáîòà [4].
Çäåñü îãðàíè÷èìñÿ òåîðåìîé, õàðàêòåðèçóþùåé äîëþ ýéëåðî-
âûõ ãðàôîâ â îáùåì ÷èñëå ïðîñòûõ ïîìå÷åííûõ ãðàôîâ.



                                 108

Страницы