Page 74 - 2589

зворотні напрямки. Таку відповідність будемо називати
канонічною.
Граф, що має як ребра, так і дуги, називається мішаним.

Про дугу (ν, w) кажуть, що вона виходить із вершини w та
входить у вершину ν. Іноді вершини ν і w називають відповідно

початком та кінцем дуги (ν, w). Домовимося позначати орграфи
літерою D або D з індексами.

5.2 Представлення графа за допомогою матриць та
списку ребер

Задати граф означає задати множини його вершин і ребер, а
також відношення інцидентності. Коли граф G – скінченний, для

опису його вершин та ребер досить їх занумерувати. Нехай v }{ n
i i 1
m
– вершини графа G; { e } – його ребра. Відношення
i i 1
інцидентності можна означити матрицею Е=||ε ||, що має m рядків
ij
й n стовпців. Стовпці відповідають вершинам графа, а рядки –
його ребрам. Якщо ребро е є інцидентним вершині ν , то ε =1, в
i j ij
іншому випадку ε =0. Це матриця інцидентності звичайного
ij
графа G, яка є одним із способів його визначення (для графа на

рис.4.3,а) її задано в табл. 4.1, а.

а) б)

Рисунок 4.3 – Відповідність вершин і дуг (ребер) у графі

У матриці інцидентності ||ε || орієнтованого графа G, якщо
ij
вершина ν – початок ребра е то ε =−1; якщо ν – кінець е то
j i ij j i
ε =1; якщо е – петля, а ν – інцидентна їй вершина, то ε = α де α
ij i j ij
– будь-яке число, відмінне від 1,0 та -1, в інших випадках ε =0 .
ij
У кожному рядку матриці інцидентності для неорієнтованого
або орієнтованого графа тільки два елементи відмінні від 0 (або

74