Матрица смежности графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлены категории)
м (rollbackEdits.php mass rollback)
 
(не показана 51 промежуточная версия 7 участников)
Строка 1: Строка 1:
== Определение ==
+
__NOTOC__
'''Матрицей смежности''' (англ. 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>, причём при <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"
 
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"
!style="background:#f2f2f2"|Граф
+
!style="background:#f2f2f2"|Взвешенность графа
 +
!style="background:#f2f2f2"|Вид графа
 
!style="background:#f2f2f2"|Матрица смежности
 
!style="background:#f2f2f2"|Матрица смежности
 
|-
 
|-
|style="background:#f9f9f9"|[[Файл:Graph 5-7.png|175px]]
+
!style="background:#f2f2f2"|Не взвешенный граф
 +
|style="background:#f9f9f9"|[[Файл: Adjacency matrix.png|180px]]
 
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
 
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
 
0 & 1 & 0 & 0 & 1\\
 
0 & 1 & 0 & 0 & 1\\
Строка 14: Строка 22:
 
0 & 1 & 1 & 0 & 1\\
 
0 & 1 & 1 & 0 & 1\\
 
1 & 1 & 0 & 1 & 0\\
 
1 & 1 & 0 & 1 & 0\\
 +
\end{pmatrix}</tex>
 +
|-
 +
!style="background:#f2f2f2"|Взвешенный граф
 +
!style="background:#f9f9f9"|[[Файл:weighted_graph.png|180px]]
 +
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
 +
0  & 40 & \infty  & \infty  & 18\\
 +
40 & 0  & 22 & 6  & 15\\
 +
\infty  & 22 & 0  & 14 & \infty \\
 +
\infty  & 6  & 14 & 0  & 20\\
 +
18 & 15 & \infty  & 20 & 0 \\
 
\end{pmatrix}</tex>
 
\end{pmatrix}</tex>
 
|}
 
|}
 +
 +
==Оценка памяти и времени работы==
 +
 +
Матрица смежности занимает <tex>O(|V|^2)</tex> памяти. За <tex>O(1)</tex> можно определить вес ребра или его наличие между любыми двумя вершинами. Такой способ хранения графа хорошо подходит для плотных графов, в которых число рёбер между различными парами вершин <tex>\Omega(|V|^2)</tex>.
  
 
== Свойства ==
 
== Свойства ==
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.
+
{{Утверждение
 +
|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>.
 +
Аналогично сумма элементов <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>-го столбца равны.
 +
}}
 +
 
  
=== Ориентированный граф ===
 
Сумма элементов <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>.
 
  
=== Неориентированный граф ===
+
{{Теорема
Для неориентированных графов матрица смежности является симметричной.
+
|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>.
  
Сумма элементов <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>-го столбца равны.
+
|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
+
== Источники информации ==
 +
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
 +
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Текущая версия на 19:20, 4 сентября 2022


Определение:
Матрицей смежности (англ. Adjacency matrix) [math]A=||\alpha_{i,j}||[/math] невзвешенного графа [math]G=(V,E)[/math] называется матрица [math]A_{[V\times{}V]}[/math], в которой [math]\alpha_{i,j}[/math] — количество рёбер, соединяющих вершины [math]v_i[/math] и [math]v_j[/math], причём при [math]i=j[/math] каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.


Определение:
Матрицей смежности (англ. Adjacency matrix) [math]A=||\alpha_{i,j}||[/math] взвешенного графа [math]G=(V,E)[/math] называется матрица [math]A_{[V\times{}V]}[/math], в которой [math]\alpha_{i,j}[/math] — вес ребра, соединяющего вершины [math]v_i[/math] и [math]v_j[/math].


Примеры матриц смежности:

Взвешенность графа Вид графа Матрица смежности
Не взвешенный граф Adjacency matrix.png [math]\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}[/math]
Взвешенный граф Weighted graph.png [math]\begin{pmatrix} 0 & 40 & \infty & \infty & 18\\ 40 & 0 & 22 & 6 & 15\\ \infty & 22 & 0 & 14 & \infty \\ \infty & 6 & 14 & 0 & 20\\ 18 & 15 & \infty & 20 & 0 \\ \end{pmatrix}[/math]

Оценка памяти и времени работы

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

Свойства

Утверждение:
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц).
Утверждение:
Для графов без петель и кратных рёбер главная диагональ матрицы смежности целиком состоит из нулей.
Утверждение (о сумме элементов строки матрицы смежности для ориентированного графа):
Сумма элементов [math]i[/math]-й строки равна [math]deg^- v_i[/math], то есть [math]\sum\limits_{j=1}^{n}\alpha_{i,j} = deg^- v_i[/math]. Аналогично сумма элементов [math]j[/math]-го стоблца равна [math]deg^+ v_j[/math], то есть [math]\sum\limits_{i=1}^{n}\alpha_{i,j} = deg^+ v_j[/math].


Утверждение (о сумме элементов строки матрицы смежности для неориентированного графа):
Матрица смежности является симметричной.
[math]\triangleright[/math]
Сумма элементов [math]i[/math]-й строки равна [math]deg \; v_i[/math], то есть [math]\sum\limits_{j=1}^{n}\alpha_{i,j} = deg \; v_i[/math]. Вследствие симметричности суммы элементов [math]i[/math]-й строки и [math]i[/math]-го столбца равны.
[math]\triangleleft[/math]


Теорема (о поиске количества путей заданной длины с помощью матрицы смежности ориентированного графа):
Пусть [math]A_{[V\times{}V]}=\alpha_{i,j}[/math]матрица смежности ориентированного графа [math]G=(V,E)[/math] без петель и [math]A^l=\gamma_{i,j}[/math], где [math]l\in\mathbb{N}[/math]. Тогда [math]\gamma_{i,j}[/math] равно количеству путей [math]v_i\leadsto{}v_j[/math] длины [math]l[/math].
Доказательство:
[math]\triangleright[/math]

Утверждение очевидно при [math]l = 1[/math]. Пусть [math]l \gt 1[/math], и утверждение верно для [math]l - 1[/math]. Тогда [math]A^{l-1}=\varepsilon_{i,j}[/math], где [math]\varepsilon_{i,j}[/math] равно количеству путей [math]v_i\leadsto{}v_j[/math] длины [math]l-1[/math]. Следовательно,

[math]\gamma_{i,j}=\sum\limits_{s=1}^{n}{\varepsilon_{i,s}\alpha_{s,j}}[/math]
равно числу путей [math]v_i\leadsto{}v_j[/math] длины [math]l[/math], так как каждый такой маршрут состоит из путей [math]v_i\leadsto{}v_s[/math] длины [math]l-1[/math] и ребра, ведущего из предпоследней вершины [math]v_s[/math] пути в его последнюю вершину [math]v_j[/math].
[math]\triangleleft[/math]

См. также

Источники информации

  • Харари Фрэнк Теория графов Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
  • Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5