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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

S
j s
j
=1,
s
j
=.0
S
s
1
s
2
s
3
s
4
s
5
s
6
s
7
s
8
s
9
s
10
0 1 0 0 0 0 0 0 0 0 0 T
0
=h{v
1
}, ∅i
1 1 0 0 0 1 0 0 0 0 0 T
1
:=T
0
+ {1; 5}
2 1 0 0 1 1 0 0 0 0 0 T
2
:=T
1
+ {4; 5}
3 1 0 0 1 1 0 0 1 0 0 T
3
:=T
2
+ {5; 8}
4 1 0 0 1 1 1 0 1 0 0 T
4
:=T
3
+ {5; 6}
5 1 0 0 1 1 1 0 1 1 0 T
5
:=T
4
+ {6; 9}
6 1 0 0 1 1 1 0 1 1 1 T
6
:=T
5
+ {3; 6}
7 1 0 1 1 1 1 0 1 1 1 T
7
:=T
6
+ {3; 2}
8 1 1 1 1 1 1 0 1 1 1 T
8
:=T
7
+ {2; 3}
9 1 1 1 1 1 1 1 1 1 1 T
9
:=T
8
+ {3; 7}
k := 1 n s
k
:= 0; S
s
1
:= 1; v
1
k := 1 n−1
i := 1;
s
e
i,1
=s
e
i,2
i := i+1;
s
e
i,1
:=1; s
e
i,2
:=1;
(i);
O(nm)
   S  ñïèñîê ïðèíàäëåæíîñòè âåðøèí ãðàôà ôîðìèðóå-
       ìîìó ôðàãìåíòó îñòîâà. Åñëè ê òåêóùåé èòåðàöèè
       âåðøèíà j óæå âêëþ÷åíà â îñòîâ, òî sj =1, èíà-
       ÷å sj =.0 Ïåðâîíà÷àëüíî âñå ýëåìåíòû ñïèñêà ðàâíû
       íóëþ, êðîìå ýëåìåíòà, ñîîòâåòñòâóþùåãî íà÷àëüíîé
       âåðøèíå. Ïî çàâåðøåíèè ðàáîòû àëãîðèòìà âñå ýëå-
       ìåíòû S ðàâíû åäèíèöå. Äëÿ ðàññìîòðåííîãî âû-
       øå ïðèìåðà äèíàìèêà èçìåíåíèÿ ñïèñêà îòðàæåíà
       â òàáë. 3.6.
                                                            Òàáëèöà 3.6
    Èòåðàöèÿ                                              Ôðàãìåíòû
    (ðåáðî)     s1 s2 s3 s4 s5 s6 s7 s8 s9 s10
                                                          îñòîâà
         0       1   0   0   0   0    0   0   0   0   0   T0 =h{v1 }, ∅i
         1       1   0   0   0   1    0   0   0   0   0   T1 :=T0 + {1; 5}
         2       1   0   0   1   1    0   0   0   0   0   T2 :=T1 + {4; 5}
         3       1   0   0   1   1    0   0   1   0   0   T3 :=T2 + {5; 8}
         4       1   0   0   1   1    1   0   1   0   0   T4 :=T3 + {5; 6}
         5       1   0   0   1   1    1   0   1   1   0   T5 :=T4 + {6; 9}
         6       1   0   0   1   1    1   0   1   1   1   T6 :=T5 + {3; 6}
         7       1   0   1   1   1    1   0   1   1   1   T7 :=T6 + {3; 2}
         8       1   1   1   1   1    1   0   1   1   1   T8 :=T7 + {2; 3}
         9       1   1   1   1   1    1   1   1   1   1   T9 :=T8 + {3; 7}

   Ñ èñïîëüçîâàíèåì ââåäåííûõ îáîçíà÷åíèé çàïèñü àëãîðèò-
ìà ïðèíèìàåò âèä:
begin              {ÏÐÈÌ}
  for k := 1 to n do sk := 0; { Èíèöèàëèçàöèÿ ñïèñêà S }
  s1 := 1;                { Íà÷àòü ïîñòðîåíèå îñòîâà ñ âåðøèíû v1 }
  for
    k := 1 to n−1 do                  { Öèêë ôîðìèðîâàíèÿ îñòîâà }
      i := 1;
   
       while sei,1 =sei,2 do i := i+1; { Ïîèñê âêëþ÷àåìîãî ðåáðà. }
    sei,1 :=1; sei,2 :=1; {Ðåáðî íàéäåíî, âêëþ÷èòü åãî â îñòîâ }
   
       output(i);                            { è íàïå÷àòàòü íîìåð. }
end.                {ÏÐÈÌ}
   Îöåíèâàÿ, êàê è ðàíåå, ïî ìàêñèìóìó òðóäîåìêîñòü ýòîãî
âàðèàíòà àëãîðèòìà Ïðèìà, óáåæäàåìñÿ, ÷òî åå ïîðÿäîê ðàâåí
O(nm) áåç ó÷åòà òðóäîåìêîñòè ñîðòèðîâêè ñïèñêà ðåáåð.



                                     66

Страницы