Матрица смежности и матрица инцидентности

Графы Г и Г ₀ можно представить в аналитической форме либо матрицей смежности A, либо матрицей инцидентности B. Для нашего конкретного неориентированного графа Г матрицы A и B выглядят следующим образом:

A(Г) =	B(Г) =

Матрица смежности для неориентированного графа всегда симметрична. Фигурирующая в ней 2 может быть в некоторых случаях заменена на 1. В матрице инцидентности сумма единиц по столбцам указывает на степень вершины v_i. Нередко расположение вершин и ребер в этой матрице меняют местами (транспонируют). Так, для нашего конкретного орграфа Г ₀ матрица A и B выглядят иначе:

A(Г0) =	B(Г0) =

В общем случае матрица смежности для ориентированного графа уже не будет симметричной. В матрице инцидентности ставится 1, если дуга исходит из вершины, и – 1, если дуга заходит в нее.

Число дуг в пути минимальной длины от вершины v_i до v_j называется расстоянием r (v_i, v_j). Если между вершинами не существует никакого пути, то расстояние равно бесконечноти: r (v_i, v_j) = ∞.