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

Матрица смежности (Adjacency matrix, connectivity matrix, vertex incidence matrix) — $(0,1)$-матрица $A(G)$ размером $n\times n$ ($n$ — число вершин в $G$), $(i,j)$-й элемент $a_{ij}$ которой равен $1$, если вершины $v_i$ и $v_j$ смежны, т.е. соединены дугой (или ребром) $(v_i,v_j)$ и равен $0$ в противном случае. Для неориентированного графа матрица смежности есть симметричная матрица с нулями на главной диагонали. В матрице смежности для мультиграфов и псевдографов $(i,j)$-й элемент равен числу ребер, соединяющих вершины $v_i$и $v_j$ (при этом петля считается как два ребра).

Матрица смежности определяет граф (орграф, мультиграф, псевдограф) с точностью до изоморфизма.

См. также

• Приведенная матрица смежности,
• Цикломатическая матрица.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.