== Основные определения == [[Файл:Directed-graph.png|thumb|right|Ориентированный граф]] {{Определение|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>.}} {{Определение|definition =Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>beg, end: E \to V</tex>.}} Для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой #REDIRECT [[Основные определения теории графов#Степень вершины|степеней вершин]]. {{Определение|definition =Ребро ориентированного графа называется '''дугой (arc)'''.}} == Представление == === Матрица и списки смежности === Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра либо их количество, если в нашем графе разрешены паралелльные ребра.Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>. Если граф разрежен, его лучше представить в виде списков смежности, что позволит сэкономить память. === Матрица инцидентности === Имеет место и другое представление графа - [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:# <tex>graph[v][numberOfArc] = 1 \wedge graph[u][numberOfArc] = -1 \Leftrightarrow (v, u) \in E</tex># <tex>graph[v][numberOfArc] = 0 \wedge graph[u][numberOfArc] = 0 \Leftrightarrow (v, u) \notin E</tex>. == См. также ==*[[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]] [[Категория: Алгоритмы и структуры данных]][[Категория: Основные определения теории графовОриентированные графы]]
