В чём заключается отличие матрицы смежности от матрицы инцидентности?

Основное отличие матрицы смежности от матрицы инцидентности заключается в том, что они описывают разные аспекты связей в графе. ru.hexlet.io

Матрица смежности основана на вершинах, смежных друг с другом (связанных или соседних). ru.hexlet.io Она описывает, являются ли две вершины смежными (1) или нет (0). ru.hexlet.io Матрица смежности всегда имеет форму квадрата, а её элементы более разрежены: обычно от 0 до 1. ru.hexlet.io

Матрица инцидентности указывает связи между инцидентными элементами графа (ребро (дуга) и вершина). prog-cpp.ru В ней единица означает связь между вершиной в строке и ребром в столбце. ru.hexlet.io Матрица инцидентности имеет форму прямоугольника, а при сложении всех элементов в столбце всегда получается два. ru.hexlet.io Это закономерно, потому что любое ребро в простом графе имеет только две вершины, соединённые с ним. ru.hexlet.io

Кроме того, в большинстве случаев рёбер всегда больше, чем вершин, поэтому матрицы смежности имеют меньше столбцов, чем матрицы инцидентности. ru.hexlet.io