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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Ориентированный граф (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].

См. также