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

Материал из 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]]
 
==См. также==
''[[Приведенная  матрица смежности]]. [[Цикломатическая матрица]]''.
==Литература==
==Литература==
[Лекции]
[Лекции]

Версия от 20:05, 23 ноября 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

См. также

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

Литература

[Лекции]