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

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

Основные понятияПравить

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

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

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

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

СвязностьПравить

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

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

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

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

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

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

Конденсацией орграфа $D$$D$  называют орграф $D^{\star <!--\; \star \; -->}$$D^{\star }$ , вершинами которого служат сильные компоненты $D$$D$ , а дуга в $D^{\star <!--\; \star \; -->}$$D^{\star }$  показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.

Дополнительные определенияПравить

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

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

Изображение и свойства всех орграфов с тремя узламиПравить

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

0 дуг	1 дуга	2 дуги	3 дуги	4 дуги	5 дуг	6 дуг
пустой, Н, Г	Н, Г		ОС	CC	CC	полный, CC
		ОС, Н, Г	CC, Н, Т	CC
		C, Н, Г	ОС, Н, Г, Т	ОС
		C, Н, Г	ОС	ОС

Применение орграфовПравить

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

Бинарные отношенияПравить

 

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

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

ПрочееПравить

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

ЛитератураПравить

• Харари Ф. Теория графов. — М.: УРСС, 2003. — 300 с. — ISBN 5-354-00301-6.
• Оре, Ойстин. Теория графов. — М.: УРСС, 2008. — 352 с. — ISBN 978-5-397-00044-4.
• Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструменты, 2 издание = Compilers: Principles, Techniques, and Tools. — 2 изд. — М.: «Вильямс», 2008. — ISBN 978-5-8459-1349-4.