Русская Википедия:Матрица инцидентности

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Пример

Граф	Матрица инцидентности
Файл:6n-graph3.svg	<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 до 6, а столбцы — рёбрам e1–e7. Например, единицы во втором столбце во 2-й и 3-й строчках означают, что ребро e2 соединяет вершины 2 и 3.

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

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

См. также

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

Литература

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