Изменения

|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>.}} ====Примеры матриц смежности:== Пример ==

!style="background:#f2f2f2"|ГрафВзвешенность графа!style="background:#f2f2f2"|Вид графа

!style="background:#f2f2f2"|Не взвешенный граф|style="background:#f9f9f9"|[[Файл:Graph 5-7Adjacency matrix.png|175px180px]]

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

{{Утверждение|about=== Случай о сумме элементов строки матрицы смежности для ориентированного графа |statement===Сумма элементов <tex>i</tex>-й строки равна <tex>deg^- v_i</tex>, то есть <tex>\sum\limits_{j=1}^{n}\alpha_{i,j} = deg^- v_i</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>. Следовательно, : <tex>\gamma_{i,j}=\sum\limits_{s=1}^{n}{\varepsilon_{i,s}\alpha_{s,j}}</tex>равно числу путей <tex>v_i\leadsto{}v_j</tex> длины <tex>l</tex>, так как каждый такой маршрут состоит из путей <tex>v_i\leadsto{}v_s</tex> длины <tex>l-1</tex> и ребра, ведущего из предпоследней вершины <tex>v_s</tex> пути в его последнюю вершину <tex>v_j</tex>.}}

 == Литература Источники информации ==* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6