В математике , в теории графов , матрица смежности Зейделя простого неориентированного графа G — это симметричная матрица со строкой и столбцом для каждой вершины, имеющая 0 на диагонали, −1 для позиций, строки и столбцы которых соответствуют смежным вершинам, и +1 для позиций, соответствующих несмежным вершинам. Она также называется матрицей Зейделя или — ее первоначальное название — (−1,1,0) -матрицей смежности . Ее можно интерпретировать как результат вычитания матрицы смежности графа G из матрицы смежности дополнения графа G.
Мультимножество собственных значений этой матрицы называется спектром Зейделя .
Матрица Зейделя была введена Дж. Х. ван Линтом и Йоханом Якобом Зейделем в 1966 году и широко использовалась Зейделем и соавторами.
Матрица Зейделя графа G также является матрицей смежности полного знакового графа K G , в котором ребра графа G отрицательны, а ребра, не входящие в G , положительны. Это также матрица смежности двумерного графа, связанного с G и K G .
Свойства собственных значений матрицы Зейделя представляют ценность при изучении сильно регулярных графов .