1632
правки
Изменения
м
0 \infty & 22 & 0 & 14 & 0 \infty \\0 \infty & 6 & 14 & 0 & 20\\18 & 15 & 0 \infty & 20 & 0 \\
=== Случай ориентированного графа ===
=== Случай неориентированного графа ===
===Связь степени матрицы смежности и количества путей===
* [[Связь степени матрицы смежности и количества путей]]
rollbackEdits.php mass rollback
__NOTOC__
{{Определение
|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> каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.
}}
{{Определение|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>.}} ====Примеры матриц смежности:== Пример ==
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"
!style="background:#f2f2f2"|Взвешенность графа
!style="background:#f9f9f9"|[[Файл:weighted_graph.png|180px]]
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
0 & 40 & 0 \infty & 0 \infty & 18\\
40 & 0 & 22 & 6 & 15\\
\end{pmatrix}</tex>
|}
==Оценка памяти и времени работы==
Матрица смежности занимает <tex>O(|V|^2)</tex> памяти. За <tex>O(1)</tex> можно определить вес ребра или его наличие между любыми двумя вершинами. Такой способ хранения графа хорошо подходит для плотных графов, в которых число рёбер между различными парами вершин <tex>\Omega(|V|^2)</tex>.
== Свойства ==
}}
{{Утверждение
|about=о сумме элементов строки матрицы смежности для ориентированного графа
|statement=Сумма элементов <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>, то есть <tex>\sum\limits_{i=1}^{n}\alpha_{i,j} = deg^+ v_j</tex>.
}}
{{Утверждение
|about=о сумме элементов строки матрицы смежности для неориентированного графа|statement=Для неориентированных графов матрица Матрица смежности является симметричной.
|proof=
Сумма элементов <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>-го столбца равны.
}}
{{Теорема
|about=о поиске количества путей заданной длины с помощью матрицы смежности ориентированного графа|statement=Пусть <tex>A_{[V\times{}V]}=\alpha_{i,j}</tex> — [[Матрица смежности графа|матрица смежности]] [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|ориентированного графа]] <tex>G=(V,E)</tex> без петель и <tex>A^l=\gamma_{i,j}</tex>, где <tex>l\in\mathbb{N}</tex>. Тогда <tex>\gamma_{i,j}</tex> равно количеству путей <tex>v_i\leadsto{}v_j</tex> длины <tex>l</tex>.
|proof=Утверждение очевидно при <tex>l = 1</tex>. Пусть <tex>l > 1</tex>, и утверждение верно для <tex>l - 1</tex>. Тогда <tex>A^{l-1}=\varepsilon_{i,j}</tex>, где <tex>\varepsilon_{i,j}</tex> равно количеству путей <tex>v_i\leadsto{}v_j</tex> длины <tex>l-1</tex>. Следовательно,
== См. также ==
* [[Матрица инцидентности графа]]
