Аноним

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

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


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


См. также ''Приведенная  матрица смежности. Цикломатическая матрица''.
[[Файл:Adjacency matrix.png|500px]]
 
==См. также==
''[[Приведенная  матрица смежности]]. [[Цикломатическая матрица]]''.
==Литература==
==Литература==
[Лекции]
[Лекции]