4625
правок
Матрица смежности: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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> | <math>\,(0,1)</math>-матрица <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> которой равен <math>\,1</math>, | ||
если вершины <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> и равен <math>\,0</math> в противном случае. | ||
Для [[неориентированный граф|неориентированного графа]] '''матрица смежности''' есть симметричная матрица | Для [[неориентированный граф|неориентированного графа]] '''матрица смежности''' есть симметричная матрица | ||
с нулями на главной диагонали. В '''матрице смежности''' для ''[[мультиграф|мультиграфов]]'' | с нулями на главной диагонали. В '''матрице смежности''' для ''[[мультиграф|мультиграфов]]'' | ||
и ''[[псевдограф|псевдографов]]'' <math>(i,j)</math>-й элемент равен числу [[ребро|ребер]], | и ''[[псевдограф|псевдографов]]'' <math>\,(i,j)</math>-й элемент равен числу [[ребро|ребер]], | ||
соединяющих вершины <math>v_{i}</math>и <math>v_{j}</math> (при этом [[петля]] | соединяющих вершины <math>\,v_{i}</math>и <math>\,v_{j}</math> (при этом [[петля]] | ||
считается как два ребра). | считается как два ребра). | ||
| Строка 15: | Строка 15: | ||
==См. также== | ==См. также== | ||
''[[Приведенная матрица смежности]] | * ''[[Приведенная матрица смежности]],'' | ||
* ''[[Цикломатическая матрица]].'' | |||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||