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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Пример[править | править вики-текст]

Граф Матрица инцидентности
Graph123.png \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}

Особенности данного представления[править | править вики-текст]

  • Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом.
  • В каждом столбце должны стоять две единицы (либо 1 и -1 в случае ориентированного графа), а все остальные символы — нули.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

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