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

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

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

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

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

Граф Матрица инцидентности[1]
Graph123.png

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

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

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

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

  1. Строки соответствуют вершинам (от 1 до 6), столбцы — рёбрам (1-2, 2-3, 3-4, 4-5, 1-5, 2-5, 4-6)

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

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