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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

V T
2
={v
1
, v
4
, v
5
}.
v
2
v
3
V T
2
.
V T
2
,
T
3
,
ET
3
={{v
1
, v
5
}, {v
4
, v
5
}, {v
5
, v
8
}}.
À
T
3
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
r
v
8
r
v
9
r
v
10
À
T
5
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
r
v
8
r
v
9
r
v
10
À
T
6
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
r
v
8
r
v
9
r
v
10
À
T
7
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
r
v
8
r
v
9
r
v
10
À
T
8
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
r
v
8
r
v
9
r
v
10
À
T
9
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
r
v
6
r
v
7
r
v
8
r
v
9
r
v
10
1, 2, . . . , n
i
k
E
e
i,1
e
i,2
,
i
óæå òðè âåðøèíû V T2 ={v1 , v4 , v5 }. Òðåòüå ðåáðî ïîêà ïðîïóñ-
êàåì, òàê êàê íè v2 íè v3 íå ïðèíàäëåæàò V T2 . Òî æå ñàìîå
ìîæíî ñêàçàòü è î ïÿòîì ðåáðå. Îáà êîíöà ÷åòâåðòîãî ðåáðà,
íàîáîðîò, ïðèíàäëåæàò V T2 , çíà÷èò, åãî âêëþ÷åíèå ïðèâåäåò
ê ïîÿâëåíèþ öèêëà, ÷òî íåäîïóñòèìî. È òîëüêî øåñòîå ðåáðî
îòâå÷àåò óñëîâèþ íà âêëþ÷åíèå. Òàêèì îáðàçîì, ïîñëå òðå-
òüåé èòåðàöèè ïîëó÷àåì äåðåâî T3 , ñîñòîÿùåå èç òðåõ ðåáåð,
ò. å. ET3 ={{v1 , v5 }, {v4 , v5 }, {v5 , v8 }}. Íà ÷åòâåðòîé èòåðàöèè ê
äåðåâó äîáàâëÿåòñÿ îäèííàäöàòîå ðåáðî, íà ïÿòîé  âîñüìîå
è ò. ä. Ïîñòðîåíèå îñòîâà çàâåðøàåòñÿ íà äåâÿòîé èòåðàöèè
ïðèñîåäèíåíèåì äåñÿòîãî ðåáðà. Íà ðèñ. 3.13 ïðåäñòàâëåíû

  3    vr 1      vr 2   vr 3   5    vr 1       vr 2   vr 3   6    vr 1     vr 2   vr 3
      À                            À                             À

  v4 r T3 vr     r v6 rv7      v4 r      r T5 r v6 rv7
                                         v5                  v4 r     r T6 r v6 rv7
                                                                      v5
             5

      r    r     r                 r     r     r                 r    r    r
      v8   v9    v10               v8    v9    v10               v8   v9   v10

  7    vr 1      vr 2   vr 3   8    vr 1       vr 2   vr 3   9    vr 1     vr 2   vr 3
      À                            À                             À

  v4 r     r T7 r v6 rv7       v4 r      r T8 r v6 rv7       v4 r     r T9 r v6 rv7
           v5                            v5                           v5
      r    r     r                 r     r     r                 r    r    r
      v8   v9    v10               v8    v9    v10               v8   v9   v10

                                        Ðèñ. 3.13
îòäåëüíûå ýòàïû îïèñàííîãî ïðîöåññà. ×èñëî â âåðõíåì óãëó
êàæäîãî ïðÿìîóãîëüíèêà ñîîòâåòñòâóåò èòåðàöèè, íà êîòîðîé
ïîëó÷åí èçîáðàæåííûé ôðàãìåíò.
   Ôîðìàëèçîâàííàÿ çàïèñü àëãîðèòìà. Ââåäåì ñëåäó-
þùèå îáîçíà÷åíèÿ:
   1, 2, . . . , n  ìåòêè âåðøèíû ãðàôà;
   i  ñ÷åò÷èê ðåáåð ãðàôà;
   k  ñ÷åò÷èê âåðøèí ãðàôà è ñ÷åò÷èê èòåðàöèé;
   E  ñïèñîê ðåáåð ãðàôà, óïîðÿäî÷åííûõ ïî äëèíå. Êàæ-
           äàÿ ñòðîêà ñïèñêà ñîñòîèò èç ïàðû ei,1 è ei,2 , ÿâëÿ-
           þùèõñÿ ìåòêàìè êîíöîâ i -ãî ðåáðà;


                                          65

Страницы