Що таке матриця суміжності?
Матриця суміжності - це спосіб представлення графа у вигляді квадратної таблиці (матриці), де рядки і стовпці відповідають вершинам, а значення в комірках показують, чи є між ними ребро.
Визначення
Для графа з вершинами ( V = {v_1, v_2, ..., v_n} ):
матриця суміжності - це матриця ( A[n][n] ), де
[
A[i][j] =
\begin{cases}
1, & \text{якщо є ребро з } v_i \text{ в } v_j,
0, & \text{якщо ребра немає.}
\end{cases}
]
Якщо граф зважений, то замість 1 і 0 у комірці зберігається вага ребра.
Приклад (неорієнтований граф)
Ребра: A-B, A-C, B-C
A B C
A [ 0 1 1 ]
B [ 1 0 1 ]
C [ 1 1 0 ]Матриця симетрична відносно діагоналі (A-B = B-A).
Приклад (орієнтований граф)
Ребра: A→B, B→C
A B C
A [ 0 1 0 ]
B [ 0 0 1 ]
C [ 0 0 0 ]Особливості
- Розмір матриці завжди n × n, де n - число вершин.
- A[i][j] = 1 - є зв'язок, A[i][j] = 0 - немає зв'язку.
- У орієнтованих графах матриця несиметрична.
- Петля (ребро з вершини в саму себе) відображається на діагоналі.
Підсумок: матриця суміжності - це таблиця, де за координатами двох вершин можна миттєво дізнатися, чи є між ними ребро (і яка в нього вага).
Коротка відповідь
Для співбесідиКоротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.