Средство представления, какие вершины (или узлы) графа смежны с какими другими вершинами.
Матрица смежности конечного графа G на n вершинах представляет собой матрицу nxn , где недиагональный элемент aij представляет собой число ребер из вершины i до вершины j , а диагональный элемент aii , в зависимости от соглашения, равен одному или двум числам ребер (петель) от вершины . ] я к себе.
Ненаправленные графы часто используют последнее соглашение о счетных циклах дважды, тогда как ориентированные графы обычно используют первое соглашение.
Существует уникальная матрица смежности для каждого класса графов изоморфизма (с точностью до перестановки строк и столбцов), и она не является матрицей смежности любого другого класса графов изоморфизма . [112 ]
В частном случае конечного простого графа матрица смежности представляет собой (0,1) -матрицу с нулями на диагонали.
Если граф ненаправленный, матрица смежности симметрична.
Связь между графом и собственными значениями и собственных векторов его матрицы смежности изучается в теории спектральных графов.