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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

s
v
1
s
v
2
s
v
3
s
v
4
@
@
v
1
: v
2
, v
2
v
2
: v
1
, v
1
, v
3
, v
4
v
3
: v
2
, v
4
v
4
: v
2
, v
3
v
1
v
2
v
1
S← S→ S→
1 v
1
v
2
{v
1
, v
2
} − 7 v
1
v
2
v
3
v
4
v
2
v
2
2 v
1
v
2
v
1
{v
2
, v
1
} − 8 v
1
v
2
v
3
v
4
v
4
3 v
1
v
2
v
1
− − v
1
9 v
1
v
2
v
3
v
3
4 v
1
v
2
v
3
{v
2
, v
3
} − 10 v
1
v
2
v
2
5 v
1
v
2
v
3
v
4
{v
3
, v
4
} − 11 v
1
v
1
6 v
1
v
2
v
3
v
4
v
2
{v
4
, v
2
} − ∅ −
v
1
6v
2
, v
2
6v
2
∅ ∅ ∅ ∅ ∅
v
2
6v
1
, v
1
, v
3
, v
4
6v
1
, v
3
, v
4
v
3
, v
4
6v
3
, v
4
v
4
6v
4
∅
v
3
v
2
, v
4
v
2
, v
4
v
2
, v
4
6v
2
, v
4
6v
4
∅ ∅
v
4
v
2
, v
3
v
2
, v
3
v
2
, v
3
v
2
, v
3
v
2
, 6v
3
6v
2
∅
v
1
.
v
1
    Ðàññìîòðèì ðàáîòó àëãîðèòìà íà ïðèìåðå. Ïóñòü òðåáóåò-
ñÿ íàéòè ýéëåðîâ öèêë äëÿ ãðàôà, èçîáðàæåííîãî íà ðèñ. 5.10
è çàäàííîãî ñïèñêàìè ñìåæíîñòè. Ôàêòè÷åñêè ìû èìååì ìóëü-
                                            sv3              v1     :   v2 , v 2
                                   v2                        v2     :   v1 , v 1 , v 3 , v 4
            v1 s                    s
                                    @                        v3     :   v2 , v 4
                                      @sv4                   v4     :   v2 , v 3

                                          Ðèñ. 5.10
òèãðàô, ïîýòîìó ñïèñêè äëÿ âåðøèí v1 è v2 ñîäåðæàò ïî-
âòîðÿþùèåñÿ ýëåìåíòû, îòðàæàÿ íàëè÷èå ïàðàëëåëüíûõ ðå-
áåð. Âûáåðåì â êà÷åñòâå íà÷àëüíîé âåðøèíó v1 è çàíåñåì åå
â ñòåê. Äàëüíåéøèå äåéñòâèÿ îòðàæåíû â òàáë. 5.1 è 5.2.
                                                                                            Òàáëèöà 5.1
  Èòå-                                                                    Èòå-
   ðà-        Ñòåê           S← Óäàëÿåìîå
                                  ðåáðî   S→                               ðà-           Ñòåê                 S→
  öèÿ                                                                     öèÿ
    1       v1                v2         {v1 , v2 }              −         7           v1 v2 v3 v4 v2         v2
    2       v1 v2             v1         {v2 , v1 }              −         8           v1 v2 v3 v4            v4
    3       v1 v2 v1          −             −                    v1        9           v1 v2 v3               v3
    4       v1 v2             v3         {v2 , v3 }              −         10          v1 v2                  v2
    5       v1 v2 v3          v4         {v3 , v4 }              −         11          v1                     v1
    6       v1 v2 v3 v4       v2         {v4 , v2 }              −                     ∅                      −
                                                                                           Òàáëèöà 5.2
  Èòå-
   ðà-               1                     2                 3               4               5         6      7
  öèÿ
   v1   :   6 v2 , v2              6 v2                  ∅               ∅               ∅            ∅       ∅
   v2   :    6 v1 , v1 , v3 , v4    6 v 1 , v3 , v 4     v3 , v 4        6 v 3 , v4      v4           6 v4    ∅
   v3   :     v2 , v4                v2 , v4             v2 , v 4         6 v 2 , v4     6 v4          ∅      ∅
   v4   :     v2 , v3                v2 , v3             v2 , v 3          v 2 , v3       v2 , 6 v3    6 v2   ∅
   Â òàáë. 5.1 ïðåäñòàâëåíû îïåðàöèè ñî ñòåêîì, à â òàáë. 5.2
ïîêàçàíî, êàê èçìåíÿþòñÿ ñïèñêè âåðøèí îò èòåðàöèè ê èòå-
ðàöèè (ñòîëáöû) ïî ìåðå óäàëåíèÿ ðåáåð.
   Ñíà÷àëà â âåðøèíå ñòåêà íàõîäèòñÿ v1 . Ïîýòîìó â ñïèñêå
ñìåæíîñòè äëÿ v1 ïðîèçâîëüíî âûáèðàåì íåêîòîðóþ âåðøè-



                                                       107

Страницы