Составители:
Рубрика:
25
Ñìåæíûìè âåðøèíàìè íàçûâàþòñÿ äâå ðàçëè÷íûå âåðøèíû v
i
, v
j
,
åñëè ñóùåñòâóåò õîòÿ áû îäíà äóãà, èäóùàÿ îò îäíîé èç íèõ ê äðóãîé,
íàïðèìåð, âåðøèíû v
1
è v
2
, v
1
è v
4
ñìåæíû, à v
1
è v
3
íå ñìåæíû (ðèñ.1.15).
Ïåòëåé íàçûâàåòñÿ äóãà (v
i
, v
i
), ãäå íà÷àëî è êîíåö äóãè ñîâïàäàþò,
íàïðèìåð, ïåòëè u
5
=(v
3
, v
3
) è u
9
=(v
5
, v
5
) (ðèñ. 1.15).
Êðàòíûìè íàçûâàþòñÿ äóãè, ãðàíè÷íûå òî÷êè êîòîðûõ ñîâïàäàþò.
Ïðè ýòîì åñëè a
1
=(v, w) è b
2
=(v, w), òî äóãè a
1
è b
2
íàçûâàþòñÿ ïàðàë-
ëåëüíûìè, à åñëè c
3
= (w, v), òî äóãè a
1
è c
3
áóäåì íàçûâàòü âñòðå÷íûìè.
Íàïðèìåð, ó ãðàôà íà ðèñ.1.15 åñòü êðàòíûå ïàðàëëåëüíûå äóãè u
3
è u
4
è âñòðå÷íûå äóãè u
1
è u
2
. Ãðàô áåç ïàðàëëåëüíûõ äóã îïèñûâàåòñÿ áóëå-
âîé ìàòðèöåé ñìåæíîñòè.
Ìóëüòèãðàôîì íàçûâàåòñÿ ãðàô ñ êðàòíûìè äóãàìè, ò. å. ãðàô íà
ðèñ. 1.15 ÿâëÿåòñÿ ìóëüòèãðàôîì.
Äóãà è åå ãðàíè÷íûå âåðøèíû èíöèäåíòíû äðóã äðóãó. Äóãà u=(v, w)
ñ÷èòàåòñÿ ïîëîæèòåëüíî èíöèäåíòíîé åå êîíå÷íîé âåðøèíå w, ãîâîðÿò,
÷òî äóãà (ñòðåëêà) çàõîäèò â âåðøèíó w. Äóãà u ñ÷èòàåòñÿ îòðèöàòåëüíî
èíöèäåíòíîé åå íà÷àëüíîé âåðøèíå v, ãîâîðÿò, ÷òî äóãà èñõîäèò èç ýòîé
âåðøèíû.
×èñëî äóã, çàõîäÿùèõ â âåðøèíó v, íàçûâàåòñÿ ïîëîæèòåëüíîé ñòå-
ïåíüþ v è îáîçíà÷àåòñÿ ÷åðåç δ
+
(v). Îòðèöàòåëüíàÿ ñòåïåíü v îïðåäåëÿ-
åòñÿ àíàëîãè÷íî äëÿ èñõîäÿùèõ äóã è îáîçíà÷àåòñÿ δ
(v). Îðèåíòèðî-
âàííàÿ ïåòëÿ, èíöèäåíòíàÿ v, ñ÷èòàåòñÿ ïîëîæèòåëüíî è îòðèöàòåëüíî
èíöèäåíòíîé ñ v. Ñòåïåíü âåðøèíû ðàâíà δ(v)= δ
+
(v)+ δ
(v).
Ó÷èòûâàÿ, ÷òî êàæäàÿ äóãà ïîëîæèòåëüíî èíöèäåíòíà âåðøèíå è
îòðèöàòåëüíî èíöèäåíòíà òàêæå îäíîé âåðøèíå, ïîëó÷èì
() ()
vV vV
vvU
+−
∈∈
δ=δ=
∑∑
,
ãäå |U| îçíà÷àåò ÷èñëî äóã ãðàôà. Âûøå áûëî ïîêàçàíî äëÿ íåîðèåíòè-
ðîâàííîãî ãðàôà
() 2
vV
vU
∈
δ=
∑
.
1.4.1. Äóãè, èíöèäåíòíûå ïîäìíîæåñòâó âåðøèí
Ïóñòü çàäàí ãðàô G=(V, U) è íåïóñòîå ïîäìíîæåñòâî V
1
ìíîæåñòâà
V (V
1
⊂V). Ãîâîðÿò, ÷òî äóãà u = (v
i
, v
j
) çàõîäèò â V
1
, åñëè v
i
∉V
1
, à v
j
∈V
1
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
