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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

(v
5
, v
2
, v
7
, v
6
, v
3
, v
1
),
(v
1
, v
2
, v
4
,
v
6
, v
1
, v
4
, v
7
, v
5
, v
2
, v
7
, v
6
, v
3
, v
1
)
v∈V ;
v→S;
S6=∅
Γ(s
1
)6=∅ s
1
u∈Γ(s
1
);
u→S;
Γ(s
1
) := Γ(s
1
)−{u};
Γ(u) := Γ(u)−{s
1
}
(
S→v;
(v)
S.
êàê ïîêàçàíî íà ðèñ.5.9,â. Òåïåðü "îñòàòîê" ãðàôà  ïðîñòàÿ
öåïü (v5 , v2 , v7 , v6 , v3 , v1 ), ñëåäîâàòåëüíî, äàëüíåéøèå ïåðåõî-
äû îïðåäåëåíû îäíîçíà÷íî. Îêîí÷àòåëüíî ïîëó÷àåì (v1 , v2 , v4 ,
v6 , v1 , v4 , v7 , v5 , v2 , v7 , v6 , v3 , v1 )  ýéëåðîâ öèêë.
     Âûøåîïèñàííàÿ ïðîöåäóðà ïîèñêà ýéëåðîâà öèêëà îðèåí-
òèðîâàíà ãëàâíûì îáðàçîì íà ðàáîòó ñ èçîáðàæåíèåì ãðàôà è
èäåàëüíî ïîäõîäèò äëÿ ðåøåíèÿ çàäà÷-ãîëîâîëîìîê òèïà "íà-
ðèñîâàòü ãðàô (êàðòèíêó), íå îòðûâàÿ êàðàíäàø îò áóìàãè è
íå ïîâòîðÿÿ ëèíèé". Åñëè æå ãðàô çàäàí èíà÷å, íàïðèìåð â
ìàòðè÷íîé ôîðìå, èëè â âèäå ñïèñêà, òî, ÷òîáû óñòàíîâèòü, íå
ÿâëÿåòñÿ ëè î÷åðåäíîå âûáèðàåìîå ðåáðî ìîñòîì (íå ïðèáåãàÿ
ê èçîáðàæåíèþ), òðåáóþòñÿ äîïîëíèòåëüíûå îïåðàöèè. Ïîýòî-
ìó äëÿ êîìïüþòåðíîé ðåàëèçàöèè ëó÷øå ïîäõîäèò àëãîðèòì,
îñíîâàííûé íà ïðîöåäóðå, èñïîëüçîâàííîé ïðè äîêàçàòåëüñòâå
òåîðåìû 5.1, â ñîîòâåòñòâèè ñ êîòîðûì ïåðâîíà÷àëüíî íàéäåí-
íûé öèêë ïîñëåäîâàòåëüíî ðàñøèðÿåòñÿ çà ñ÷åò îáúåäèíåíèÿ
ñ äðóãèìè öèêëàìè, ïîêà íå áóäóò çàäåéñòâîâàíû âñå ðåáðà.
Ôîðìàëèçîâàííàÿ çàïèñü àëãîðèòìà èìååò âèä:
 begin               {ÝÉËÅÐ}
   select v∈V ;              { Âûáðàòü ïðîèçâîëüíóþ âåðøèíó }
   v→S;                                       { è çàíåñòè â ñòåê. }
   while
        S6=∅ do { Ïîêà ñòåê íå ïóñò, âûïîëíÿòü äåéñòâèÿ: }
     if Γ(s1 )6=∅              { åñëè îêðóæåíèå âåðøèíû s1 , }
    
                  { íàõîäÿùåéñÿ â âåðõóøêå ñòåêà, íå ïóñòî, }
    
      
    
                                  { òî }
    
      
                
                  select u∈Γ(s1 ); { âûáðàòü îäíó èç åå }
    
      
                
    
      
       
                   u→S;      { "ñîñåäîê" è çàíåñòè â ñòåê, }
       
         then
                  Γ(s1 ) := Γ(s1 )−{u}; { à çàòåì óäàëèòü }
                
    
                    Γ(u) := Γ(u)−{s1 } { ïðîéäåííîå ðåáðî; }
    
      
    
      
                                 { èíà÷å }
    
      
                (
    
      
                    S→v;                { ïîëó÷èòü èç ñòåêà }
    
      
    
      else
                    output(v)       { è âûâåñòè î÷åðåäíóþ }
                                           { âåðøèíó öèêëà. }
 end.               {ÝÉËÅÐ}
   Ïðåäïîëàãàåòñÿ, ÷òî ãðàô çàäàí ñïèñêîì âåðøèí (ñïèñêîì
ñìåæíîñòè), à â êà÷åñòâå îñíîâíîé ðàáî÷åé ñòðóêòóðû äàí-
íûõ, ïîçâîëÿþùåé ëåãêî çàôèêñèðîâàòü ïîñëåäîâàòåëüíîñòü
ïðîõîæäåíèÿ âåðøèí, èñïîëüçîâàí ñòåê S.


                                106

Страницы