Page 12 - 4336

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

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

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

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

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

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

кубічними.

Для орієнтованого графа визначаються два степені вершин:

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

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

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

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

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

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

 (  v )   (  v  )  m . (1.4)

v V v V

1.3 Способи задання графів

Задати граф – означає описати множини його вершин і

ребер, а також відношення інцидентності. Для цього досить
занумерувати вершини і ребра графа.

1.3.1 Задання графа за допомогою діаграми

Граф G=(V, E) зручно зображати за допомогою рисунка на

площині, який називають діаграмою графа G. Вершинам графа G

ставляться у відповідність точки площини; точки, що

відповідають вершинам v та w, з’єднуються лінією (відрізком або

12