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

Если элементы множества %%E%% графа %%G = (V, E)%% — упорядоченные пары, то граф называется ориентированным или орграфом. Можно сказать, что орграф — это граф, ребрам которого присвоено направление.

Ребро %%e%% графа %%G%% называют ориентированным, если одну вершину считают началом ребра, а другую — концом, на рисунке его изображают стрелкой между вершинами. Таким образом, граф, все ребра которого ориентированы, является ориентированным графом.

Одна и та же вершина орграфа может служить началом для одних ребер и концом для других, поэтому различают две степени вершины: степень выхода и степень входа.

Степенью выхода вершины орграфа называется число выходящих из вершины ребер.

Степенью входа вершины орграфа называется число входящих в вершину ребер.

В орграфах в зависимости от сочетания степеней входа и выхода для данной вершины рассматриваются три случая:

• вершина называется изолированной, если ее степени выхода и входа равны 0;
• вершина называется источником, если ее степень входа равна 0, а степень выхода больше 0;
• вершина называется стоком, если ее степень выхода равна 0, а степень входа больше 0.

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

Длиной пути называется число ребер в этом пути.

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

Петлей называется ребро, у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной.