748
правок
Изменения
→Оценка памяти и времени работы
__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> каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.
}}
!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>. Следовательно,
== См. также ==
* [[Матрица инцидентности графа]]
