Изменения

|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> каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.

0 & 40 & 0 \infty & 0 \infty & 18\\

0 \infty & 22 & 0 & 14 & 0 \infty \\0 \infty & 6 & 14 & 0 & 20\\18 & 15 & 0 \infty & 20 & 0 \\

 Матрица смежности занимает <tex>O(|V|^2)</tex> памяти. За <tex>O(1)</tex> можно определить вес ребра или его наличие между любыми двумя вершинами. Такой способ хранения графа хорошо подходит для плотных графов, поиск ребра в ней происходит за которых число рёбер между различными парами вершин <tex>O\Omega(1|V|^2)</tex>.

|statementabout=У о сумме элементов строки матрицы смежности для ориентированного графа сумма |statement=Сумма элементов <tex>i</tex>-й строки равна <tex>deg^- v_i</tex>, то есть <tex>\sum\limits_{j=1}^{n}\alpha_{i,j} = deg^- v_i</tex>.

|about=о сумме элементов строки матрицы смежности для неориентированного графа|statement=Для неориентированных графов матрица Матрица смежности является симметричной.

|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>.