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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Adjacency matrix.png

См. также

Литература

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