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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

s
v
1
r
v
2
r
v
3
s
v
4
s
v
5
sv
6
sv
7
s
v
8
s
v
9
s
v
10
s
v
11
s
v
12
@
@
@
@
@
@
s
v
4
s
v
2
s
v
3
s
v
9
s
v
7
s
v
1
s
v
6
s
v
11
s
v
5
s
v
10
s
v
8
s
v
12
Q
Q
Q
B
B
B
B
B
B
B
B
B
s
v
4
s
v
2
s
v
3
s
v
9
s
v
7
s
v
1
s
v
6
s
v
11
s
v
5
s
v
10
s
v
8
s
v
12
@
@
H
H
H
@
@
@
@
   3. Äåðåâüÿ
   Äåðåâüÿ ÿâëÿþòñÿ ïðîñòûì, íî î÷åíü âàæíûì âèäîì ãðà-
ôîâ. Ñ èõ ïîìîùüþ ëåãêî îïèñûâàåòñÿ ñòðóêòóðà ñàìûõ ðàç-
ëè÷íûõ îáúåêòîâ: îðãàíèçàöèé è ó÷ðåæäåíèé, êíèã è äîêóìåí-
òîâ, ìàòåìàòè÷åñêèõ ôîðìóë, õèìè÷åñêèõ ñîåäèíåíèé, êîì-
ïüþòåðíûõ ôàéëîâûõ ñèñòåì, ïðîãðàìì è ìíîãîå äðóãîå.
   Ñ÷èòàåòñÿ, ÷òî ïåðâûì ïîíÿòèå äåðåâà èñïîëüçîâàë Êèðõ-
ãîô â 1847ã. ïðè èññëåäîâàíèè ýëåêòðè÷åñêèõ öåïåé. Ñïóñòÿ
äåñÿòèëåòèå Êýëè ââåë òåðìèí "äåðåâî" ïðè èçó÷åíèè ñòðóê-
òóðû óãëåâîäîðîäíûõ ñîåäèíåíèé è ïîëó÷èë ïåðâûå âàæíûå
ðåçóëüòàòû â ýòîì ðàçäåëå òåîðèè ãðàôîâ.

   3.1. Îñíîâíûå ïîíÿòèÿ
   Íåîðèåíòèðîâàííûå äåðåâüÿ. Íà ðèñ. 3.1 äàíû òðè
èçîáðàæåíÿ îäíîãî è òîãî æå íåîðèåíòèðîâàííîãî äåðåâà. Íàè-
áîëåå ñîîòâåòñòâóåò íàçâàíèþ âàðèàíò â, íî îáû÷íî ïðè èçîáðà-
         vs1    vr2                   vs4                 vs5      vs10
                                     Q
   v3 r       sv4     sv5   v2 s v3 s Q Qsv9        sv1 @  @sv7
       v6 s v7 s                           B         sv3      sv2      sv8  sv12
          @        @        v7 s v1 sv6 s BBsv11    @                 @
   v8 s @ sv9 @ sv10            B             B      v@
                                                        4H
                                                           s        sv6 @sv11
      @ @s                   s BBs        s BBs           HH
                   s                                                s
         v11      v12       v5 v10         v8 v12                  v9
             a                        á                            â
                                 Ðèñ. 3.1
æåíèè äåðåâüåâ èñïîëüçóþò âàðèàíòû à è á. Èç ðèñóíêà ñòà-
íîâÿòñÿ ïîíÿòíûìè òåðìèíû êîðåíü è ëèñò, óïîòðåáëÿåìûå
ïðè ðàññìîòðåíèè ïîäîáíûõ ãðàôîâ. Ëèñòîì (âèñÿ÷åé âåðøè-
íîé ) íàçûâàþò âåðøèíó, ñòåïåíü êîòîðîé ðàâíà 1, åñëè îíà íå
ðàññìàòðèâàåòñÿ êàê êîðåíü.  êà÷åñòâå êîðíÿ â íåîðèåíòèðî-
âàííîì äåðåâå ìîæíî ïðèíÿòü ëþáóþ âåðøèíó.
   Ñóùåñòâóåò íåñêîëüêî ýêâèâàëåíòíûõ îïðåäåëåíèé íåîðè-
åíòèðîâàííîãî äåðåâà, êàæäîå èç êîòîðûõ îòðàæàåò ðàçëè÷-
íûå ñâîéñòâà ïîñëåäíåãî. Ïðèâåäåì íåêîòîðûå èç íèõ:



                                        43

Страницы