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

Матрица смежности (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}$ (при этом петля считается как два ребра).