Page 45 - 2577

Таким чином, кожна вершина в G є вершиною в G, а кожне ребро G є орієнтованим
ребром в G.

Орієнтований шлях із v в v задається послідовністю вершин v v v ...v , де v ,v –
0 k 0 1 2 n i 1 i
орієнтоване ребро; 1 i  n . Довжиною орієнтованого шляху називають кількість ребер, що
утворюють такий шлях.

Орграф V ,E називається зв’язаним, якщо його співвіднесений граф є зв’язаним.
G
Орграф називається сильно зв’язаним, якщо для будь – якої пари вершин a , b V існує
орієнтований шлях із a в b.

G
Нехай V ,E орієнтований граф, який включає в себе петлі. Тоді співвіднесений

s
G
a,b
граф V ,E визначається так:   E s , тоді і тільки тоді, коли для різних вершин a і b
ребро  ba,  G або  ab,  G . На рис. 3.11 показаний співвіднесений граф для орграфа із
рис. 3.10.

Рисунок 3.11 – Співвіднесений граф до графа із рис. 3.10

Віддалю між двома вершинами графа називається довжина найкоротшого шляху між
цими двома вершинами.
Діаметром графа називають найбільшу віддаль між будь-якими двома його
вершинами.

3.1.2 Матриці інцидентності і суміжності

Нехай G – граф, а В – матриця, рядки якої означені вершинами, а стовпці – ребрами
графа. Будемо вважати, що вершини і ребра пронумеровані. Елемент і-го рядка і j-го стовпця
матриці В, який позначається як b , дорівнює одиниці, якщо і-та вершина інцидентна j-ому
ij
ребру, і дорівнює нулю в протилежному випадку. Матриця В називається матрицею
інцидентності. На рис. 3.12 показаний граф і його матриця інцидентності.
e e e e
1 2 3 4
v 1  1 1 1 0
 
v 1 0 0 0
2  
v  0 0 1 1
3
 
v 4  0 0 0 0 

Рисунок 3.12 – Граф та його матриця інцидентності
Із матриці інцидентності можна визначити степінь вершини v
i
n
  
deg v i  b ,
ij
j 1 
де n – кількість вершин графа.
Матриця інцидентності не має великого значення при розгляді орграфів, так як вони
не вміщують інформації яке ребро зорієнтовано. Тому, використовуючи матрицю

42