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