Слайд 5
![В теории графов классическим способом представления графа служит матрица инцидентности. Это](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1370637/slide-4.jpg)
В теории графов классическим способом представления графа служит матрица инцидентности.
Это
матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (x,y) содержит 1 в строке, соответствующей вершине х, -1 в строке, соответствующей вершине у, и нули во всех остальных строках. В случае неориентированного графа столбец, соответствующий ребру {х,у}, содержит 1 в строках, соответствующих х и у, и нули в остальных строках.
Этот способ один из самых худших способов представления графов с алгоритмической точки зрения. Он требует n*m ячеек памяти, причем большинство этих ячеек занято нулями. Неудобен также доступ к информации.
Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».