Введение

Матрица, показывающая связь между двумя классами объектов. В математике матрица инциденций — это логическая матрица, которая отображает взаимосвязь между двумя классами объектов, обычно называемую отношением инцидентности. Если первый класс — X, а второй — Y, то матрица имеет одну строку для каждого элемента X и один столбец для каждого элемента Y. Элемент в строке x и столбце y равен 1, если x и y связаны (в этом контексте называются инцидентными), и 0, если они не связаны. Существуют различные варианты; см. ниже.

Теория графов

Матрица инцидентности — распространённое представление графа в теории графов. Она отличается от матрицы смежности, которая кодирует связи между парами вершин.

Подписанные и двунаправленные графики

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

Мультиграфы

Определения матрицы инцидентности применимы к графам с петлями и кратным ребрам. Столбец ориентированной матрицы инцидентности, соответствующий петле, состоит из нулей, если только граф не является знаковым и петля не отрицательная; в этом случае столбец состоит из нулей, за исключением ±2 в строке, соответствующей вершине, в которой эта петля инцидентна.

Гиперграфы

Поскольку ребра обычных графов могут соединять только две вершины (по одной на каждом конце), столбец матрицы инцидентности для графов может содержать только две ненулевые ячейки. В отличие от этого, гиперграф может иметь несколько вершин, связанных с одним ребром; таким образом, гиперграф описывается общей матрицей неотрицательных целых чисел.

Структуры заболеваемости

Матрица инцидентности инцидентной структуры C — это матрица B (или её транспонированная матрица) размера p × q, где p и q — количество точек и прямых соответственно, такая что Bi,j = 1, если точка pi и прямая Lj инцидентны, и 0 в противном случае. В этом случае матрица инцидентности также является матрицей биадъяцентности графа Леви данной структуры. Поскольку для каждого графа Леви существует гиперграф, и наоборот, матрица инцидентности инцидентной структуры описывает гиперграф.

Конечные геометрии

Важным примером является конечная геометрия. Например, в конечной плоскости X – это множество точек, а Y – множество прямых. В конечной геометрии более высокой размерности X может быть множеством точек, а Y может быть множеством подпространств размерности на единицу меньше размерности всего пространства (гиперплоскостей); или, в более общем случае, X может быть множеством всех подпространств размерности d, а Y – множеством всех подпространств размерности e, при этом инцидентность определяется включением.

Политопы

Аналогичным образом, отношение между ячейками, размеры которых отличаются на единицу в политопе, может быть представлено матрицей инцидентности.

Конструкция блоков

Другой пример — блочный дизайн. Здесь X — конечное множество "точек", а Y — класс подмножеств X, называемых "блоками", подчиняющихся правилам, зависящим от типа дизайна. Матрица инцидентности является важным инструментом в теории блочных дизайнов. Например, её можно использовать для доказательства неравенства Фишера, фундаментальной теоремы сбалансированных неполных 2-дизайнов (BIBD), утверждающей, что число блоков не меньше числа точек. Рассматривая блоки как систему множеств, перманент матрицы инцидентности равен числу систем различных представителей (SDR).