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