Матрица смежности Зейделя

В математике , в теории графов , матрица смежности Зейделя простого неориентированного графа G представляет собой симметричную матрицу со строкой и столбцом для каждой вершины, имеющую 0 на диагонали, -1 для позиций, строки и столбцы которых соответствуют соседним вершинам, и +1 для позиций, соответствующих несмежным вершинам.Ее еще называют матрицей Зейделя или — ее первоначальное название — (−1,1,0) -матрицей смежности . Его можно интерпретировать как результат вычитания смежности G G из матрицы дополнения смежности матрицы .

Мультимножество значений собственных этой матрицы называется спектром Зейделя .

Матрица Зейделя была представлена ​​Дж. Х. ван Линтом и Йоханом Якобом Зейделем в 1966 году и широко использовался Зайделем и соавторами.

Матрица Зейделя графа G также является матрицей смежности полного графа со знаком K _G, в котором ребра G отрицательны, а ребра, не входящие в G, положительны. Это также матрица смежности двухграфа, связанного с G и K _G .

Свойства собственных значений матрицы Зейделя ценны при изучении сильно регулярных графов .

Ссылки

• ван Линт, Дж. Х., и Зайдель, Дж. Дж. (1966), Равносторонние множества точек в эллиптической геометрии. Indagationes Mathematicae , vol. 28 (= Proc. Kon. Ned. Aka. Wet. Ser. A , т. 69), стр. 335–348.
• Зайдель, Дж.Дж. (1976), Обзор двух графов. В: Международный коллоквиум по комбинаторным теориям (Труды, Рим, 1973), том. я, стр. 481–511. Материалы Линцианских конференций, № 17. Национальная академия Линчеи, Рим.
• Зайдель, Дж. Дж. (1991), изд. Д. Г. Корней и Р. Матон, Геометрия и комбинаторика: Избранные труды Дж. Дж. Зейделя . Бостон: Академическая пресса. Во многих статьях используется матрица Зейделя.
• Зайдель, Дж. Дж. (1968), Сильно регулярные графы с (-1,1,0) матрицей смежности, имеющей собственное значение 3. Линейная алгебра и ее приложения 1, 281–298.