Открыть главное меню

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

Directed.svg

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПримечанияПравить

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