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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

a∈P, d,
P ={a, b, c, d}.
f, (a, b, c, d, f).
Γ(f)
d
Γ(d)={c, f}. c∈P,
f
d
c.
(a, b), c
b. b
c e, e
b
e.
Γ(e)={c, d} c,
(a, b, e, c).
(a, b, e, c, d, f),
(f, a),
(a, b, e).
Γ(e) d
(a, b, e, d, f, c)
(c, a).
a.
(a, b, e, c, d, f, a) (a, b, e, d, f, c, a),
P
P red
u
u
ñïèñêå âåðøèíà a∈P, ïîýòîìó áåðåì âòîðóþ  d, ñ ðåçóëüòà-
òîì P ={a, b, c, d}. Íà ÷åòâåðòîì øàãå, ïîñòóïàÿ àíàëîãè÷íî,
äîáàâëÿåì âåðøèíó f, è öåïü ïðèíèìàåò âèä (a, b, c, d, f ).
    Äàëüíåéøåå íàðàùèâàíèå ñòàíîâèòñÿ íåâîçìîæíûì, òàê
êàê âñå âåðøèíû ìíîæåñòâà Γ(f ) óæå ñîäåðæàòñÿ â ñôîðìè-
ðîâàííîé öåïè. Ïîýòîìó âîçâðàùàåìñÿ ê âåðøèíå d è âíîâü
àíàëèçèðóåì åå ñïèñîê ñìåæíîñòè Γ(d)={c, f }. Çäåñü c∈P, à
âåðøèíà f òîëüêî ÷òî ïðîçîíäèðîâàíà, è çíà÷èò, "êàíäèäà-
òîâ" äëÿ ïðèñîåäèíåíèÿ ê öåïè íåò. Èñêëþ÷àåì d è âîçâðà-
ùàåìñÿ ê âåðøèíå c. Ñ íåé ñèòóàöèÿ ïîâòîðÿåòñÿ, ïîýòîìó
ïîñëå ñåäüìîé èòåðàöèè öåïü ñîêðàùàåòñÿ äî äâóõ âåðøèí è
ïðèíèìàåò âèä (a, b), ïðè÷åì âåðøèíà c ïîìå÷åíà êàê ïðî-
çîíäèðîâàííàÿ èç b. Ñïèñîê ñìåæíîñòè âåðøèíû b ñîäåðæèò
âåðøèíû c è e, èç êîòîðûõ òîëüêî e íå ïðîçîíäèðîâàíà èç
b è íå ñîäåðæèòñÿ â òåêóùåé öåïè. Ïîýòîìó ñëåäóåò ïåðåé-
òè ê âåðøèíå e. Íà äåâÿòîì øàãå èç äâóõ ïîäõîäÿùèõ âåð-
øèí Γ(e)={c, d} âûáèðàåì c, ïîñëå ÷åãî öåïü âûãëÿäèò êàê
(a, b, e, c). Åùå äâå èòåðàöèè (10 è 11) ïðîäëåâàþò öåïü äî ãà-
ìèëüòîíîâîé, êîòîðàÿ èìååò âèä (a, b, e, c, d, f ), è ïîñêîëüêó â
ãðàôå åñòü äóãà (f, a), ïîëó÷àåì ïåðâûé ãàìèëüòîíîâ öèêë.
    Äàëåå ñëåäóþò èòåðàöèè, ñîêðàùàþùèå öåïü äî òåõ ïîð,
ïîêà â ñïèñêå ñìåæíîñòè ïîñëåäíåé âåðøèíû íå íàéäåòñÿ ïîä-
õîäÿùåãî ïðîäîëæåíèÿ. Òàêàÿ ñèòóàöèÿ íàñòóïàåò íà øàãå 15,
êîãäà öåïü ïðèíèìàåò âèä (a, b, e). Èç äâóõ âåðøèí ìíîæåñòâà
Γ(e) îäíà åùå íå èñïîëüçîâàíà. Ýòî âåðøèíà d . Âûáðàâ åå,
â èòîãå ïîñëå øàãà 19 ïîëó÷àåì åùå îäíó ãàìèëüòîíîâó öåïü
(a, b, e, d, f, c) è ñîîòâåòñòâóþùèé öèêë, òàê êàê â ãðàôå åñòü
äóãà (c, a).
    Äàëüíåéøèå äåéñòâèÿ ïðèâîäÿò òîëüêî ê ñîêðàùåíèþ öå-
ïè. Ïðîöåññ çàâåðøàåòñÿ íà øàãå 25, êîãäà â öåïè îñòàåòñÿ
òîëüêî èñõîäíàÿ âåðøèíà a. Òàêèì îáðàçîì, îêîí÷àòåëüíî
èìååì äâà öèêëà: (a, b, e, c, d, f, a) è (a, b, e, d, f, c, a), ÷òî ñîâ-
ïàäàåò ñ ðåçóëüòàòîì, ïîëó÷åííûì àëãåáðàè÷åñêèì ñïîñîáîì.
    Ôîðìàëèçîâàííîå îïèñàíèå ðàññìîòðåííîãî ñïîñîáà ïîèñ-
êà ãàìèëüòîíîâûõ öèêëîâ, â êîòîðîì:
   P  ìíîæåñòâî âåðøèí, âêëþ÷åííûõ â ôîðìèðóåìóþ öåïü;
   P redu  âåðøèíà, ïðåäøåñòâóþùàÿ âåðøèíå u â öåïè;


                                 122

Страницы