|
|
| (не показаны 4 промежуточные версии этого же участника) |
| Строка 1: |
Строка 1: |
| − | == Основные определения ==
| + | #REDIRECT [[Основные определения теории графов#Ориентированные графы]] |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | '''Ориентированный граф (directed graph) <tex> G </tex>''' - это пара <tex> G = (V, E) </tex>, где <tex>V</tex> - конечное множество вершин, а <tex>E \subset V \times V </tex> - множество рёбер. Ребро обозначается как пара вершин <tex>(v, u)</tex>, где <tex>v</tex> - начало ребра, а <tex>u</tex> - конец. Причём <tex>(v, u) \ne (u, v)</tex>.
| |
| − | }}
| |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>begin, end: E \to V</tex>.
| |
| − | }}
| |
| − | | |
| − | Для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
| |
| − | | |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | Ребро ориентированного графа называется '''дугой (arc)'''.
| |
| − | }}
| |
| − | | |
| − | == Представление ==
| |
| − | | |
| − | === Матрица и списки смежности ===
| |
| − | | |
| − | Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра или их количество (если в графе разрешены паралелльные ребра).
| |
| − | Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
| |
| − | | |
| − | Если граф разрежен, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
| |
| − | | |
| − | === Матрица инцидентности ===
| |
| − | | |
| − | Имеет место и другое представление графа - [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:
| |
| − | # <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>.
| |
| − | # В остальных случаях ячейки матрицы равны 0.
| |
| − | | |
| − | == Источник ==
| |
| − | * ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
| |
| − | | |
| − | == См. также ==
| |
| − | *[[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
| |
| − | | |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Основные определения теории графов]]
| |
