|
[[Файл:Directed.svg|thumb|right]]
'''<big><big>== ЗУРГ ЖЖОТ! ==</big></big>'''
'''Ориентированный граф''' (кратко '''орграф''') — (мульти) [[Граф (математика)|граф]], рёбрам которого присвоено направление. Направленные рёбра именуются также ''дугами'', а в некоторых источниках (Оре) и просто рёбрами.
== Основные понятия ==
Формально, орграф D=(V, E) есть [[множество]] E упорядоченных пар вершин <math>v\in V</math>.
Дуга {u, v} '''инцидентна''' вершинам u и v. При этом говорят, что u — '''начальная вершина''' дуги, а v — '''конечная вершина'''.
Орграф, полученный из [[Словарь терминов теории графов#П|простого графа]] ориентацией ребер называется '''направленным'''. В отличие от последнего, в произвольном '''простом орграфе''' две вершины могут соединяться двумя разнонаправленными дугами.
Направленный [[полный граф]] называется '''турниром'''.
=== Связность ===
'''Маршрутом''' в орграфе называют чередующуюся последовательность вершин и ''дуг'', вида <math>v_0 \{v_0, v_1\} v_1 \{v_1, v_2\} v_2 ... v_n</math> (вершины могут повторяться). '''Длина маршрута''' — количество дуг в нем.
'''Путь''' есть ''маршрут'' в орграфе без повторяющихся дуг, '''простой путь''' — без повторяющихся вершин. Если существует путь из одной вершины в другую, то вторая вершина '''достижима''' из первой.
'''Контур''' есть замкнутый ''путь''.
Для '''полумаршрута''' снимается ограничение на направление дуг, аналогично определяются '''полупуть''' и '''полуконтур'''.
| 