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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Directed.svg

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

Основные понятия[править | править исходный текст]

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

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

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

Направленный полный граф называется турниром.

Связность[править | править исходный текст]

Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида v_0 \{v_0, v_1\} v_1 \{v_1, v_2\} v_2 ... v_n (вершины могут повторяться). Длина маршрута — количество дуг в нем.

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

Контур есть замкнутый путь.

Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур.

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

Максимальный сильный подграф называется сильной компонентой; односторонняя компонента и слабая компонента определяются аналогично.

Конденсацией орграфа D называют орграф D*, вершинами которого служат сильные компоненты D, а дуга в D* показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.

Дополнительные определения[править | править исходный текст]

Направленный ациклический граф или гамак есть бесконтурный орграф.

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

Изображение и свойства всех орграфов с тремя узлами[править | править исходный текст]

Легенда: С — слабый, ОС — односторонний, СС — сильный, Н — является направленным графом, Г — является гамаком (ациклический), Т — является турниром

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
ОС

Применение орграфов[править | править исходный текст]

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

Бинарные отношения[править | править исходный текст]

орграф отношения делимости

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

Примечания[править | править исходный текст]

Литература[править | править исходный текст]