Ориентированный граф — это граф, у которого имеется множество вершин (узлов) и множество рёбер (дуг), где каждая дуга имеет направление.
Особенности:
- Направленные рёбра: Движение по ребру возможно только в одном направлении, указанном стрелкой.
- Степень вершины: Для ориентированного графа определяют входящую степень (число рёбер, оканчивающихся в вершине) и исходящую степень (число рёбер, начинающихся в вершине).
- Пути и циклы: Путь — это последовательность вершин, соединённых рёбрами в правильном направлении. Цикл — это путь, начинающийся и заканчивающийся в одной и той же вершине. Ориентированные графы могут содержать ориентированные циклы.
- Связность: Различают слабую связность (игнорируя направления рёбер, граф связан как неориентированный) и сильную связность (для любых двух вершин A и B существует ориентированный путь из A в B и из B в A).
- Представление: Могут быть представлены списком смежности или матрицей смежности, где для ориентированного графа матрица, в общем случае, не симметрична.
Пример представления с помощью списка смежности:
python
Пример представления с помощью матрицы смежности:
python