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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

{v
i
, v
j
},
e a b l
ab
T
i
V T
i
i
T
0
=h{v
1
}, ∅i {v
1
}
1 v
1
v
5
2 T
1
:= T
0
+ {v
1
, v
5
} {v
1
, v
5
} 1
2 v
4
v
5
3 T
2
:= T
1
+ {v
4
, v
5
} {v
1
, v
4
, v
5
} 2
3 v
2
v
3
5 T
8
:= T
7
+ {v
2
, v
3
}
{v
1
, v
2
, v
3
, v
4
, v
5
,
v
6
, v
8
, v
9
, v
10
}
8
4 v
1
v
4
7
5 v
9
v
10
8 T
6
:= T
5
+ {v
9
, v
10
} {v
1
, v
4
, v
5
, v
6
, v
8
, v
9
, v
10
} 6
6 v
5
v
8
10 T
3
:= T
2
+ {v
5
, v
8
} {v
1
, v
4
, v
5
, v
8
} 3
7 v
4
v
8
13
8 v
6
v
10
14 T
5
:= T
4
+ {v
6
, v
10
} {v
1
, v
4
, v
5
, v
6
, v
8
, v
10
} 5
9 v
6
v
9
14
10 v
3
v
7
17 T
9
:= T
8
+ {v
3
, v
7
}
{v
1
, v
2
, v
3
, v
4
, v
5
,
v
6
, v
7
, v
8
, v
9
, v
10
}
9
11 v
5
v
6
20 T
4
:= T
3
+ {v
5
, v
6
} {v
1
, v
4
, v
5
, v
6
, v
8
} 4
12 v
2
v
7
22
13 v
8
v
9
23
14 v
4
v
9
23
15 v
6
v
3
25 T
7
:= T
6
+ {v
3
, v
6
}; {v
1
, v
3
, v
4
, v
5
, v
6
, v
8
, v
10
} 7
. . . . . . . . . . . . . . . . . .
T
i
V T
i
i
v
1
.
v
1
v
5
.
ðàñòàíèþ âåñîâ ðåáåð, òî âêëþ÷åíèþ â îñòîâ íà î÷åðåäíîé
èòåðàöèè ïîäëåæèò ïåðâîå îò íà÷àëà ñïèñêà ðåáðî {vi , vj },
îòâå÷àþùåå óêàçàííîìó âûøå óñëîâèþ.
   Ïîñòðîåíèå îñòîâà äëÿ ãðàôà, èçîáðàæåííîãî íà ðèñ. 3.10,
èëëþñòðèðóåò òàáë. 3.5, àíàëîãè÷íàÿ òàáë. 3.3.
                                                                Òàáëèöà 3.5
    e    a     b   lab            Ti                    V Ti                    i
                         T0 =h{v1 }, ∅i                 {v1 }
    1    v1 v5 2         T1 := T0 + {v1 , v5 }       {v1 , v5 }                 1
    2    v4 v5 3         T2 := T1 + {v4 , v5 }     {v1 , v4 , v5 }              2
                                             {v1 , v2 , v3 , v4 , v5 ,
    3    v2 v3 5 T8 := T7 + {v2 , v3 }                                          8
                                              v6 , v8 , v9 , v10 }
    4    v1 v4 7                                         
    5    v9 v10 8 T6 := T5 + {v9 , v10 } {v1 , v4 , v5 , v6 , v8 , v9 , v10 }   6
    6    v5 v8 10 T3 := T2 + {v5 , v8 }         {v1 , v4 , v5 , v8 }            3
    7    v4 v8 13                                        
    8    v6 v10 14 T5 := T4 + {v6 , v10 } {v1 , v4 , v5 , v6 , v8 , v10 }       5
    9    v6 v9 14                                        
                                             {v1 , v2 , v3 , v4 , v5 ,
   10    v3 v7 17 T9 := T8 + {v3 , v7 }                                         9
                                              v6 , v7 , v8 , v9 , v10 }
   11    v5 v6 20 T4 := T3 + {v5 , v6 }       {v1 , v4 , v5 , v6 , v8 }         4
   12    v2 v7 22                                        
   13    v8 v9 23                                        
   14    v4 v9 23                                        
   15    v6 v3 25 T7 := T6 + {v3 , v6 }; {v1 , v3 , v4 , v5 , v6 , v8 , v10 }   7
   ...   ... ... ...       ...                           ...

   Çäåñü ñîäåðæèìîå ñòîëáöà Ti ïîêàçûâàåò, êàê ðàñòåò åäèí-
ñòâåííûé äðåâîâèäíûé ôðàãìåíò ôîðìèðóåìîãî îñòîâà, ñòîë-
áåö V Ti îòðàæàåò ðîñò ìíîæåñòâà âåðøèí, ïðèíàäëåæàùèõ
ýòîìó ôðàãìåíòó, à íîìåð èòåðàöèè, íà êîòîðîé ðåáðî âêëþ-
÷àåòñÿ â îñòîâ, óêàçàí â ñòîëáöå i .
   Ïóñòü íà÷àëüíûé ôðàãìåíò ñîñòîèò èç âåðøèíû v1 . Àíà-
ëèç ïåðâîãî ðåáðà ñïèñêà ïîêàçûâàåò, ÷òî îíî îòâå÷àåò óñëî-
âèþ âêëþ÷åíèÿ â îñòîâ. Ïîëó÷åííîå äåðåâî èìååò äâå âåð-
øèíû v1 è v5 . Ïðîâåðÿÿ âòîðîå ðåáðî, óáåæäàåìñÿ, ÷òî åãî
òàêæå ñëåäóåò âêëþ÷èòü â îñòîâ. Íîâûé ôðàãìåíò ñîäåðæèò


                                       64

Страницы