Page 25 - 4386

який виходить з початкового графа заміною кожного

неорієнтованого ребра двома протилежно направленими дугами,

що сполучають ті ж самі вершини. Наприклад, для графа G
2
(рис. 2.2) відображення вершин v та v буде наступним:
2
4
Г(v )={v , v , v }, Г(v )={v , v }.
5
2
1
3
3
5
4
2.4 Матриця суміжності, інцидентності
та список ребер графа

Відношення інцидентності для графа можна описати також

матрицею суміжності, матрицею інцидентності та списком

ребер графа. Опишемо докладно кожний із перерахованих

способів.

Занумеруємо всі вершини графа G натуральними числами

від 1 до n.

Матрицею суміжності A графа G називається квадратна

n×n-матриця, в якій елемент a i-го рядка і j-го стовпчика
i,j
дорівнює:

− числу ребер, що з'єднують вершини v та v у випадку
j
i
неорієнтованого графа;

− числу дуг з початком в i-тій вершині та кінцем в j-тій

вершині у випадку орієнтованого графа.

Занумеруємо всі вершини графа G натуральними числами

від 1 до n та всі його ребра натуральними числами від 1 до m.

Матрицею інцидентності B графа G називається n×m-матриця, в

якій елемент b i-го рядка і j-го стовпчика дорівнює:
i,j
1) у випадку неорієнтованого графа:

− 1, якщо ребро e інцидентне вершині v ;
i
j
− 0, якщо ребро e не інцидентне вершині v ;
j
i

24