Некоторые основные характеристики матрицы смежности в теории графов:

• Квадратная форма. 4 Каждая строка и столбец матрицы соответствуют одной вершине графа. 4
• Бинарность. 2 Для графов без петель и кратных рёбер матрица смежности состоит из нулей и единиц. 2
• Симметричность. 14 Матрица симметрична относительно главной диагонали, так как ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней. 14
• Количество единиц. 13 Если граф неориентированный, то число единиц в матрице равно удвоенному числу рёбер в графе. 1
• Связь между строками и столбцами. 1 Ячейка в позиции (i, j) равна 1, когда существует ребро между вершинами i и j. 1 Если ребра между вершинами i и j не существует, то ставится 0. 1
• Связь между строками и степенями вершин. 3 Число единиц в i-строке матрицы смежности простого графа равно степени i-вершины, а в j-столбце — степени j-вершины. 3