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

ìíîæåñòâîì íåêîòîðîãî íåçàâèñèìîãî ìíîæåñòâà âåðøèí. Â
ãðàôå G2 åñòü äâà òàêèõ ìíîæåñòâà. Îäíî èç íèõ V1 âêëþ-
÷àåò âñå âåðøèíû, íàõîäÿùèåñÿ â ñåðåäèíå ðåáåð êóáà, äðóãîå
V2 ñîñòîèò èç âåðøèí, ñîâïàäàþùèõ ñ âåðøèíàìè êóáà è ñå-
ðåäèíàìè åãî ãðàíåé. Ðàññìîòðèì ìíîæåñòâî V1 . Êàæäàÿ èç
âõîäÿùèõ â íåãî âåðøèí èíöèäåíòíà ÷åòûðåì ðåáðàì, èç êî-
òîðûõ òîëüêî äâà ìîãóò ïðèíàäëåæàòü ãàìèëüòîíîâó öèêëó.
Òàê êàê |V1 |=12, òî îáùåå ÷èñëî ðåáåð, íå âõîäÿùèõ â öèêë
òîëüêî ïî ìíîæåñòâó V1 , ðàâíî 24. Îñòàâøèõñÿ 24 ðåáåð èç 48
íå äîñòàòî÷íî äëÿ îðãàíèçàöèè ãàìèëüòîíîâà öèêëà, êîòîðûé
â äàííîì ãðàôå äîëæåí áû (ïî ÷èñëó âåðøèí) èìåòü äëèíó
26. À ýòî çíà÷èò, ÷òî ãðàô G2 íåãàìèëüòîíîâ.
    Îðèãèíàëüíûé ñïîñîá ðåøåíèÿ çàäà÷è, èñïîëüçóþùèé îñî-
áåííîñòè ñòðóêòóðû ãðàôà, ïðåäëîæèë Þ.Í.Çàâàðîâñêèé24 .
                          z
                          6

                                 t[0;0;2] t[0;1;2] t[0;2;2]
                     [1;0;2]   
                                    t t
                                                   
                           t
                            t        t       [1;2;2]
             [2;0;2] t
                                 t[0;0;1] [0;1;1]
                                             t           t[0;2;1]
                                ©
                           ©t©                   t
             [2;0;1] t©©       t         t
                                 t[0;0;0] [0;1;0]
                                             t        t
                                                           [0;2;0]-
                                ©         ©                       y
                           ©t©      ©t©         t
                     t©©
                     ©         t©©        t  [1;2;0]
                                          
                  ©
              ©
              ¼© [2;0;0] [2;1;0] [2;2;0]
             x
                                Ðèñ. 5.17
   Ñâÿæåì ñ êóáîì, íà êîòîðîì óëîæåí ðàññìàòðèâàåìûé ãðàô,
äåêàðòîâó ñèñòåìó êîîðäèíàò ñ åäèíè÷íûì îòðåçêîì, ñîîò-
âåòñòâóþùèì ðåáðó ãðàôà, êàê ïîêàçàíî íà ðèñ. 5.17. Òîãäà
êàæäîé âåðøèíå ìîæíî ïðèïèñàòü ÷èñëîâóþ ïîìåòêó, ðàâíóþ
ñóììå åå êîîðäèíàò. ßñíî, ÷òî ïðè ïåðåõîäå èç îäíîé âåðøè-
íû â äðóãóþ, ñìåæíóþ ñ íåé, çíà÷åíèå ïîìåòêè óâåëè÷èâàåò-
ñÿ èëè óìåíüøàåòñÿ íà åäèíèöó, ñòàíîâÿñü ëèáî ÷åòíûì, ëèáî
 24 Äîöåíò  êàôåäðû âûñøåé ìàòåìàòèêè Âñåðîññèéñêîãî çàî÷íîãî
ôèíàíñîâî-ýêîíîìè÷åñêîãî èíñòèòóòà.



                                        125