419
правок
Изменения
Нет описания правки
{{Определение
|definition =
Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>begbegin, end: E \to V</tex>.
}}
=== Матрица и списки смежности ===
Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра либо или их количество, (если в нашем графе разрешены паралелльные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
Если граф разрежен, его лучше представить в виде списков смежности, что где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
=== Матрица инцидентности ===
