Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро (дуга) и вершина). 13

Столбцы матрицы соответствуют рёбрам, строки — вершинам. 1 Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность). 1 Если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0». 1

Матрица инцидентности используется для любых графов, даже если есть петля. 1 Также она может применяться для представления гиперграфов (в этом случае столбец может содержать больше двух единиц). 1

Ещё матрица инцидентности используется в теории блочных конструкций, например, для доказательства неравенства Фишера. 5