Page 300 - 6197

Рисунок Д3.4 –
Рисунок Д3.3 – Граф з Мультиграф
петлею
 
Степеню вершини V (позначають deg V ) називають
кількість ребер, які інцидентні даній вершині V. Вершина
степені 0 називається ізольованою.
У неорієнтованому графі сума всіх степенів вершин
дорівнює подвоєному числу ребер
n
 deg V i 2m ,
  
i 1
де n , m - кількість вершин і кількість ребер неорієнтованого
графа.

Нехай G  G V ,E – граф з вершинами V , V ,..., V  V і
1
k
0
ребрами e , e ,..., e  E . Шляхом довжини k із V в V
1 2 k 0 k
називається послідовність V eV e V e ...V e V така, що
0 1 1 2 2 3 k 1 k k

e  V ,V . Коротко шлях позначають як V , V ,..., V . Таким
i i 1 i 0 1 k
чином, шлях довжиною k має k ребер. Простим шляхом із
V в V називають шлях, в якому немає вершин, що
0 k
повторюються.
Приклад Д3.2. У графі, який показаний на рис Д3.5, шлях
V VV V V є простим шляхом.
0 1 2 5 7
Граф G називається зв’язаним, якщо є шлях між будь-
якими двома його різними вершинами. Граф, який показаний
на рис. Д3.5 є зв’язаним графом, а граф на рис. Д3.6 – не
зв’язаний.

300