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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Γ(v
i
)
v
i
, Γ
−1
(v
i
)
v
i
.
Γ
−1
(v
1
) = {v
4
} Γ
−1
(v
2
) = {v
1
, v
3
} Γ
−1
(v
3
) = {v
1
, v
4
}
Γ
−1
(v
4
) = {v
5
} Γ
−1
(v
5
) = {v
2
}
G
2
m
m
2
m
G.
deg v,
v deg
+
v=|Γ(v)|
v deg
−
v=|Γ
−1
(v)|
deg v= deg
+
v+ deg
−
v
P
n
i=1
deg
−
v
i
=
P
n
i=1
deg
+
v
i
=|A|=m m
A=[a
i,j
] n
a
i,j
(v
i
, v
j
)
Ïîñêîëüêó Γ(vi ) îáîçíà÷àåò ìíîæåñòâî êîíå÷íûõ âåðøèí âñåõ
äóã, èñõîäÿùèõ èç vi , òî ÷åðåç Γ−1 (vi ) åñòåñòâåííî îáîçíà÷èòü
ìíîæåñòâî íà÷àëüíûõ âåðøèí âñåõ äóã, âõîäÿùèõ â vi . Òîãäà
îïèñàíèå ãðàôà, èçîáðàæåííîãî íà ðèñ. 1.15, ìîæåò áûòü âû-
ïîëíåíî òàê:
     Γ−1 (v1 ) = {v4 }, Γ−1 (v2 ) = {v1 , v3 }, Γ−1 (v3 ) = {v1 , v4 },
     Γ−1 (v4 ) = {v5 }, Γ−1 (v5 ) = {v2 }.
   Î êîëè÷åñòâå îðãðàôîâ. Ëþáîìó ïðîñòîìó ãðàôó G
ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå îðãðàô, ïðèäàâ êàæäîìó ðåá-
ðó îäíó èç äâóõ âîçìîæíûõ îðèåíòàöèé. Âñåãî èìååòñÿ 2m
ðàçëè÷íûõ âàðèàíòîâ îðèåíòàöèè ìíîæåñòâà èç m ðåáåð, ò. å.
èç îäíîãî ïðîñòîãî ïîìå÷åííîãî ãðàôà â îáùåì ñëó÷àå ìîæ-
íî ïîëó÷èòü 2m îðèåíòèðîâàííûõ. Êðîìå òîãî, âìåñòî îäíîé
äóãè ìîæíî âçÿòü äâå ïàðàëëåëüíûå ñ ïðîòèâîïîëîæíîé îðè-
åíòàöèåé. Âàðüèðóÿ êîëè÷åñòâî ïàð ïàðàëëåëüíûõ äóã è âûáè-
ðàÿ èõ â ðàçëè÷íûõ êîìáèíàöèÿõ, ïîëó÷àåì äîïîëíèòåëüíîå è
âåñüìà ñóùåñòâåííîå ðàñøèðåíèå ÷èñëà ãðàôîâ, ïðîèçâîäíûõ
îò ãðàôà G.
    Õàðàêòåðèñòèêè îðãðàôîâ. Ïðè îïèñàíèè îðãðàôîâ
èñïîëüçóþò òå æå ïîíÿòèÿ, òåðìèíû è õàðàêòåðèñòèêè, ÷òî è
äëÿ íåîðèåíòðîâàííûõ ãðàôîâ, íî åñòü è ñâîÿ ñïåöèôèêà, îáó-
ñëîâëåííàÿ íàëè÷èåì îðèåíòàöèè äóã. Íàïðèìåð, äëÿ îðãðà-
ôîâ ñîõðàíÿþòñÿ ïîíÿòèÿ ñìåæíîñòè è èíöèäåíòíîñòè, îïðå-
äåëåííûå â ðàçä. 1.1, íî íàðÿäó ñ òàêîé õàðàêòåðèñòèêîé, êàê
ñòåïåíü âåðøèíû deg v, èñïîëüçóþò åùå äâå: ïîëóñòåïåíü èñ-
õîäà  ÷èñëî èñõîäÿùèõ èç v äóã deg+ v=|Γ(v)| è ïîëóñòå-
ïåíü çàõîäà  ÷èñëî âõîäÿùèõ â v äóã deg− v=|Γ−1 (v)| , ñâÿ-
çàííûå
Pn        î÷åâèäíûìè
                  P      ñîîòíîøåíèÿìè deg v= deg+ v+ deg− v è
           −       n      +
   i=1 deg   vi =  i=1 deg vi =|A|=m , ãäå m  ÷èñëî äóã â ãðàôå.
Íåêîòîðûå ñïåöèôè÷åñêèå ïîíÿòèÿ è õàðàêòåðèñòèêè îðãðà-
ôîâ ðàññìîòðåíû â ïîñëåäóþùèõ ðàçäåëàõ.
    Ìàòðèöû îðãðàôîâ. Ìàòðèöà ñìåæíîñòè îðãðàôà
îïðåäåëÿåòñÿ êàê êâàäðàòíàÿ ìàòðèöà A=[ai,j ] ïîðÿäêà n , â
êîòîðîé ýëåìåíò ai,j ðàâåí 1, åñëè â ãðàôå åñòü äóãà (vi , vj ) , è
0, åñëè òàêîé äóãè íåò.  êà÷åñòâå ïðèìåðà íà ðèñ. 1.16 ïðåä-



                                 24

Страницы