Разница между матрицей инцидентности и матрицей смежности в теории графов заключается в том, как они описывают связи между элементами графа. 12

Матрица смежности основана на вершинах, смежных друг с другом (связанных или соседних). 2 Она описывает, являются ли две вершины смежными (1) или нет (0). 2 Каждый элемент в такой матрице — это булево число, описывающее связность. 2

Матрица инцидентности указывает связи между инцидентными элементами графа (ребро (дуга) и вершина). 1 В ней граф с множеством вершин V и множеством рёбер E преобразуется в матрицу размером V на E. 2 Строки и столбцы обозначаются как вершины и рёбра соответственно. 2 Единица означает связь между вершиной в строке и ребром в столбце. 2

Некоторые другие различия:

• Форма матрицы: матрица смежности всегда имеет форму квадрата, а матрица инцидентности — форму прямоугольника. 24
• Количество столбцов: в большинстве случаев рёбер всегда больше, чем вершин, поэтому матрицы смежности имеют меньше столбцов, чем матрицы инцидентности. 2
• Информативность: матрицы смежности более разрежены — от 0 до 1, и, вероятно, менее информативны на элемент матрицы. 2
• Значения элементов: в неориентированном графе, если вершина инцидентна ребру, то соответствующий элемент равен 1, в противном случае — 0. 1 В ориентированном графе, если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то элемент равен -1, если ребро отсутствует, то элемент равен 0. 1