Матрица смежности
Матрица смежности — это квадратная таблица, которая показывает, соединены ли пары вершин графа ребрами. По строке и столбцу можно определить, есть ли ребро между выбранными вершинами.
Правило построения
Сначала составляют список вершин и нумеруют их. Затем создают таблицу: названия вершин записывают и в заголовок строк, и в заголовок столбцов. Для каждой пары вершин ставят \(1\), если они соединены ребром, и \(0\) — если не соединены. В неориентированном графе матрица симметрична относительно главной диагонали: если \(i\) смежна с \(j\), то и \(j\) смежна с \(i\). Главная диагональ обычно заполнена нулями, потому что в простом графе нет ребер из вершины в саму себя.
Пусть в графе три вершины: \(A\), \(B\), \(C\). Ребра соединяют \(A\) с \(B\) и \(B\) с \(C\), но \(A\) и \(C\) не соединены. Тогда матрица смежности имеет вид:
\(\begin{array}{c|ccc}&A&B&C\\\hline A&0&1&0\\ B&1&0&1\\ C&0&1&0\end{array}\)
Например, число в строке \(B\) и столбце \(C\) равно \(1\), значит, вершины \(B\) и \(C\) смежны. Сумма элементов строки показывает степень вершины в простом неориентированном графе.
Матрица смежности отличается от матрицы инцидентности. В матрице смежности и строки, и столбцы соответствуют вершинам, поэтому она имеет размер \(n\times n\). В матрице инцидентности строки обычно соответствуют вершинам, а столбцы — ребрам. Для ориентированного графа матрица смежности не обязана быть симметричной: направление ребра учитывается.
В матрице смежности неориентированного графа элемент \(a_{24}=1\). Что обязательно верно?
Главное
- Матрица смежности — квадратная таблица связей между вершинами графа.
- В простом графе \(1\) означает наличие ребра, а \(0\) — его отсутствие; диагональ обычно состоит из нулей.
- В неориентированном графе матрица симметрична, а сумма строки равна степени соответствующей вершины.