Матрица заболеваемости

Матрица, показывающая связь между двумя классами объектов.

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

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

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

Неориентированные и ориентированные графы

Неориентированный граф.

В теории графов неориентированный граф имеет два вида матриц инцидентности: неориентированную и ориентированную.

Неориентированная матрица инцидентности (или просто матрица инцидентности ) неориентированного графа — это матрица B , где n и m — количество вершин и ребер соответственно, такая, что ${\displaystyle n\times m}$

${\displaystyle B_{ij}=\left\{{\begin{array}{rl}\,1&{\text{if vertex }}v_{i}{\text{ is incident with edge }}e_{j},\\0&{\text{otherwise.}}\end{array}}\right.}$

Например, матрица инцидентности неориентированного графа, показанного справа, представляет собой матрицу, состоящую из 4 строк (соответствующих четырем вершинам, 1–4) и 4 столбцов (соответствующих четырем ребрам, ): ${\displaystyle e_{1},e_{2},e_{3},e_{4}}$

Если мы посмотрим на матрицу инцидентности, то увидим, что сумма каждого столбца равна 2. Это связано с тем, что каждое ребро имеет вершину, соединенную с каждым концом.

Матрица инцидентности ориентированного графа представляет собой матрицу B , где n и m — количество вершин и ребер соответственно, такая, что ${\displaystyle n\times m}$

${\displaystyle B_{ij}=\left\{{\begin{array}{rl}{-1}&{\text{if edge }}e_{j}{\text{ leaves vertex }}v_{i},\\{\phantom {-}}1&{\text{if edge }}e_{j}{\text{ enters vertex }}v_{i},\\{\phantom {-}}0&{\text{otherwise.}}\end{array}}\right.}$

(Многие авторы используют противоположное соглашение о знаках.)

Ориентированная матрица инцидентности неориентированного графа — это матрица инцидентности в смысле ориентированных графов любой ориентации графа. То есть в столбце ребра e есть одна единица в строке, соответствующей одной вершине e , и одна -1 в строке, соответствующей другой вершине e , а все остальные строки имеют 0. Ориентированная матрица инцидентности равна уникален вплоть до отрицания любого из столбцов, поскольку отрицание записей столбца соответствует изменению ориентации края.

Неориентированная матрица инцидентности графа G связана с матрицей смежности его линейного графа L ( G ) следующей теоремой:

${\displaystyle A(L(G))=B(G)^{\textsf {T}}B(G)-2I_{m}.}$

где A ( L ( G )) — матрица смежности линейного графа G , B ( G ) — матрица инцидентности, а I _m — единичная матрица размерности m .

Дискретный лапласиан (или матрица Кирхгофа) получается из ориентированной матрицы инцидентности B ( G ) по формуле

${\displaystyle B(G)B(G)^{\textsf {T}}.}$

Целочисленное пространство циклов графа равно нулевому пространству его ориентированной матрицы инцидентности, рассматриваемой как матрица целых , действительных или комплексных чисел . Пространство двоичного цикла — это нулевое пространство его ориентированной или неориентированной матрицы инцидентности, рассматриваемое как матрица над двухэлементным полем .

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

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

Мультиграфы

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

Взвешенные графики

Взвешенный неориентированный граф

Взвешенный граф можно представить, используя вес ребра вместо 1. Например, матрица инцидентности графа справа:

Гиперграфики

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

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

Матрица инцидентности структуры инцидентности C представляет собой матрицу B размера p × q (или ее транспонированную), где p и q — количество точек и линий соответственно, так что B _{i , j} = 1, если точка p _i и линия L _j являются инцидентными и 0 в противном случае. В этом случае матрица инцидентности также является матрицей двусмежности графа Леви структуры. Поскольку для каждого графа Леви существует гиперграф , и наоборот , матрица инцидентности структуры инцидентности описывает гиперграф.

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

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

Многогранники

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

Блочные конструкции

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

Смотрите также

• Инвариант Парри – Салливана

Рекомендации

1. Коксетер, HSM (1973) [1963], Правильные многогранники (3-е изд.), Дувр, стр. 166-167, ISBN 0-486-61480-8
2. Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса № 14, Математическая ассоциация Америки, стр. 99

дальнейшее чтение

• Дистель, Рейнхард (2005), Теория графов , Тексты для аспирантов по математике , том. 173 (3-е изд.), Springer-Verlag, ISBN 3-540-26183-4
• Джонатан Л. Гросс, Джей Йеллен, Теория графов и ее приложения , второе издание, 2006 г. (стр. 97, Матрицы инцидентности для неориентированных графов; стр. 98, матрицы инцидентности для орграфов)

Внешние ссылки

• Вайсштейн, Эрик В. «Матрица заболеваемости». Математический мир .