Матрицы графов.
Пусть 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 — кратность дуги (ребра).
С помощью матриц смежности и инциндентности всегда можно полностью определеить граф и все его компоненты. Такой метод задания графов очень удобен для обработки данных на ЭВМ.
