Ориентированный граф
Слито со статьей Основные определения теории графов
Основные определения
| Определение: |
| Ориентированный граф (directed graph) - это пара , где - конечное множество вершин, а - множество рёбер. Ребро обозначается как пара вершин , где - начало ребра, а - конец. Причём . |
| Определение: |
| Также ориентированным графом - называется четверка , где . |
Для ориентированного графа справедлива лемма о рукопожатиях, связывающая количество ребер с суммой степеней вершин.
| Определение: |
| Ребро ориентированного графа называется дугой (arc). |
Представление
Матрица и списки смежности
Ориентированный граф можно представить в виде матрицы смежности, где . Также в ячейке матрицы может хранится вес ребра или их количество (если в графе разрешены паралелльные ребра). Для матрицы смежности существует теорема, позволяющая связать степень матрицы и количество путей из вершины в вершину .
Если граф разрежен (), его лучше представить в виде списков смежности, где список для вершины будет содержать вершины . Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
Матрица инцидентности
Имеет место и другое представление графа - матрица инцидентности, которая сопоставляет множество вершин множеству ребер. То есть:
- .
- В остальных случаях ячейки матрицы равны 0.
Источник
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
