Задання графа за допомогою матриці суміжності
Матриця суміжності графа – це квадратна матриця = ||ij||, стовпцям і рядкам якої відповідають вершини графа. Для неорієнтованого графа ij дорівнює кількості ребер, інцидентних i-й та j-й вершинам, для орієнтованого графа цей елемент матриці суміжності відповідає кількості ребер з початком в i-й вершині й кінцем у j-й. Таким чином, матриця суміжності неорієнтованого графа є симетричною, а орієнтованого – необов’язково.
Граф може бути поданий різними способами: може бути зображений на рисунку, заданий матрицею інцидентності, списком ребер або матрицею суміжності.
Означення. Нехай існує бієкція , яка діє з множини вершин графа G на множину вершин графа H так, що для будь-яких вершин v1 та v2 графа H їхні образи (v1) і (v2) є суміжними в H тоді й тільки тоді, коли v1 та v2 – суміжні в G. Така бієкція називається ізоморфізмом графа G на граф H, а графи G і H – ізоморфними.
Наприклад, графи зображені на рисунку, є ізоморфними.
а)
б)
в)
4
1
2
3
2
3
1
4
1
2
4
1
Матриці суміжності для графів, зображених на рисунках а) та б), мають відповідно вигляд:
а) |
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
|
б) |
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
v1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
v1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
v2 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
v2 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
v3 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
v3 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
v4 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
v4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
v5 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
v5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
v6 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
v6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
v7 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
v7 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |