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

Ориенти́рованный граф, граф, каждому ребру которого приписана ориентация. Ориентированный граф ${\displaystyle G}$ задаётся множеством вершин ${\displaystyle V}$ и набором ${\displaystyle E}$ упорядоченных пар вершин, называемых дугами. Говорят, что дуга ${\displaystyle (u,v)}$ исходит из вершины ${\displaystyle u}$ и входит в вершину ${\displaystyle v}$. Число дуг, исходящих из ${\displaystyle v}$, называется полустепенью исхода вершины ${\displaystyle v}$, а число дуг, входящих в ${\displaystyle v}$, называется полустепенью захода вершины ${\displaystyle v}$. Чередующаяся последовательность вершин и дуг ${\displaystyle v_{0},e_{1},v_{1},e_{2},\ldots ,e_{n},v_{n}}$, в которой ${\displaystyle e_{i}=(v_{i-1},v_{i})}$, ${\displaystyle i=1,2,\ldots ,n}$, называется маршрутом (ориентированным). Маршрут называется замкнутым, если его первая и последняя вершины совпадают. Путь – это маршрут, в котором все вершины различны. Контур – это нетривиальный (содержащий хотя бы одну дугу) замкнутый маршрут, у которого все вершины различны, кроме первой и последней. Если существует путь из вершины ${\displaystyle u}$ в вершину ${\displaystyle v}$, то говорят, что ${\displaystyle v}$ достижима из ${\displaystyle u}$.

Ориентированный граф ${\displaystyle G}$ с нумерованными вершинами ${\displaystyle v_{1},\ldots ,v_{n}}$ и дугами ${\displaystyle e_{1},\ldots ,e_{m}}$ можно задать матрицей инцидентности, т. е. матрицей${\displaystyle \left\Vert b_{ij}\right\Vert }$ размера ${\displaystyle n\times m}$, в которой

${\displaystyle b_{ij}={\begin{cases}+1,&{\text{если дуга }}e_{j}{\text{ исходит из }}v_{i},\\-1,&{\text{если дуга }}e_{j}{\text{ заходит в }}v_{i},\\0,&{\text{если дуга }}e_{j}{\text{ не инцидентна }}v_{i}.\end{cases}}}$

Матрицей смежности ${\displaystyle A(G)}$ вершин ориентированного графа ${\displaystyle G}$ называется матрица ${\displaystyle \left\Vert a_{ij}\right\Vert }$ размера ${\displaystyle n\times n}$, в которой элемент ${\displaystyle a_{ij}}$ равен числу дуг, идущих из ${\displaystyle v_{i}}$ в ${\displaystyle v_{j}}$. Суммы элементов по строкам матрицы ${\displaystyle A(G)}$ равны полустепеням исхода вершин ориентированного графа ${\displaystyle G}$, а суммы элементов по столбцам – полустепеням захода. Элемент ${\displaystyle (i,j)}$ матрицы ${\displaystyle A^{k}(G)}$ (т. е. ${\displaystyle k}$-й степени матрицы смежности графа ${\displaystyle G}$) равен числу маршрутов длины ${\displaystyle k}$, идущих из ${\displaystyle v_{i}}$ в ${\displaystyle v_{j}}$

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

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