Матрицы графов.
Пусть D = (V, X) – орграф, где V = {v1, …, vn}, X = {x1, … , xm}.
Определение. Матрицей смежности орграфа D называется квадратичная матрица A(D) = [aij] порядка п, у которой
Определение.
Если вершина v является крнцом ребра х, то говорят, что v и х – инциндентны.
Определение. Матрицей инциндентности оргафа D называется матрица размерности п´т B(D) = [bij], у которой
Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.
x1
v1 x4 v2
x2
x3
v3
Составим матрицу смежности:
| 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 – кратность дуги (ребра).
С помощью матриц смежности и инциндентности всегда можно полностью определеить граф и все его компоненты.
Такой метод задания графов очень удобен для обработки данных на ЭВМ.
Пример. Задана симметрическая матрица Q неотрицательных чисел. Нарисовать на плоскости граф G(V, X), имеющий заданную матицу Q своей матрицей смежности. Найти матрицу инциндентности R графа G. Нарисованть также орграф 
, имеющий матрицу смежности Q, определить его матрицу инциндентности С.
x4
x3
v2
x2 x5
x6
x1 v1 v3 x7 x8
x10
x11 x9
v4
Составим матрицу инциндентности:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | |
| v1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| v2 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| v3 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| v4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
Итого: 
Построим теперь ориентированный граф с заданной матрицей смежности.
x4
x5
 |
v2
x2 x7
х3 x6
x1 v1 х8 v3 x10 x11
х9
х17 х15 x14
x16 х13 x12
v4
Составим матрицу инцидентности для ориентированного графа.
Элемент матрицы равен 1, если точка является концом дуги, –1 – если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.
Таким образом, операции с графами можно свести к операциям с их матрицами.