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

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

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

Матрицы заболеваемости часто используются в теория графов.

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

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

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

В неориентированная матрица инцидентности (или просто матрица инцидентности) неориентированного графа является п × м матрица B, куда п и м количество вершины и края соответственно такие, что Bя,j = 1 если вершина vя и край еj инцидентны и 0 в противном случае.

Например, матрица инцидентности неориентированного графа, показанного справа, представляет собой матрицу, состоящую из 4 строк (соответствующих четырем вершинам, 1–4) и 4 столбцов (соответствующих четырем ребрам, e1 – e4):

е1е2е3е4
11110
21000
30101
40011
=

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

В матрица инцидентности из ориентированный граф это п × м матрица B куда п и м - количество вершин и ребер соответственно, таких что Bя,j = −1 если край еj оставляет вершину vя, 1, если он входит в вершину vя и 0 в противном случае (многие авторы используют соглашение о противоположных знаках).

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

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

куда А(L(грамм)) - матрица смежности линейного графа грамм, B(грамм) - матрица инцидентности, а ям это единичная матрица измерения м.

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

Интегральный велосипедное пространство графа равна пустое пространство ориентированной матрицы инцидентности, рассматриваемой как матрица над целые числа или же настоящий или же сложные числа. Пространство двоичного цикла - это пустое пространство его ориентированной или неориентированной матрицы инцидентности, рассматриваемой как матрица над двухэлементной поле.

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

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

Мультиграфы

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

Гиперграфы

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

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

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

Конечная геометрия

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

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

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

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

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

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

  1. ^ Кокстер, H.S.M. (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, матрицы инцидентности для орграфов)

внешняя ссылка