Page 17 - 4386

виходу вершини) і δ(v)´´ - кількість ребер, що входять у вершину v

(півстепінь входу вершини). Петля дає внесок по одній одиниці в

обидва степені.

В орграфі суми степенів усіх вершин δ(v)´ і δ(v)´´ рівні між

собою і дорівнюють кількості ребер m графа:

∑ ( δ v =) ′ ∑ ( δ v ′′ ) = E . (1.4)

v∈ V v∈ V

Приклад 1.6. Визначити степені вершин орграфа,

зображеного на рис. 1.9.

Розв'язок.

δ(v )´=1, δ(v )´=2, δ(v )´=3,
1
2
3
δ(v )´=2, δ(v )´=2.
4
5
δ(v )´´=2, δ(v )´´=1, δ(v )´´=2,
1
2
3
δ(v )´´=2, δ(v )´´=3.
4
5
∑ δ (v ) = ′ 1+ 2 + 3+ 2 + 2 = 10.
v ∈V
Рисунок 1.9

∑ ( δ v) ′ ′ = 2 +1 + 2 + 2 + 3 =10 .
v ∈V

E = 10.

1.5 Операції над графами

Для графів можна означити операції об’єднання, перетину,

доповнення та дві специфічні операції – вилучення ребра та

вилучення вершини.

Об’єднанням графів G =(V , E ) та G =(V , E ) називається
2
1
2
2
1
1
граф з множиною вершин V ∪V і множиною ребер E ∪E –
1
2
2

1
G=(V ∪V , E ∪E ); позначається G=G ∪G . Об’єднання G=G ∪G
1
2
1
2
1
2
2
1
16