Матрица смежности графа — различия между версиями
(→Оценка памяти и времени работы) |
(→Примеры матриц смежности:) |
||
Строка 27: | Строка 27: | ||
!style="background:#f9f9f9"|[[Файл:weighted_graph.png|180px]] | !style="background:#f9f9f9"|[[Файл:weighted_graph.png|180px]] | ||
|style="background:#f9f9f9"|<tex>\begin{pmatrix} | |style="background:#f9f9f9"|<tex>\begin{pmatrix} | ||
− | 0 & 40 & | + | 0 & 40 & \infty & \infty & 18\\ |
40 & 0 & 22 & 6 & 15\\ | 40 & 0 & 22 & 6 & 15\\ | ||
− | + | \infty & 22 & 0 & 14 & \infty \\ | |
− | + | \infty & 6 & 14 & 0 & 20\\ | |
− | 18 & 15 & | + | 18 & 15 & \infty & 20 & 0 \\ |
\end{pmatrix}</tex> | \end{pmatrix}</tex> | ||
|} | |} |
Версия 15:59, 6 ноября 2015
Определение: |
Матрицей смежности (англ. Adjacency matrix) | невзвешенного графа называется матрица , в которой — количество рёбер, соединяющих вершины и , причём при каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.
Определение: |
Матрицей смежности (англ. Adjacency matrix) | взвешенного графа называется матрица , в которой — вес ребра, соединяющего вершины и .
Примеры матриц смежности:
Взвешенность графа | Вид графа | Матрица смежности |
---|---|---|
Не взвешенный граф | ||
Взвешенный граф |
Оценка памяти и времени работы
Матрица смежности занимает
памяти. За можно определить вес ребра или есть ли ребро между двумя вершинами. Из этого следует, что если граф маленький и мало ребер, то такой метод использовать хуже, чем список ребер, но если граф большой и в нем много ребер, то лучше использовать матрицу смежности.Свойства
Утверждение: |
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц). |
Утверждение: |
Для графов без петель и кратных рёбер главная диагональ матрицы смежности целиком состоит из нулей. |
Утверждение: |
У матрицы смежности ориентированного графа сумма элементов -й строки равна , то есть .
Аналогично сумма элементов -го стоблца равна , то есть . |
Утверждение: |
Для неориентированных графов матрица смежности является симметричной. |
Сумма элементов | -й строки равна , то есть . Вследствие симметричности суммы элементов -й строки и -го столбца равны.
Теорема: |
Пусть матрица смежности ориентированного графа без петель и , где . Тогда равно количеству путей длины . — |
Доказательство: |
Утверждение очевидно при . Пусть , и утверждение верно для . Тогда , где равно количеству путей длины . Следовательно, |
См. также
Источники информации
- Харари Фрэнк Теория графов Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5