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

---

Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.

Формально, орграф ${\displaystyle D=(V,E)}$ состоит из множества ${\displaystyle V}$, элементы которого называются вершинами, и множества ${\displaystyle E}$ упорядоченных пар вершин ${\displaystyle u,v\in V}$, элементы которого называются дугами.

Дуга ${\displaystyle (u,v)}$ инцидентна вершинам ${\displaystyle u}$ и ${\displaystyle v}$. При этом говорят, что ${\displaystyle u}$ — начальная вершина дуги, а ${\displaystyle v}$ — конечная вершина.

Орграф, полученный из простого графа ориентацией рёбер, называется направленным. В отличие от последнего, в произвольном простом орграфе две вершины могут соединяться двумя разнонаправленными дугами.

Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида ${\displaystyle v_{0}\{v_{0},v_{1}\}v_{1}\{v_{1},v_{2}\}v_{2}...v_{n}}$ (вершины могут повторяться). Длина маршрута — количество дуг в нём.

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

---