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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлены категории)
(вставка шаблона)
Строка 1: Строка 1:
== Определение ==
+
__NOTOC__
'''Матрицей смежности''' (англ. Adjacency matrix) <tex>A=||\alpha_{i,j}||</tex> ''помеченного графа'' <tex>G(V,E)</tex> называется матрица <tex>A_{[V\times{}V]}</tex>, в которой <tex>\alpha_{i,j}</tex> — количество рёбер, соединяющих вершины <tex>v_i</tex> и <tex>v_j</tex>, причём при <tex>i=j</tex> каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.
+
{{Определение
 +
|definition ='''Матрицей смежности''' (англ. Adjacency matrix) <tex>A=||\alpha_{i,j}||</tex> ''помеченного графа'' <tex>G(V,E)</tex> называется матрица <tex>A_{[V\times{}V]}</tex>, в которой <tex>\alpha_{i,j}</tex> — количество рёбер, соединяющих вершины <tex>v_i</tex> и <tex>v_j</tex>, причём при <tex>i=j</tex> каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.
 +
}}
  
=== Пример ===
+
== Пример ==
 
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"
 
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"
 
!style="background:#f2f2f2"|Граф
 
!style="background:#f2f2f2"|Граф
Строка 20: Строка 22:
 
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.
 
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.
  
=== Ориентированный граф ===
+
=== Случай ориентированного графа ===
Сумма элементов <tex>i</tex>-й строки равна <tex>\deg^- v_i</tex>, то есть <math>\sum_{j=1}^{n}\alpha_{i,j} = \deg^- v_i</math>.
+
Сумма элементов <tex>i</tex>-й строки равна <tex>\deg^- v_i</tex>, то есть <tex>\sum\limits_{j=1}^{n}\alpha_{i,j} = \deg^- v_i</tex>.
Аналогично сумма элементов <tex>j</tex>-го стоблца равна <tex>\deg^+ v_j</tex>, то есть <math>\sum_{i=1}^{n}\alpha_{i,j} = \deg^+ v_j</math>.
+
Аналогично сумма элементов <tex>j</tex>-го стоблца равна <tex>\deg^+ v_j</tex>, то есть <tex>\sum\limits_{i=1}^{n}\alpha_{i,j} = \deg^+ v_j</tex>.
  
=== Неориентированный граф ===
+
=== Случай неориентированного графа ===
 
Для неориентированных графов матрица смежности является симметричной.
 
Для неориентированных графов матрица смежности является симметричной.
  
Сумма элементов <tex>i</tex>-й строки равна <tex>\deg v_i</tex>, то есть <math>\sum_{j=1}^{n}\alpha_{i,j} = \deg v_i</math>. В следствии симметричности суммы элементов <tex>i</tex>-й строки и <tex>i</tex>-го столбца равны.
+
Сумма элементов <tex>i</tex>-й строки равна <tex>\deg v_i</tex>, то есть <tex>\sum\limits_{j=1}^{n}\alpha_{i,j} = \deg v_i</tex>. В следствии симметричности суммы элементов <tex>i</tex>-й строки и <tex>i</tex>-го столбца равны.
  
 
== См. также ==
 
== См. также ==

Версия 00:17, 14 октября 2010


Определение:
Матрицей смежности (англ. Adjacency matrix) [math]A=||\alpha_{i,j}||[/math] помеченного графа [math]G(V,E)[/math] называется матрица [math]A_{[V\times{}V]}[/math], в которой [math]\alpha_{i,j}[/math] — количество рёбер, соединяющих вершины [math]v_i[/math] и [math]v_j[/math], причём при [math]i=j[/math] каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.


Пример

Граф Матрица смежности
Graph 5-7.png [math]\begin{pmatrix} 0 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0\\ \end{pmatrix}[/math]

Свойства

Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.

Случай ориентированного графа

Сумма элементов [math]i[/math]-й строки равна [math]\deg^- v_i[/math], то есть [math]\sum\limits_{j=1}^{n}\alpha_{i,j} = \deg^- v_i[/math]. Аналогично сумма элементов [math]j[/math]-го стоблца равна [math]\deg^+ v_j[/math], то есть [math]\sum\limits_{i=1}^{n}\alpha_{i,j} = \deg^+ v_j[/math].

Случай неориентированного графа

Для неориентированных графов матрица смежности является симметричной.

Сумма элементов [math]i[/math]-й строки равна [math]\deg v_i[/math], то есть [math]\sum\limits_{j=1}^{n}\alpha_{i,j} = \deg v_i[/math]. В следствии симметричности суммы элементов [math]i[/math]-й строки и [math]i[/math]-го столбца равны.

См. также

Литература

  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
  • Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5