|
Матриця суміжності
Розглянемо наступний граф:
При представленні графа матрицею суміжності інформація про граф зберігається в квадратній матриці (двомірному списку), де елемент a[i,j] дорівнює 1, якщо вершини i та j з’єднані ребром та дорівнює 0, якщо вершини i та j не з’єднані.
Для даного прикладу матриця суміжності матиме вигляд:
|
|
1
|
2
|
3
|
4
|
5
|
|
1
|
0
|
1
|
1
|
1
|
0
|
|
2
|
1
|
0
|
0
|
1
|
1
|
|
3
|
1
|
0
|
0
|
1
|
0
|
|
4
|
1
|
1
|
1
|
0
|
1
|
|
5
|
0
|
1
|
0
|
1
|
0
|
Якщо граф неорієнтований, то матриця суміжності завжди симетрична відносно головної діагоналі.
Розглянемо орієнтований граф:
Матриця суміжності матиме вигляд
| |
1
|
2
|
3
|
4
|
5
|
|
1
|
0
|
1
|
0
|
0
|
0
|
|
2
|
0
|
0
|
0
|
1
|
1
|
|
3
|
1
|
0
|
0
|
1
|
0
|
|
4
|
1
|
0
|
1
|
0
|
0
|
|
5
|
0
|
0
|
0
|
0
|
0
|
Для зваженого графа кожному ребру відповідає деяке число (наприклад, довжина дороги або вартість проїзду) – вага ребра.
В цьому випадку замість одиниць в матриці суміжності зберігають ваги ребер, а при відсутності ребра зберігають спеціальне значення, наприклад, в багатьох задачах зручно при відсутності ребра зберігати дуже велике число – «нескінченість».
Джерела:disted.edu.vn.ua
|
