Вероятность и статистика · Графы и деревья

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

Стрелки, входящие и исходящие степени, достижимость и вероятностные переходы.

6 минут на чтениеЗаданий для самопроверки: 3

Чему научимся

Ориентированные графы описывают односторонние дороги, зависимости задач и переходы между состояниями. Входящие и исходящие степени помогают проверять структуру и вероятностные ветви.

Главная идея. В ориентированном графе каждое ребро имеет направление и называется дугой, поэтому A → B и B → A — разные связи. Путь обязан следовать стрелкам, а достижимость обычно несимметрична.

План рассуждения и проверка понимания

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

Частая ошибка. Игнорировать стрелки и считать, что из C можно вернуться в A только потому, что в неориентированном виде вершины A, B и C соединены.

Как проверить себя. Стройте последовательность дуг в требуемом направлении; из A → B и B → C следует достижимость C из A, но обратного пути эти дуги не дают.

Схема к теме

Наглядная модель: Ориентированные графы

Стрелки, входящие и исходящие степени, достижимость и вероятностные переходы.

Ориентированные графы → ориентированный граф
Ориентированные графы → дуга
Ориентированные графы → достижимость

Схема связывает понятие «Ориентированные графы» с его ключевыми признаками. Вывод: Свяжите определение, условия и обозначения: тогда формула станет краткой записью уже понятной идеи.

Проверка пониманияОбъясните тему своими словами

Для цикла A → B, B → C, C → A объясните сильную связность и проверьте общие суммы входящих и исходящих степеней.

В хорошем объяснении есть:

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

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

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

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

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

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

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

Три примера

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

Ошибки

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

Формула, смысл и ограничения

Главные формулы с расшифровкой

\sum_v\deg^+(v)=\sum_v\deg^-(v)=|E|

Формула словами: Каждая дуга имеет одно начало и один конец; петля добавляет по единице в обе степени.

От простого к сложному

Проверьте себя

Сначала запишите решение самостоятельно. Затем можно открыть намёк, сравнить каждый переход с пошаговым разбором и только после этого посмотреть ответ. Прогресс сохраняется в этом браузере.

Открываем задание…

Источники и соглашения

Объяснения и задачи — авторские. Источники помогают проверить определения, условия и школьную привязку. Обозначения и параметризация указаны в статье.