Матрицы графов.
Пусть D = (V, X) – орграф, где V = {v1, …, vn}, X = {x1, … , xm}.
Определение. Матрицей смежности орграфа D называется квадратичная матрица A(D) = [aij] порядка п, у которой
Определение. Если вершина v является крнцом ребра х, то говорят, что v и х – инциндентны.
Определение. Матрицей инциндентности оргафа D называется матрица размерности п´т B(D) = [bij], у которой
Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.
x1
Составим матрицу смежности:
|
| v1 | v2 | v3 |
| v1 | 0 | 1 | 0 |
| v2 | 1 | 0 | 1 |
| v3 | 1 | 0 | 0 |
Т.е.
- матрица смежности.
Матрица инциндентности:
|
| x1 | x2 | x3 | x4 |
| v1 | -1 | 0 | 1 | 1 |
| v2 | 1 | -1 | 0 | -1 |
| v3 | 0 | 1 | -1 | 0 |
Т.е.
Если граф имеет кратные дуги (ребра), то в матрице смежности принимается aij=k, где k – кратность дуги (ребра).
С помощью матриц смежности и инциндентности всегда можно полностью определеить граф и все его компоненты. Такой метод задания графов очень удобен для обработки данных на ЭВМ.
