61
правка
Изменения
Новая страница: «== Определение == '''Матрицей смежности''' (англ. Adjacency matrix) <tex>A=||\alpha_{i,j}||</tex> ''помеченного графа…»
== Определение ==
'''Матрицей смежности''' (англ. 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"
!style="background:#f2f2f2"|Граф
!style="background:#f2f2f2"|Матрица смежности
|-
|style="background:#f9f9f9"|[[Файл:Graph 5-7.png|175px]]
|style="background:#f9f9f9"|<tex>\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}</tex>
|}
== Свойства ==
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.
=== Ориентированный граф ===
Сумма элементов <tex>i</tex>-й строки равна <tex>\deg^- v_i</tex>, то есть <math>\sum_{j=1}^{n}\alpha_{i,j} = \deg^- v_i</math>.
Аналогично сумма элементов <tex>j</tex>-го стоблца равна <tex>\deg^+ v_j</tex>, то есть <math>\sum_{i=1}^{n}\alpha_{i,j} = \deg^+ v_j</math>.
=== Неориентированный граф ===
Для неориентированных графов матрица смежности является симметричной.
Сумма элементов <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>-го столбца равны.
== См. также ==
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
== Литература ==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
'''Матрицей смежности''' (англ. 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"
!style="background:#f2f2f2"|Граф
!style="background:#f2f2f2"|Матрица смежности
|-
|style="background:#f9f9f9"|[[Файл:Graph 5-7.png|175px]]
|style="background:#f9f9f9"|<tex>\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}</tex>
|}
== Свойства ==
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.
=== Ориентированный граф ===
Сумма элементов <tex>i</tex>-й строки равна <tex>\deg^- v_i</tex>, то есть <math>\sum_{j=1}^{n}\alpha_{i,j} = \deg^- v_i</math>.
Аналогично сумма элементов <tex>j</tex>-го стоблца равна <tex>\deg^+ v_j</tex>, то есть <math>\sum_{i=1}^{n}\alpha_{i,j} = \deg^+ v_j</math>.
=== Неориентированный граф ===
Для неориентированных графов матрица смежности является симметричной.
Сумма элементов <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>-го столбца равны.
== См. также ==
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
== Литература ==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
