Русская Википедия:Ориентированный граф
Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Основные понятия
Формально, орграф <math>D = (V, E)</math> состоит из множества <math>V</math>, элементы которого называются вершинами, и множества <math>E</math> упорядоченных пар вершин <math>u,v\in V</math>, элементы которого называются дугами.
Дуга <math>(u, v)</math> инцидентна вершинам <math>u</math> и <math>v</math>. При этом говорят, что <math>u</math> — начальная вершина дуги, а <math>v</math> — конечная вершина.
Орграф, полученный из простого графа ориентацией рёбер, называется направленным. В отличие от последнего, в произвольном простом орграфе две вершины могут соединяться двумя разнонаправленными дугами.
Направленный полный граф называется турниром.
Связность
Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида <math>v_0 \{v_0, v_1\} v_1 \{v_1, v_2\} v_2 ... v_n</math> (вершины могут повторяться). Длина маршрута — количество дуг в нём.
Путь есть маршрут в орграфе без повторяющихся дуг, простой путь — без повторяющихся вершин. Если существует путь из одной вершины в другую, то вторая вершина достижима из первой.
Контур есть замкнутый путь.
Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур.
Орграф сильно связный, или просто сильный, если все его вершины взаимно достижимы; односторонне связный, или просто односторонний, если для любых двух вершин, по крайней мере, одна достижима из другой; слабо связный, или просто слабый, если при игнорировании направления дуг получается связный (мульти)граф;
Максимальный сильный подграф называется сильной компонентой; односторонняя компонента и слабая компонента определяются аналогично.
Конденсацией орграфа <math>D</math> называют орграф <math>D^\star</math>, вершинами которого служат сильные компоненты <math>D</math>, а дуга в <math>D^\star</math> показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.
Дополнительные определения
Направленный ациклический граф или комок есть бесконтурный орграф.
Ориентированный граф, полученный из заданного сменой направления рёбер на противоположное, называется обратным.
Изображение и свойства всех орграфов с тремя узлами
Легенда: С — слабый, ОС — односторонний, СС — сильный, Н — является направленным графом, Г — является гамаком (ациклический), Т — является турниром
| 0 дуг | 1 дуга | 2 дуги | 3 дуги | 4 дуги | 5 дуг | 6 дуг |
| Файл:3node digraph0.svgШаблон:-пустой, Н, Г | Файл:3node digraph1.svgШаблон:-Н, Г | Файл:3node digraph21.svgШаблон:- | Файл:3node digraph31.svgШаблон:-ОС | Файл:3node digraph41.svgШаблон:-CC | Файл:3node digraph5.svgШаблон:-CC | Файл:3node digraph6.svgШаблон:-полный, CC |
|---|---|---|---|---|---|---|
| Файл:3node digraph22.svgШаблон:-ОС, Н, Г | Файл:3node digraph32.svgШаблон:-CC, Н, Т | Файл:3node digraph42.svgШаблон:-CC | ||||
| Файл:3node digraph23.svgШаблон:-C, Н, Г | Файл:3node digraph33.svgШаблон:-ОС, Н, Г, Т | Файл:3node digraph43.svgШаблон:-ОС | ||||
| Файл:3node digraph24.svgШаблон:-C, Н, Г | Файл:3node digraph34.svgШаблон:-ОС | Файл:3node digraph44.svgШаблон:-ОС |
Применение орграфов
Орграфы широко применяются в программировании как способ описания систем со сложными связями. К примеру, одна из основных структур, используемых при разработке компиляторов и вообще для представления компьютерных программ — граф потоков данных.
Бинарные отношения
Бинарное отношение над конечным носителем может быть представлено в виде орграфа. Простым орграфом представимы антирефлексивные отношения, в общем случае требуется орграф с петлями. Если отношение симметрично, то его можно представить неориентированным графом, а если антисимметрично, то направленным графом.
Прочее
Алгоритм Суурбалле — алгоритм нахождения двух непересекающихся (не имеющих общих рёбер) путей в ориентированном графе с неотрицательными весами, так что оба пути связывают ту же самую пару вершин и имеют минимальную общую длину.
Литература
