5. Ориентированные графы (рёбра со стрелками)

До сих пор мы рассматривали неориентированные графы: по ребру можно двигаться в обе стороны.

В реальности связи часто направлены:

  • одностороннее движение на улице;

  • подписка в Instagram (Аня подписана на Борю, но Боря — не обязательно на Аню);

  • передача информации (из А в В, но не обратно).

Определение:
Ориентированный граф (орграф) — граф, у которого каждое ребро имеет направление (изображается стрелкой).

Ребро в орграфе называют дугой.

Пример 6. Схема одностороннего движения:
Вершины — перекрёстки A, B, C.
Дуги: A→B, B→C, C→A (кольцевая односторонняя).
Из A можно попасть в C: A→B→C.
Из C в B — нельзя, так как C→A→B? Проверим: C→A есть, A→B есть → да, можно C→A→B. Значит, граф сильно связный (из любой вершины в любую есть путь).

Пример 7. Подписки в соцсети:
Вершины: Аня, Боря, Витя.
Дуги: Аня → Боря (Аня подписана на Борю),
Боря → Витя,
Витя → Аня.
Здесь тоже можно добраться по кругу, но не все связи взаимны.