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

Когда направление существенно

В ориентированном графе ребро имеет направление и называется дугой. Дуги $A\to B$ и $B\to A$ различаются. Так описывают односторонние дороги, зависимости заданий, состояния процесса и ветви последовательного эксперимента.

Исходящая степень $\deg^+(v)$ — число дуг, начинающихся в вершине; входящая $\deg^-(v)$ — число заканчивающихся в ней. Каждая дуга учитывается один раз в каждой общей сумме, поэтому обе суммы равны числу дуг.

Путь должен следовать стрелкам

Из $A$ достижима $B$, если существует направленный путь. Достижимость не обязана быть симметричной. Граф сильно связен, если любая вершина достижима из любой другой по направлениям. Слабая связность означает связность после удаления направлений; она не гарантирует возможность обратной поездки.

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

Три примера

1. При дугах $A\to B$ и $B\to C$ вершина $C$ достижима из $A$ за два шага, но обратного пути нет.
2. При дугах $A\to B,B\to C,C\to A$ граф сильно связен: из любой вершины можно обойти цикл.
3. Из состояния выходят дуги с вероятностями 0.2, 0.5 и $q$. Для корректной модели переходов $q=1-0.2-0.5=0.3$.

Ошибки

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