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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(v, v
0
, . . . , w, w
0
, . . . , v), p.
G
0
v
0
, w
0
, v,
w.
|adj w|≥ deg v, adj w
w.
G
0
, n+k− deg w.
n+k− deg w≥ deg v,
n+k≥ deg w+ deg v.
G
0
G
k, G
n+k≥ deg w+ deg v+2k,
deg v+ deg w≥n, n+k ≥ n+2k.
k=0. G
0
=G
¢
v G
n>3 deg v≥n/2, G
n
2
/4 n=20
G
1
C
20
,
îðãàíèçîâàòü òàê: (v, v 0 , . . . , w, w0 , . . . , v), íå èñïîëüçóÿ p. Òà-
êèì îáðàçîì, â ãàìèëüòîíîâîì öèêëå ãðàôà G0 íå ìîæåò áûòü
ôðàãìåíòîâ v 0, w0 , ò. å. çà êàæäîé âåðøèíîé, ñìåæíîé ñ v,
äîëæíà ñëåäîâàòü âåðøèíà, íå ñìåæíàÿ ñ w. Ýòî âîçìîæ-
íî ïðè óñëîâèè, ÷òî |adj w|≥ deg v, ãäå adj w  ìíîæåñòâî
âåðøèí, íå ñìåæíûõ ñ w. Êîëè÷åñòâî òàêèõ âåðøèí â ãðàôå
G0 , î÷åâèäíî, ðàâíî n+k− deg w. Ïîýòîìó ïðèâåäåííîå óñëî-
âèå ìîæíî ïåðåïèñàòü òàê: n+k− deg w≥ deg v, èëè, ñîáèðàÿ
ñòåïåíè â ïðàâîé ÷àñòè, n+k≥ deg w+ deg v. Ïðè ïîñòðîåíèè
ãðàôà G0 ñòåïåíü êàæäîé âåðøèíû ãðàôà G óâåëè÷èëàñü
íà k, çíà÷èò ïðèìåíèòåëüíî ê G íåðàâåíñòâî ïðèíèìàåò âèä
n+k≥ deg w+ deg v+2k, à ñ ó÷åòîì èñõîäíîãî ïðåäïîëîæåíèÿ
deg v+ deg w≥n, èìååì n+k ≥ n+2k. Ïîñëåäíåå íåðàâåíñòâî
óäîâëåòâîðÿåòñÿ ëèøü ïðè k=0. Ïîýòîìó G0 =G è, ñëåäîâà-
òåëüíî, èñõîäíûé ãðàô ãàìèëüòîíîâ. ¢
    Èç äîêàçàííîé òåîðåìû âûòåêàåò òåîðåìà Äèðàêà:
   Òåîðåìà 5.5 Åñëè äëÿ ëþáîé âåðøèíû v ãðàôà G ïîðÿä-
êà n>3 âûïîëíÿåòñÿ íåðàâåíñòâî deg v≥n/2, òî G  ãàìèëü-
òîíîâ ãðàô.
   Ê ñîæàëåíèþ, ýôôåêòèâíîñòü ïðèâåäåííûõ â îáåèõ òåî-
ðåìàõ êðèòåðèåâ îñòàâëÿåò æåëàòü ëó÷øåãî. Äåéñòâèòåëüíî,
òàê êàê ñóììà ñòåïåíåé âñåõ âåðøèí ãðàôà ðàâíà óäâîåííî-
ìó ÷èñëó åãî ðåáåð, òî î÷åâèäíî, ÷òî â ãàìèëüòîíîâîì ãðà-
ôå, îòâå÷àþùåì óñëîâèÿì ïîñëåäíåé òåîðåìû, äîëæíî áûòü
íå ìåíåå n2 /4 ðåáåð.  ÷àñòíîñòè, ïðè n=20 ýòî ñîñòàâëÿåò
100 ðåáåð. Îäíàêî ãðàô ñ òàêèì êîëè÷åñòâîì âåðøèí ìîæåò
áûòü ãàìèëüòîíîâûì è ïðè ñóùåñòâåííî ìåíüøåì ÷èñëå ðå-
áåð. Íàïðèìåð, â ãðàôå G1 íà ðèñ. 5.13, òàêæå èìåþùåì äâà-
äöàòü âåðøèí, âñåãî òðèäöàòü ðåáåð, è ñòåïåíè âñåõ åãî âåð-
øèí ðàâíû òðåì (à íå äåñÿòè, êàê òîãî òðåáóåò òåîðåìà), íî
îí ãàìèëüòîíîâ. Åùå áîëåå ðàçèòåëüíûì ïðèìåðîì ÿâëÿåòñÿ
ïðîñòîé öèêë C20 , â êîòîðîì òîëüêî äâàäöàòü ðåáåð, à ñòåïå-
íè âåðøèí ðàâíû äâóì. Íåñêîëüêî óòðèðóÿ ñóòü äåëà, ìîæíî
ñêàçàòü: äàííûå êðèòåðèè îòðàæàþò òîò î÷åâèäíûé ôàêò, ÷òî
ïðè îäíîì è òîì æå ÷èñëå âåðøèí ÷åì áîëüøå â ãðàôå ðåáåð,
òåì âûøå âåðîÿòíîñòü òîãî, ÷òî îí ãàìèëüòîíîâ.



                                   115

Страницы