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

Основная статья: Граф (математика)

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

Пример

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

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

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

См. также

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