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

   Íèçêàÿ ýôôåêòèâíîñòü ïîäîáíûõ êðèòåðèåâ, ïî-âèäèìîìó,
îáúÿñíÿåòñÿ òåì, ÷òî ãðàíèöà ìåæäó ãàìèëüòîíîâûìè è íåãà-
ìèëüòîíîâûìè ãðàôàìè îïðåäåëÿåòñÿ íå òîëüêî âåëè÷èíîé
åãî ñâÿçíîñòè, êîòîðàÿ âî ìíîãîì îïðåäåëÿåòñÿ ñòåïåíÿìè âåð-
øèí, íî è äðóãèìè ñòðóêòóðíûìè îñîáåííîñòÿìè ãðàôà. Íà-
ãëÿäíûì ïîäòâåðæäåíèåì ýòîãî ìîæåò ñëóæèòü ñëåäóþùàÿ
òåîðåìà, ÿâëÿþùàÿñÿ îäíèì èç íàèáîëåå ýôôåêòèâíûõ êðè-
òåðèåâ, êàñàþùèõñÿ ãàìèëüòîíîâûõ ãðàôîâ.
   Òåîðåìà 5.6 Ëþáîé 4-ñâÿçíûé21 ïëàíàðíûé22 ãðàô ÿâëÿ-
åòñÿ ãàìèëüòîíîâûì.
   Â ïëàíå ðàññìîòðåíèÿ âîïðîñà î êðèòåðèÿõ ãàìèëüòîíî-
âîñòè íåñêîëüêî "óòåøàåò" ôàêò, äåêëàðèðóåìûé ñëåäóþùåé
òåîðåìîé, êîòîðàÿ îòðàæàåò òèïè÷íûé ñëó÷àé.
   Òåîðåìà 5.7 Ïî÷òè âñå ãðàôû ãàìèëüòîíîâû.
   Ýòî çíà÷èò, ÷òî ñ ðîñòîì ÷èñëà âåðøèí äîëÿ ãàìèëüòîíî-
âûõ ãðàôîâ óâåëè÷èâàåòñÿ, ñòðåìÿñü â ïðåäåëå ê 1. Òàê, èç 34
ãðàôîâ, èìåþùèõ 5 âåðøèí, òîëüêî 8 ãàìèëüòîíîâûõ (23,5%),
òîãäà êàê ñðåäè 156 ãðàôîâ ñ 6 âåðøèíàìè èõ óæå 48 (30,8%).

   5.3.2. Ìåòîäû ïîèñêà ãàìèëüòîíîâûõ öèêëîâ

   Â îñíîâå ýòèõ ìåòîäîâ ëåæèò òîò èëè èíîé ñïîñîá ðåàëèçà-
öèè ïåðåáîðà ðàçëè÷íûõ âàðèàíòîâ öåïåé. Íàèáîëåå ïðîñòûì,
íî âìåñòå ñ òåì è íàèáîëåå òðóäîåìêèì ïðåäñòàâëÿåòñÿ ðåøå-
íèå, êîãäà ïîñëå âûáîðà âåðøèíû víà÷ ðàññìàòðèâàþòñÿ ðàç-
ëè÷íûå ïåðåñòàíîâêè èç ìíîæåñòâà îñòàëüíûõ n−1 âåðøèí
è äëÿ êàæäîé ïðîâåðÿåòñÿ íàëè÷èå â ãðàôå ñîîòâåòñòâóþùåé
ãàìèëüòîíîâîé öåïè. Åñëè òàêàÿ öåïü åñòü è ïîñëåäíÿÿ âåðøè-
íà öåïè ñâÿçàíà ñ víà÷ , íàéäåí ãàìèëüòîíîâ öèêë. Î÷åâèäíî,
÷òî â õóäøåì ñëó÷àå ïðè ýòîì ìåòîäå ïîòðåáóåòñÿ ñôîðìèðî-
âàòü âñå (n−1)! ïåðåñòàíîâîê, ïðè÷åì áîëüøàÿ ÷àñòü ðàáîòû
 21 Ñâÿçíîñòü  (ðåáåðíàÿ) îïðåäåëÿåòñÿ êàê íàèìåíüøåå êîëè÷åñòâî ðå-
áåð, óäàëåíèå êîòîðûõ ïðèâîäèò ê íåñâÿçíîìó ãðàôó.
  22 Ïëàíàðíûì íàçûâàåòñÿ ãðàô, êîòîðûé ìîæåò áûòü èçîáðàæåí íà
ïëîñêîñòè òàê, ÷òî íèêàêèå äâà ðåáðà íå ïåðåñåêàþòñÿ.



                               116