Page 51 - 4496

 -канонічна відповідність двох графів.

Граф, що має як ребра, так і дуги називається мішаним.
Кількість дуг, що виходять з вершини a i, називають
-
ступенем її виходу d , заходять у a - ступенем заходу d i + ,
i
i
-
+
сума ступенів результату і заходу (d =d +d ) - ступенем
i
i
i
вершини i.
3.3 Задання графа за допомогою матриці
інцидентності
Задати граф означає задати множини його вершин і
ребер та відношення інцидентності. Коли граф G – скінчений
V , V ,...., V
його вершини та ребра нумерують: 1 2 n - вершини
e , e ,.... e
графа G; 1 2 m - його ребра. Відношення інциндентності
можна задати матрицею E, що має m рядків і n стовпців.
Елементи цієї матриці  , i  , 1 m , j  n , 1 ;   1
ij ij
Якщо ребро e мультиграф вершині V j і  ij  0 в
i
протилежному випадку. Ця матриця інцидентності звичайного
графа є способом його визначення.

е 10 V 7 е 9

V 6 е 11 V 5

е 8 е 7
е 5 е 6 е 4
V 4 V 3
е 1 е 3 е 2

е 1
V 2 V 1
Рисунок 3.6 – Звичайний граф
48