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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

T
K
.
T
K
T
0
S
, T
K
T
00
S
T
K
.
1, 2, . . . , n
i
k
E
e
i,1
e
i,2
,
i
t
S
s
j
j.
S
4, 7, 9, 12 14
s
1
s
2
s
3
s
4
s
5
s
6
s
7
s
8
s
9
s
10
0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 1 0 0 0 0 0 T
1
:={1; 5}
2 1 0 0 1 1 0 0 0 0 0 T
1
:=T
1
+ {4; 5}
3 1 2 2 1 1 0 0 0 0 0 T
2
:={2; 3}
5 1 2 2 1 1 0 0 0 3 3 T
3
:={9; 10}
6 1 2 2 1 1 0 0 1 3 3 T
1
:=T
1
+ {5; 8}
8 1 2 2 1 1 3 0 1 3 3 T
3
:=T
3
+ {6; 10}
10 1 2 2 1 1 3 2 1 1 1 T
2
:=T
2
+ {3; 7}
11 1 2 2 1 1 1 2 1 1 1 T
1
:=T
1
+ T
3
; T
3
\
15 1 1 1 1 1 1 1 1 1 1 T
1
:=T
1
+ T
2
; T
2
\
áîëüøå ðåáåð, ñîâïàäàþùèõ ñ ðåáðàìè TK . Ïîâòîðÿÿ îïèñàí-
íóþ ïðîöåäóðó äëÿ TK è TS0 , çàòåì äëÿ TK è TS00 è ò. ä.,
ïîëó÷àåì êîíå÷íóþ ïîñëåäîâàòåëüíîñòü êðàò÷àéøèõ îñòîâîâ,
ñõîäÿùóþñÿ ê TK .
   Ôîðìàëèçîâàííàÿ çàïèñü àëãîðèòìà. Ââåäåì ñëåäó-
þùèå îáîçíà÷åíèÿ:
    1, 2, . . . , n  ÷èñëîâûå ìåòêè âåðøèí ãðàôà;
    i  ñ÷åò÷èê ðåáåð ãðàôà;
    k  ñ÷åò÷èê ðåáåð îñòîâà;
    E  ñïèñîê ðåáåð ãðàôà, óïîðÿäî÷åííûõ ïî äëèíå. Êàæ-
            äàÿ ñòðîêà ñïèñêà ñîñòîèò èç ïàðû ei,1 è ei,2 , ÿâëÿ-
            þùèõñÿ ÷èñëîâûìè ìåòêàìè êîíöîâ i -ãî ðåáðà;
    t  íîìåð ôðàãìåíòà îñòîâà;
    S  ñïèñîê ïðèíàäëåæíîñòè âåðøèí ãðàôà ôðàãìåíòàì
            îñòîâà. Çíà÷åíèå sj ðàâíî íîìåðó ôðàãìåíòà, êîòî-
            ðîìó íà òåêóùåé èòåðàöèè ïðèíàäëåæèò âåðøèíà j.
            Ïåðâîíà÷àëüíî âñå ýëåìåíòû ñïèñêà ðàâíû íóëþ. Ïî
            çàâåðøåíèè ðàáîòû àëãîðèòìà âñå ýëåìåíòû S ðàâ-
            íû åäèíèöå. Äëÿ ðàññìîòðåííîãî âûøå ïðèìåðà äè-
            íàìèêà èçìåíåíèÿ ñïèñêà îòðàæåíà â òàáë. 3.4. Íà
            èòåðàöèÿõ 4, 7, 9, 12  14 ñîñòîÿíèå ñïèñêà íå ìåíÿ-
            åò ñÿ, òàê êàê ñîîòâåòñòâóþùèå ðåáðà íå ìîãóò áûòü
            âêëþ÷åíû â îñòîâ.
                                                Òàáëèöà 3.4
      Èòåðàöèÿ
      (ðåáðî)    s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 Ôðàãìåíòû
                                                îñòîâà
           0     0 0 0 0 0 0 0 0 0 0                 
           1     1 0 0 0 1 0 0 0 0 0 T1 :={1; 5}
           2     1 0 0 1 1 0 0 0 0 0 T1 :=T1 + {4; 5}
           3     1 2 2 1 1 0 0 0 0 0 T2 :={2; 3}
           5     1 2 2 1 1 0 0 0 3 3 T3 :={9; 10}
           6     1 2 2 1 1 0 0 1 3 3 T1 :=T1 + {5; 8}
           8     1 2 2 1 1 3 0 1 3 3 T3 :=T3 + {6; 10}
          10     1 2 2 1 1 3 2 1 1 1 T2 :=T2 + {3; 7}
          11     1 2 2 1 1 1 2 1 1 1 T1 :=T1 + T3 ; T\3
          15     1 1 1 1 1 1 1 1 1 1 T1 :=T1 + T2 ; T\2




                               61

Страницы