2015-07-14
266
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа. В ячейку матрицы на пересечении строки 
со столбцом 
записывается:
в случае, если связь «выходит» из вершины ,
−1,
если связь «входит» в вершину,
во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)
Данный способ является самым ёмким (размер пропорционален 
) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).
· Используется для любых графов, даже если есть петля.
· В каждом столбце обязательно должны стоять две единицы (либо 1 и -1 в случае ориентированного графа).
