Ориентированный граф

Определение:

Ориентированный граф (directed graph) [math] G [/math] - это пара [math] G = (V, E) [/math], где [math]V[/math] - конечное множество вершин, а [math]E \subset V \times V [/math] - множество рёбер.

Определение:

Также ориентированным графом [math] G [/math] - называется четверка [math] G = (V, E, begin, end) [/math], где [math]beg, end: E /to V[/math].

Для ориентированного графа справедлива лемма о рукопожатиях, связывающая количество ребер с суммой степеней вершин.

Определение:

Ребро ориентированного графа называется дугой (arc).

Ориентированный граф

Ребро обозначается как пара вершин [math](v, u)[/math], где [math]v[/math] - начало ребра, а [math]u[/math] - конец. Причём [math](v, u) \ne (u, v)[/math].

См. также

• Основные определения: граф, ребро, вершина, степень, петля, путь, цикл