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

íå÷åòíûì. Ïðè òàêîì õàðàêòåðå ÷åðåäîâàíèÿ â ãàìèëüòîíî-
âîì öèêëå íà 26 âåðøèí äîëæíî áûòü 13 âåðøèí ñ ÷åòíûìè è
13 ñ íå÷åòíûìè ïîìåòêàìè. Îäíàêî ïðîñòîé ïîäñ÷åò ïîêàçû-
âàåò, ÷òî â ãðàôå 14 "÷åòíûõ" è 12 "íå÷åòíûõ" âåðøèí, ò. å.
ãàìèëüòîíîâà öèêëà áûòü íå ìîæåò.
   Åñëè èñïîëüçîâàòü ïîíÿòèå äâóäîëüíîñòè, ìîæíî äàòü è
áîëåå ïðîñòîå îáîñíîâàíèå ïîëó÷åííîãî ðåçóëüòàòà. Ïîñêîëü-
êó ãðàô äâóäîëüíûé, ëþáîé öèêë â íåì, â òîì ÷èñëå è ãàìèëü-
òîíîâ, äîëæåí ñîäåðæàòü ÷åòíîå ÷èñëî âåðøèí ïðè ñòðîãîì
÷åðåäîâàíèè ïî èõ ïðèíàäëåæíîñòè ê ðàçíûì äîëÿì. Ñëåäî-
âàòåëüíî, äëÿ ãàìèëüòîíîâîñòè ãðàôà íåîáõîäèìî, ÷òîáû äîëè
èìåëè ðàâíîå ÷èñëî âåðøèí.  ðàññìàòðèâàåìîì ñëó÷àå ýòî íå
òàê, çíà÷èò, ãðàô íåãàìèëüòîíîâ.
   Âûøåèçëîæåííîå ïîçâîëÿåò ñäåëàòü âûâîä î òîì, ÷òî ëþ-
áîé äâóäîëüíûé ãðàô ñ ÷åòíûì ÷èñëîì âåðøèí ìîæåò áûòü
ãàìèëüòîíîâûì òîëüêî ïðè ðàâåíñòâå åãî äîëåé.

   5.4. Çàäà÷à êîììèâîÿæåðà
   Òàê íàçûâàåòñÿ øèðîêî èçâåñòíàÿ êëàññè÷åñêàÿ çàäà÷à èñ-
ñëåäîâàíèÿ îïåðàöèé, êîòîðàÿ â ãðàôîâîé èíòåðïðåòàöèè ôîð-
ìóëèðóåòñÿ ñëåäóþùèì îáðàçîì. Èìååòñÿ ïîëíûé ãðàô (îð-
ãðàô), çàäàííûé ìàòðèöåé âåñîâ C. Òðåáóåòñÿ íàéòè ãàìèëü-
òîíîâ öèêë ñ ìèíèìàëüíîé ñóììîé ñîñòàâëÿþùèõ åãî ðåáåð
(äóã). Åñëè òðàêòîâàòü âåñ ðåáðà ci,j ≥0 êàê ðàññòîÿíèå ìåæ-
äó âåðøèíàìè vi è vj , òî çàäà÷à çàêëþ÷àåòñÿ â îòûñêàíèè
êðàò÷àéøåãî ãàìèëüòîíîâà öèêëà.
     ëèòåðàòóðå ïî èññëåäîâàíèþ îïåðàöèé ÷àñòî ïðèâîäèò-
ñÿ ñëåäóþùàÿ ôîðìóëèðîâêà, îïðåäåëèâøàÿ íàçâàíèå çàäà÷è.
Êîììèâîÿæåð (àãåíò ïî ñáûòó) äîëæåí ïîñåòèòü n ãîðîäîâ,
íà÷èíàÿ ñ îäíîãî èç íèõ, è âåðíóòüñÿ â èñõîäíûé ïóíêò, ïî-
áûâàâ â êàæäîì òîëüêî îäèí ðàç. Äëÿ ëþáîé ïàðû ãîðîäîâ
vi è vj èçâåñòíî ðàññòîÿíèå (âðåìÿ èëè ñòîèìîñòü ïåðååçäà,
ïåðåëåòà) ci,j . Êàêèì äîëæåí áûòü êðàò÷àéøèé (íàèáîëåå äå-
øåâûé) ìàðøðóò êîììèâîÿæåðà?




                            126