Составители:
Рубрика:
13
1.3.3. Ñòåïåíü âåðøèíû
Ñòåïåíüþ âåðøèíû δ(v) íàçûâàåòñÿ ÷èñëî êîíöîâ ðåáåð, èíöèäåíò-
íûõ âåðøèíå v (ò. å. ïåòëÿ ó÷èòûâàåòñÿ äâàæäû). Íàïðèìåð, δ(v
3
)=5
(ðèñ. 1.4).
Èçîëèðîâàííîé âåðøèíîé íàçûâàåòñÿ òà, äëÿ êîòîðîé δ(v)=0, íàïðè-
ìåð δ(v
4
)=0 (ðèñ. 1.4).
Âûðîæäåííûì íàçûâàåòñÿ ãðàô, ó êîòîðîãî âñå âåðøèíû èçîëèðî-
âàíû.
Ïóñòü äàíî |V| ÷èñëî âåðøèí, à |
U
| ÷èñëî ðåáåð êîíå÷íîãî ãðàôà
G=(V,
U
). Ïîÿâëåíèå êàæäîãî íîâîãî ðåáðà äîáàâëÿåò ïî åäèíèöå ê
ñòåïåíÿì äâóõ âåðøèí (èëè â ñëó÷àå ïåòëè äîáàâëÿåò äâà ê ñòåïåíè
îäíîé âåðøèíû), ïîýòîìó ñïðàâåäëèâî âûðàæåíèå
()
vV
v
∈
δ
∑
= 2|
U
|, ò. å.
ýòî ÷åòíîå çíà÷åíèå.
Åñëè V
0
è V
1
ìíîæåñòâà âåðøèí, èìåþùèõ ÷åòíûå è íå÷åòíûå
ñòåïåíè ñîîòâåòñòâåííî, òî çíà÷åíèå
0
()
vV
v
∈
δ
∑
÷åòíî, òàê êàê ýòî êîíå÷-
íàÿ ñóììà ÷åòíûõ
÷èñåë. Îòñþäà ñëåäóåò, ÷òî çíà÷åíèå
()
vV
v
∈
δ
∑
0
()
vV
v
∈
δ
∑
=
1
()
vV
v
∈
δ
∑
òàêæå îáÿçàòåëüíî ÷åòíî, ÷òî äîêàçûâàåò ñëåäóþùåå óòâåðæäåíèå: â
êîíå÷íîì ãðàôå ÷èñëî âåðøèí íå÷åòíîé ñòåïåíè ÷åòíî. Íàïðèìåð, äëÿ
ãðàôà ðèñ.1.4 èìååì δ(v
1
)=2, δ(v
2
)=3, δ(v
3
)=5, δ(v
4
)=0, îòñþäà
δ(v
1
)+δ(v
4
)=2, δ(v
2
)+δ(v
4
)=8.
1.3.4. Ðàçäåëåíèå íåîðèåíòèðîâàííîãî ãðàôà
íà ñîñòàâëÿþùèå
Ðàññìîòðèì ïîíÿòèÿ, èñïîëüçóåìûå äëÿ âûäåëåíèÿ âàæíåéøèõ ÷àñ-
òåé ãðàôà. Ïóñòü çàäàí ãðàô G=(V,
U
) (ðèñ.1.4).
Ñóãðàôîì ãðàôà G íàçûâàåòñÿ ãðàô G'=(V,
U
'), ãäå
U
'⊂
U
, ò. å.
ñóãðàô ïîëó÷àåòñÿ èç èñõîäíîãî ãðàôà óäàëåíèåì íåêîòîðîãî ÷èñëà ðå-
áåð (ñ ñîõðàíåíèåì âåðøèí). Íàïðèìåð, íà ðèñ. 1.5,à ïîêàçàí ñóãðàô
ãðàôà (ðèñ. 1.4) áåç êðàòíûõ ðåáåð è ïåòåëü.
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
