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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

¤
¢
n n−1
¤
n=1, 2, 3.
n−1
T n
n
1
≤(n−1) n
2
≤(n−1)
n
1
−1 n
2
−1 T
[(n
1
−1)+(n
2
−1)]+1=n
1
+n
2
−1=n−1 ¢
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
  1) Äåðåâî  ýòî ñâÿçíûé ãðàô áåç öèêëîâ.
  2) Äåðåâî  ýòî ãðàô, â êîòîðîì ëþáàÿ ïàðà âåðøèí ñâÿ-
     çàíà åäèíñòâåííîé öåïüþ. ¤ Äåéñòâèòåëüíî, íàëè÷èå
     äâóõ è áîëåå öåïåé, ñîåäèíÿþùèõ íåêîòîðóþ ïàðó âåð-
     øèí, îçíà÷àåò ïðèñóòñòâèå öèêëîâ, îáðàçîâàííûõ íåñîâ-
     ïàäàþùèìè ÷àñòÿìè òàêèõ öåïåé. ¢
  3) Äåðåâî  ýòî ñâÿçíûé ãðàô, èìåþùèé n âåðøèí è n−1
     ðåáåð. ¤ Íåïîñðåäñòâåííîé ïðîâåðêîé óñòàíàâëèâàåì
     ñïðàâåäëèâîñòü ýòîãî óòâåðæäåíèÿ ïðè n=1, 2, 3. Äîïó-
     ñòèì, ÷òî îíî âåðíî äëÿ äåðåâà ñ n−1 âåðøèíàìè, è
     ðàññìîòðèì ñëó÷àé, êîãäà äåðåâî T èìååò n âåðøèí.
     Åñëè â íåì óäàëèòü ëþáîå ðåáðî, òî â ñèëó óòâåðæäåíèÿ
     2, ïîëó÷èì äâà äåðåâà ñ n1 ≤(n−1) è n2 ≤(n−1) âåðøè-
     íàìè. Ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ ÷èñëî ðåáåð â
     íèõ n1 −1 è n2 −1 ñîîòâåòñòâåííî. Ïîýòîìó T ñîäåðæèò
     [(n1 −1)+(n2 −1)]+1=n1 +n2 −1=n−1 ðåáåð. ¢
   Åñòåñòâåííûì ðàñøèðåíèåì ïîíÿòèÿ äåðåâà ÿâëÿåòñÿ
ëåñ  íåñâÿçíûé ãðàô, âñå êîìïîíåíòû êîòîðîãî  äåðåâüÿ.
   Ëþáîìó ñâÿçíîìó ãðàôó ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå
íåêîòîðîå äåðåâî, íàçûâàåìîå îñòîâíûì äåðåâîì, èëè îñòî-
âîì ýòîãî ãðàôà. Îñòîâ ãðàôà  ýòî åãî ìèíèìàëüíûé ñâÿç-
íûé îñòîâíûé ïîäãðàô.  îáùåì ñëó÷àå ãðàô ìîæåò èìåòü
íåñêîëüêî îñòîâîâ.  êà÷åñòâå ïðìåðà íà ðèñ. 3.2,à ïðåäñòàâ-
ëåí íåîðèåíòèðîâàííûé ãðàô è âñå åãî îñòîâû (ðèñ. 3.2,á,â,ã ).
            vs2              vs2              vs2              vs2
             @@               @@               @@               @@
     v1 s         sv3 v1 s         sv3 v1 s         sv3 v1 s         sv3


     v5 s         sv4 v5 s         sv4 v5 s         sv4 v5 s         sv4
            à                á                â                ã
                                   Ðèñ. 3.2
   Àíàëîãè÷íî, ëþáîìó íåñâÿçíîìó ãðàôó ìîæíî ïîñòàâèòü
â ñîîòâåòñòâèå îñòîâíûé ëåñ  ìàêñèìàëüíûé îñòîâíûé ïîä-
ãðàô, íå ñîäåðæàùèé öèêëîâ.




                                        44

Страницы