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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

W
u
u
v
v
u ∈ V u
½
W
u
:= ∅; u
P red
u
:= u; u
v := v ;
P := {v};
P 6= ∅ P
if Γ(v)−P −W
v
6= ∅
u ∈ Γ(v)−P −W
v
; u
P := P +{u};
P red
u
:= v; v u
v := u; u
(P =V )and(v ∈Γ(v))
P red
u
6=∅ do
½
(u);
u:=P red
u
;
(u);
P :=P −{v};
W
v
:= ∅;
v
u := P red
v
; u
W
u
:= W
u
+{v}; v u
v := u; u
  Wu  ìíîæåñòâî âåðøèí, "ïðîçîíäèðîâàííûõ" èç u ;
  víà÷  èñõîäíàÿ âåðøèíà ïðè ïîèñêå öèêëîâ;
  v  ïîñëåäíÿÿ âåðøèíà òåêóùåé öåïè,
ìîæíî ïðåäñòàâèòü â ñëåäóþùåì âèäå:
begin              {ÃÀÌÈËÜÒÎÍ}
  for
   ½ u ∈ V do         { Âíà÷àëå äëÿ êàæäîé âåðøèíû ãðàôà u }
      Wu := ∅;      { ìíîæåñòâî ïðîçîíäèðîâàííûõ èç u ïóñòî; }
      P redu := u; { â êà÷åñòâå ïðåäøåñòâóþùåé ïðèíÿòà u. }
   v := víà÷ ; { Çà ïîñëåäíþþ âåðøèíó öåïè âçÿòà èñõîäíàÿ, }
   P := {v}; { ò. å. âíà÷àëå öåïü ñîñòîèò èç îäíîé âåðøèíû. }
   while
          P 6= ∅ do             { Âûïîëíÿòü, ïîêà P íå ïóñòî: }
     if Γ(v)−P −Wv 6= ∅ { Åñòü âîçìîæíîñòü ïðîäëèòü öåïü? }
   
                                   { "äà" }
   
            
   
               select u ∈ Γ(v)−P −Wv ; { Âûáðàòü âåðøèíó u; }
   
            
             
   
            
               P := P +{u};                  { âêëþ÷èòü â öåïü; }
   
            
             
   
            
               P redu := v;          { òåïåðü v ïðåäøåñòâóåò u; }
   
            
             
   
            
               v := u;     { äàëåå ñ÷èòàòü u ïîñëåäíåé â öåïè. }
   
             if (P =V )and(v ∈Γ(v))
   
                               íà÷
   
      then                    { íàéäåí ãàìèëüòîíîâ öèêë }
   
            
                       
                        
   
            
                       
                         while   P redu 6=∅ do { Âûâîä ñïèñêà }
             
                         ½
             
             
                 then        output(u);          { âåðøèí öåïè, }
   
            
                       
                             u:=P redu ;               { íà÷èíàÿ }
   
            
                       
                        
   
                         output(u);                { ñ êîíå÷íîé. }
   
   
   
                                  { "íåò" }
   
             
   
               P :=P −{v}; { Èñêëþ÷èòü ïîñëåäíþþ âåðøèíó; }
   
             
              
              
               Wv := ∅; { "îïóñòîøèòü" ìíîæåñòâî âåðøèí, }
   
             
   
   
                                      { ïðîçîíäèðîâàííûõ èç v ; }
   
   
      else     u := P redv ;     { u  ïðåäïîñëåäíÿÿ âåðøèíà; }
   
             
              
             
                                       { v ïðîçîíäèðîâàíà èç u; }
   
              Wu := Wu +{v};
                v := u;    { äàëåå ñ÷èòàòü u ïîñëåäíåé â öåïè. }
end.              {ÃÀÌÈËÜÒÎÍ}
   Âûÿâëåíèå íåãàìèëüòîíîâîñòè ãðàôà. Â îáùåì ñëó-
÷àå óñòàíîâèòü, ÿâëÿåòñÿ ëè ãðàô ãàìèëüòîíîâûì, êàê óæå
áûëî ïîêàçàíî â 5.3.1, äîñòàòî÷íî ñëîæíî. Îäíàêî â íåêîòî-
ðûõ ñëó÷àÿõ íåãàìèëüòîíîâîñòü ìîæíî âûÿâèòü, íå ïðèáåãàÿ
ê òðóäîåìêèì àëãîðèòìàì. Ðàññìîòðèì ïðèìåðû, èëëþñòðè-
ðóþùèå ïðîñòûå ïðèåìû ðåøåíèÿ ýòîé çàäà÷è. Ïóñòü òðåáóåò-
ñÿ îïðåäåëèòü õàðàêòåð ãðàôîâ, ïðåäñòàâëåííûõ íà ðèñ. 5.16.


                                123

Страницы