Главные отличия между матрицами смежности и инцидентности в теории графов:

1. Форма: матрицы смежности всегда имеют форму квадрата, а матрицы инцидентности — форму прямоугольника. 1
2. Обозначения: в матрице смежности вершины представлены и в строках, и в столбцах, а в матрице инцидентности — только в строках, а столбцы обозначают рёбра. 1
3. Размерность: в матрице смежности число строк и столбцов равно числу вершин графа, а в матрице инцидентности — числу вершин и рёбер графа. 24
4. Информативность: матрицы смежности более разрежены, так как в большинстве случаев рёбер всегда больше, чем вершин. 1

Таким образом, матрица смежности описывает смежные вершины, а матрица инцидентности — связь между вершиной в строке и ребром в столбце. 1