Page 16 - 4386

4. Повний граф К з n вершинами має n(n-1)/2 ребер. Дійсно,
n
степінь кожної з n вершин дорівнює n-1, тому за формулою (1.1):

2 E = ∑ δ (v ) =n ( −n ) 1 , (1.2)

v ∈V

звідки кількість ребер дорівнює

E = n ( −n 2 / ) 1 . (1.3)

5. У довільному графі сума степенів вершин парна.

6. У будь-якому графі кількість вершин, степінь яких

непарний, парна.

Граф, усі вершини якого мають степінь r

(δ(v )=δ(v )=…=δ(v )=δ(v)=r) називається регулярним
1
n
2
(однорідним) степеня r. Регулярні графи степеня 0, 1 та 2 за
своїми структурними властивостями є досить простими. Перші

“цікаві” регулярні графи мають степінь 3 – вони називаються

кубічними.

Приклад 1.5. Визначити степені вершин та кількість ребер

графа, зображеного на рис. 1.8.

Розв'язок.

δ(v )=2, δ(v )=2, δ(v )=3,
2
3
1
δ(v )=4, δ(v )=3, δ(v )=4.
5
4
6
2 E = ∑ δ (v ) = 2 + 2 + 3 +4 +
v ∈V
+ 3 + 4 = 18.

E = 9. Рисунок 1.8

Таким чином, у розглянутому графі дев’ять ребер і дві

вершини непарного степеня – v та v .
5
3
Для орієнтованого графа визначаються два степені вершин:
δ(v)´ - кількість ребер, що виходять із вершини v (півстепінь

15