119
правок
Изменения
→Матрица и списки смежности
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
Если граф разрежен (sparse graph, <tex>|E| = O(<< |V^k2|), k < 2</tex>, то есть, неформально говоря, в нем не очень много ребер), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
=== Матрица инцидентности ===
