Слайд 5
В теории графов классическим способом представления графа служит матрица инцидентности.
Это
матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (x,y) содержит 1 в строке, соответствующей вершине х, -1 в строке, соответствующей вершине у, и нули во всех остальных строках. В случае неориентированного графа столбец, соответствующий ребру {х,у}, содержит 1 в строках, соответствующих х и у, и нули в остальных строках.
Этот способ один из самых худших способов представления графов с алгоритмической точки зрения. Он требует n*m ячеек памяти, причем большинство этих ячеек занято нулями. Неудобен также доступ к информации.
Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».