Матрица смежности: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 12: Строка 12:
'''Матрица смежности''' определяет ''[[граф]]'' (''[[орграф]], мультиграф, псевдограф'') с точностью до ''[[изоморфизм графов|изоморфизма]]''.
'''Матрица смежности''' определяет ''[[граф]]'' (''[[орграф]], мультиграф, псевдограф'') с точностью до ''[[изоморфизм графов|изоморфизма]]''.


[[Файл:Adjacency matrix.png|500px]]
[[Файл:Adjacency matrix.png|600px]]


==См. также==  
==См. также==  

Версия от 12:47, 24 ноября 2009

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

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

Adjacency matrix.png

См. также

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

Литература

[Лекции]