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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G
v
i
v
j
, (v
i
, v
j
)
v
j
v
i
{v, w}
G n≥3 deg v+
+ deg w ≥ n G
¤ G(V, E),
deg v + deg w ≥ n
G, G
0
(V
0
, E
0
)
k
(v, p, w, . . . , v) G
0
,
v, w ∈ V, p
v w G
0
,
G
p
k w
0
∈ adj w
v
0
∈ adj v,
(v, p, w, . . . , v
0
, w
0
, . . . , v),
p
w, . . . , v
0
v
0
, . . . , w
   Ïóñòü G  îðãðàô, âåðøèíû êîòîðîãî ñîîòâåòñòâóþò ïðî-
äóêòàì vi è vj , à äóãè (vi , vj ) îòðàæàþò òîò ôàêò, ÷òî ïðî-
äóêò vj ìîæåò ïðîèçâîäèòüñÿ ïîñëå vi áåç îñòàíîâêè àïïàðà-
òóðû. Òåïåðü îòâåò íà ïîñòàâëåííûé âîïðîñ çàâèñèò îò òîãî,
ñóùåñòâóåò ëè â ãðàôå ãàìèëüòîíîâ êîíòóð èëè íå ñóùåñòâóåò.
   Ñðàâíèâàÿ îïðåäåëåíèÿ ýéëåðîâà è ãàìèëüòîíîâà öèêëîâ,
íåëüçÿ íå çàìåòèòü èõ ñóùåñòâåííîå ñõîäñòâî.  ïåðâîì ñëó÷àå
íàêëàäûâàåòñÿ òðåáîâàíèå îäíîêðàòíîãî ïðîõîæäåíèÿ êàæäî-
ãî ðåáðà ãðàôà (âåðøèíû ìîæíî ïðîõîäèòü íåîäíîêðàòíî), à
âî âòîðîì  òðåáîâàíèå îäíîêðàòíîãî ïðîõîæäåíèÿ êàæäîé
âåðøèíû. È ïîñêîëüêó äëÿ ýéëåðîâûõ öèêëîâ èìååòñÿ âåñüìà
ïðîñòîå íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå ñóùåñòâîâàíèÿ,
åñòåñòâåííî ïðåäïîëîæèòü (â ñèëó îòìå÷åííîãî ñõîäñòâà), ÷òî
è äëÿ ãàìèëüòîíîâûõ öèêëîâ åñòü ïîäîáíûé êðèòåðèé. Îä-
íàêî òàêîé êðèòåðèé íå íàéäåí. Â íàñòîÿùåå âðåìÿ èçâåñòíî
íåñêîëüêî óñëîâèé ñóùåñòâîâàíèÿ ãàìèëüòîíîâûõ öèêëîâ. Îä-
íî èç íèõ óñòàíàâëèâàåò ñëåäóþùàÿ òåîðåìà Îðå.
   Òåîðåìà 5.4 Åñëè äëÿ ëþáîé ïàðû {v, w} íåñìåæíûõ âåð-
øèí ãðàôà G ïîðÿäêà n≥3 âûïîëíÿåòñÿ íåðàâåíñòâî deg v+
+ deg w ≥ n , òî G  ãàìèëüòîíîâ ãðàô.
    ¤ Äîïóñòèì, ÷òî ñóùåñòâóåò íåãàìèëüòîíîâ ãðàô G(V, E),
â êîòîðîì äëÿ ëþáîé ïàðû íåñìåæíûõ âåðøèí âûïîëíÿåòñÿ
íåðàâåíñòâî deg v + deg w ≥ n . Áóäåì äîáàâëÿòü ê ãðàôó íî-
âûå âåðøèíû, ñîåäèíÿÿ êàæäóþ èç íèõ ñ êàæäîé âåðøèíîé
G, äî òåõ ïîð, ïîêà ïîëó÷àþùèéñÿ ïðè ýòîì ãðàô G0 (V 0 , E 0 )
íå ñòàíåò ãàìèëüòîíîâûì. Îáîçíà÷èì ÷åðåç k ìèíèìàëüíîå
êîëè÷åñòâî òàêèõ äîïîëíèòåëüíûõ âåðøèí.
    Ïóñòü (v, p, w, . . . , v)  ãàìèëüòîíîâ öèêë â ãðàôå G0 , ãäå
v, w ∈ V, à p  îäíà èç äîáàâëåííûõ âåðøèí. Çàìåòèì, ÷òî
âåðøèíû v è w íå ÿâëÿþòñÿ ñìåæíûìè íè â G0 , íè òåì áî-
ëåå, â G (â ïðîòèâíîì ñëó÷àå, ïðè óêàçàííîé ñòðóêòóðå öèê-
ëà âåðøèíà p íå íóæíà, ÷òî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ
î ìèíèìàëüíîñòè k ). Áîëåå òîãî, ëþáàÿ âåðøèíà w0 ∈ adj w
íå ìîæåò ñëåäîâàòü çà âåðøèíîé v 0 ∈ adj v, ïîòîìó ÷òî â ýòîì
ñëó÷àå öèêë ïðèíèìàåò âèä (v, p, w, . . . , v 0 , w0 , . . . , v), è òîãäà
îïÿòü âåðøèíà p îêàçûâàåòñÿ ëèøíåé. Äåéñòâèòåëüíî, åñëè
ôðàãìåíò w, . . . , v 0 "ïåðåâåðíóòü" v 0 , . . . , w , òî öèêë ìîæíî


                                  114

Страницы