В математике , матрица случаев является логической матрицей , которая показывает взаимосвязь между двумя классами объектов, как правило , называют отношением инцидентности . Если первый класс X , а второй Y , то матрица имеет одну строку для каждого элемента X и один столбец для каждого элемента Y . Запись в строке x и столбце y равна 1, если x и y связаны ( в данном контексте это называется инцидент ), и 0, если они не связаны. Есть вариации; Смотри ниже.
Теория графов [ править ]
Матрицы инцидентности часто используются в теории графов .
Ненаправленные и ориентированные графы [ править ]
В теории графов неориентированный граф имеет два вида матриц инцидентности: неориентированные и ориентированные.
Неориентированная матрица частоты (или просто частота матрицы ) неориентированный граф с п × м матрица B , где п и т является числом вершин и ребер соответственно, таким образом, что Б я , J = 1 , если вершина V я и край e j инцидентны и 0 в противном случае.
Например, матрица инцидентности неориентированного графа, показанная справа, представляет собой матрицу, состоящую из 4 строк (соответствующих четырем вершинам, 1–4) и 4 столбцов (соответствующих четырем ребрам, e1 – e4):
| знак равно |
Если мы посмотрим на матрицу инцидентности, мы увидим, что сумма каждого столбца равна 2. Это потому, что каждое ребро имеет вершину, соединенную с каждым концом.
Матрица инцидентности из ориентированного графа является п × м матрицы B , где п и т являются число вершин и ребер , соответственно, таким образом, что B я , J = -1 , если ребро е J листья вершины V я , 1 , если оно входит вершина v i и 0 в противном случае (многие авторы используют противоположное соглашение о знаках).
Ориентированная матрица инцидентности неориентированного графа является матрицей заболеваемости, в том смысле , ориентированные графов, любой ориентации графа. То есть в столбце ребра e одна единица в строке соответствует одной вершине e и одна -1 в строке, соответствующей другой вершине e , а все остальные строки имеют 0. Ориентированная матрица инцидентности имеет вид уникален до отрицания любого из столбцов, поскольку отрицание записей столбца соответствует изменению ориентации края.
Неориентированная матрица инцидентности графа G связана с матрицей смежности его линейного графа L ( G ) следующей теоремой:
где A ( L ( G )) - матрица смежности линейного графа G , B ( G ) - матрица инцидентности, а I m - единичная матрица размерности m .
Дискретный лапласиан (или матрица Кирхгофа) получается из ориентированной матрицы инцидентности B ( G ) по формуле
Интеграл цикла пространство графа равна нуль - пространство его ориентированной матрицы инцидентности, рассматривается в качестве матрицы над целыми числами или действительных или комплексных чисел . Пространство двоичного цикла - это пустое пространство его ориентированной или неориентированной матрицы инцидентности, рассматриваемой как матрица над двухэлементным полем .
Подписанные и двунаправленные графики [ править ]
Матрица инцидентности графа со знаком является обобщением ориентированной матрицы инцидентности. Это матрица инцидентности любого двунаправленного графа, которая ориентирует данный граф со знаком. Столбец положительного ребра имеет 1 в строке, соответствующей одной конечной точке, и -1 в строке, соответствующей другой конечной точке, точно так же, как ребро в обычном (беззнаковом) графе. Столбец отрицательного ребра имеет либо 1, либо -1 в обеих строках. Свойства линейного графа и матрицы Кирхгофа обобщаются на графы со знаком.
Мультиграфы [ править ]
Определения матрицы инцидентности применимы к графам с петлями и кратными ребрами . Столбец ориентированной матрицы инцидентности, который соответствует циклу, равен нулю, если только граф не подписан, а цикл отрицательный; тогда весь столбец равен нулю, за исключением ± 2 в строке его инцидентной вершины.
Гиперграфы [ править ]
Поскольку ребра обычных графов могут иметь только две вершины (по одной на каждом конце), столбец матрицы инцидентности для графов может иметь только два ненулевых элемента. Напротив, гиперграф может иметь несколько вершин, назначенных одному ребру; таким образом, общая матрица неотрицательных целых чисел описывает гиперграф.
Структуры заболеваемости [ править ]
Матрица инцидентности из структуры заболеваемости С является р × д матрица В (или его транспонированном), где р и д является количеством точек и линий , соответственно, таким образом, что Б я , J = 1 , если точка р я и линия L j инцидентны и 0 в противном случае. В этом случае матрица заболеваемости также biadjacency матрица из Леви графа структуры. Поскольку есть гиперграфдля любого графа Леви, и наоборот , матрица инцидентности структуры инцидентности описывает гиперграф.
Конечная геометрия [ править ]
Важный пример - конечная геометрия . Например, на конечной плоскости X - это множество точек, а Y - это множество прямых. В конечной геометрии более высокого измерения X может быть набором точек, а Y может быть набором подпространств размерности на единицу меньше, чем размерность всего пространства (гиперплоскости); или, в более общем смысле, X может быть набором всех подпространств одного измерения d, а Y - набором всех подпространств другого измерения e , с инцидентностью, определяемой как включение.
Многогранники [ править ]
Аналогичным образом отношения между ячейками, размеры которых в многограннике отличаются на единицу, могут быть представлены матрицей инцидентности. [1]
Блочные конструкции [ править ]
Другой пример - блочная конструкция . Здесь X - конечный набор «точек», а Y - класс подмножеств X , называемых «блоками», в соответствии с правилами, зависящими от типа конструкции. Матрица инцидентности - важный инструмент в теории блочных схем. Например, его можно использовать для доказательства неравенства Фишера , фундаментальной теоремы о сбалансированных неполных 2-схемах (BIBD), о том, что количество блоков не меньше количества точек. [2] Рассматривая блоки как систему множеств, перманент матрицы инцидентности - это количество систем различных представителей (SDR).
Ссылки [ править ]
- ↑ Coxeter, HSM (1973) [1963], Regular Polytopes (3-е изд.), Dover, стр. 166-167 , ISBN 0-486-61480-8
- ^ Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса № 14, Математическая ассоциация Америки, стр. 99
Дальнейшее чтение [ править ]
- Дистель, Рейнхард (2005), Теория графов , Тексты для выпускников по математике , 173 (3-е изд.), Springer-Verlag, ISBN 3-540-26183-4
- Джонатан Л. Гросс, Джей Йеллен, Теория графов и ее приложения , второе издание, 2006 г. (стр. 97, Матрицы инцидентности для неориентированных графов; стр. 98, матрицы инцидентности для орграфов)
Внешние ссылки [ править ]
 | Викискладе есть медиафайлы, связанные с матрицами инцидентности графов . |
 | Найдите матрицу заболеваемости в Викисловаре, бесплатном словаре. |
- Вайсштейн, Эрик У. «Матрица заболеваемости» . MathWorld .
