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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

K
n
V, |E(K
n
)| C
2
n
=
n(n−1)
2
.
|EG|=n−1)
G
6
G
7
.
P
4
G
7
,
(v
0
, e
1
, v
1
, e
2
, v
2
, . . . , v
k−1
, e
k
, v
k
), v
i−1
v
i
e
i
.
(v
0
, v
1
, . . . , v
k−1
, v
k
) (e
1
, e
2
, . . . , e
k−1
, e
k
).
(v
1
, v
2
,
v
5
, v
4
, v
3
) (v
1
, v
2
, v
5
, v
4
, v
1
, v
3
)
G
8
.
C
n
.
G
1
G
11
, G
2
G
10
, G
3
G
8
, G
4
G
9
, G
5
G
6
.
K
4
ðÿäêà ÷èñëî ðåáåð. Ýòî òàê íàçûâàåìûé ïîëíûé ãðàô. Äëÿ òà-
êèõ ãðàôîâ ïðèíÿòî îáîçíà÷åíèå Kn . ßñíî, ÷òî ÷èñëî ðåáåð
â ïîëíîì ãðàôå ðàâíî êîëè÷åñòâó äâóõýëåìåíòíûõ ïîäìíî-
æåñòâ ìíîæåñòâà V, ïîýòîìó èìååì |E(Kn )| = Cn2 = n(n−1)                  2
                                                                               .
     Äåðåâüÿ è öåïè. Ñâÿçíûå ãðàôû ñ ìèíèìàëüíûì êîëè-
÷åñòâîì ðåáåð ( |EG|=n−1) îáðàçóþò êëàññ òàê íàçûâàåìûõ
äåðåâüåâ. Â íàøåì ïðèìåðå ýòî G6 è G7 . Ðàññìîòðåíèþ äå-
ðåâüåâ ïîñâÿùåí ðàçä. 3 ïîñîáèÿ. Çäåñü æå îòìåòèì îáîçíà-
÷åííûé íà ðèñ. 1.7 êàê P4 ãðàô G7 , ÿâëÿþùèéñÿ ÷àñòíûì
ñëó÷àåì äåðåâà è íàçûâàåìûé ïðîñòîé öåïüþ.
     Âîîáùå öåïü  ýòî ÷åðåäóþùàÿñÿ ïîñëåäîâàòåëüíîñòü âåð-
øèí è ðåáåð (v0 , e1 , v1 , e2 , v2 , . . . , vk−1 , ek , vk ), ãäå vi−1 è vi ÿâ-
ëÿþòñÿ êîíöàìè ðåáðà ei . Â êîìïàêòíîé ôîðìå ýòà çàïèñü
âûãëÿäèò òàê: (v0 , v1 , . . . , vk−1 , vk ) èëè (e1 , e2 , . . . , ek−1 , ek ). Â
îòëè÷èå îò ïðîñòîé öåïü îáùåãî âèäà ìîæåò ñîäåðæàòü ïî-
âòîðÿþùèåñÿ âåðøèíû. Íàïðèìåð, â ãðàôå íà ðèñ. 1.1 (v1 , v2 ,
v5 , v4 , v3 )  ïðîñòàÿ öåïü, à (v1 , v2 , v5 , v4 , v1 , v3 )  öåïü. Îáû÷-
íî öåïü ðàññìàòðèâàåòñÿ íå êàê ñàìîñòîÿòåëüíûé ãðàô, à êàê
÷àñòü íåêîòîðîãî ãðàôà. Äëèíîé öåïè íàçûâàþò êîëè÷åñòâî
ñîñòàâëÿþùèõ åå ðåáåð. ßñíî, ÷òî äëèíà ïðîñòîé öåïè íå ìî-
æåò ïðåâûøàòü ÷èñëà âåðøèí ñîäåðæàùåãî åå ãðàôà, à äëèíà
öåïè îáùåãî âèäà  ÷èñëà ðåáåð ýòîãî ãðàôà.
     Ïîíÿòèå öåïè øèðîêî èñïîëüçóåòñÿ â òåîðèè ãðàôîâ. Íà-
ïðèìåð, ñâÿçíûé ãðàô ìîæíî îïðåäåëèòü êàê ãðàô, â êîòîðîì
ëþáàÿ ïàðà âåðøèí ñîåäèíåíà õîòÿ áû îäíîé öåïüþ.
     Öèêëû. Öèêëîì (ïðîñòûì öèêëîì) íàçûâàåòñÿ çàìêíó-
òàÿ öåïü (ïðîñòàÿ öåïü). Ïðèìåðîì ïðîñòîãî öèêëà ÿâëÿåòñÿ
ãðàô G8 . Ãðàô, ïðåäñòàâëÿþùèé ñîáîé ïðîñòîé öèêë, îáîçíà-
÷àåòñÿ êàê Cn . Êàê è â ñëó÷àå öåïåé, èíòåðåñ ïðåäñòàâëÿåò
ðàññìîòðåíèå öèêëîâ êàê ÷àñòåé íåêîòîðîãî ãðàôà.
     Äîïîëíèòåëüíûå ãðàôû. Ðàññìîòðèì ïàðû ãðàôîâ:
G1 è G11 , G2 è G10 , G3 è G8 , G4 è G9 , G5 è G6 . Åñëè â êàæ-
äîé èç íèõ èçîáðàæåíèå îäíîãî èç ãðàôîâ "íàëîæèòü" îïðå-
äåëåííûì îáðàçîì íà èçîáðàæåíèå äðóãîãî, òî ïîëó÷èòñÿ ïîë-
íûé ãðàô, ò. å. îäèí ãðàô äîïîëíÿåò äðóãîé äî K4 . Ýòî ïàðû
âçàèìíî äîïîëíèòåëüíûõ ãðàôîâ. Âîîáùå äîïîëíåíèåì ãðàôà



                                       14

Страницы