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

   Ãðàô G1 èìååò ñåìü âåðøèí. Çíà÷èò, ñîîòâåòñòâóþùèé ãà-
ìèëüòîíîâ öèêë äîëæåí ñîñòîÿòü èç ñåìè ðåáåð, ò. å. èìåòü
äëèíó, ðàâíóþ ñåìè. Íî, èç ðèñ. 5.16 âèäíî, ÷òî ãðàô G1 äâó-
äîëüíûé è ïîýòîìó (â ñèëó òåîðåìû 1.2) ìîæåò ñîäåðæàòü
      r                        r                      r r r
                                                   r
                                                      r    r
      C          r      r     
                                                r  r
                                                           
                                                           r
        C       @
                 B     B    
         C  B @ B                                   r     r r
                                                   r ©        r
                                                              
          C  B @ B                              ©
                                                r© r
                                                ©           
                                                           r
           CCr    Br @Br                           r     r r
                                                   r ©   r ©  r
                                                              
                                                   © ©©
                                                r © r©
                                                ©           
                                                           r
                  G1                                  G2
                                   Ðèñ. 5.16

òîëüêî öèêëû ÷åòíîé äëèíû. Îòñþäà ñëåäóåò, ÷òî ãðàô íåãà-
ìèëüòîíîâ. Îáîáùàÿ, ìîæíî óòâåðæäàòü, ÷òî ëþáîé äâóäîëü-
íûé ãðàô ñ íå÷åòíûì ÷èñëîì âåðøèí íå ìîæåò áûòü ãà-
ìèëüòîíîâûì. Òàêèì îáðàçîì, ðåøàÿ çàäà÷ó âûÿâëåíèÿ íåãà-
ìèëüòîíîâîñòè äëÿ ãðàôà ñ íå÷åòíûì ÷èñëîì âåðøèí, öåëåñî-
îáðàçíî ïðîâåðèòü åãî íà äâóäîëüíîñòü, èñïîëüçóÿ àëãîðèòì,
èçëîæåííûé â ðàçä. 1.3.
   Îòìåòèì, ÷òî â îáùåì ñëó÷àå äâóäîëüíîñòü ãðàôà (â îò-
ëè÷èå îò ãðàôà G1 , ïðåäñòàâëåííîãî íà ðèñ. 5.16) íå âñåãäà
î÷åâèäíà. Òàê, ãðàô G2 íà ðèñ. 5.16 òàêæå äâóäîëüíûé, íî
÷òîáû óñòàíîâèòü ýòî, òðåáóþòñÿ íåêîòîðûå óñèëèÿ.
   Ïåðåéäåì ê àíàëèçó ãðàôà G2 , èçîáðàæåíèå êîòîðîãî íà
ðèñ. 5.16 ñîâìåùåíî ñ òðåõìåðíûì êóáîì òàê, ÷òî âåðøèíû
ãðàôà ñîâàäàþò ñ ñåðåäèíàìè ãðàíåé è ðåáåð êóáà, à òàêæå ñ
åãî âåðøèíàìè.  ïîäîáíûõ ñëó÷àÿõ ãîâîðÿò, ÷òî ãðàô óëî-
æåí íà íåêîòîðîé ïîâåðõíîñòè.  äàííîì ñëó÷àå ýòî ïîâåðõ-
íîñòü êóáà. Ëåãêî ïîäñ÷èòàòü, ÷òî ãðàô G2 èìååò 26 âåðøèí è
48 ðåáåð. Òàê êàê ÷èñëî âåðøèí ÷åòíî, âûøåîïèñàííûé ïðèåì
çäåñü íåïðèåìëåì. Ïîñòóïèì èíà÷å, íî ïðåäâàðèòåëüíî ââå-
äåì ïîíÿòèå íåçàâèñèìîãî ìíîæåñòâà âåðøèí, ïîä êîòîðûì
ñëåäóåò ïîíèìàòü ëþáîå ìíîæåñòâî âåðøèí, òàêèõ, ÷òî íèêà-
êèå äâå èç íèõ íå ñìåæíû. Íåçàâèñèìîå ìíîæåñòâî íàçûâà-
åòñÿ ìàêñèìàëüíûì, åñëè îíî íå ÿâëÿåòñÿ ñîáñòâåííûì ïîä-



                                          124