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

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

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

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

Литература

[Лекции]