Матрица инцидентности

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

В случае ориентированного графа каждой дуге <x,y> ставится в соответствующем столбце: «-1» в строке вершины x и «1» в строке вершины y; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0».

Пример

Граф	Матрица инцидентности
	<math>\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix}</math>

Особенности данного представления

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

См. также

• Матрица смежности

Литература

1. Харари Ф. Теория графов. — М.: Мир. — 1973. — 300 с.

Отрывок, характеризующий Матрица инцидентности

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