Ориентированный граф — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Матрица и списки смежности)
Строка 38: Строка 38:
  
 
== См. также ==
 
== См. также ==
*[[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
+
*[[Основные определения теории графов]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Версия 04:12, 17 января 2012

Основные определения

Определение:
Ориентированный граф (directed graph) [math] G [/math] - это пара [math] G = (V, E) [/math], где [math]V[/math] - конечное множество вершин, а [math]E \subset V \times V [/math] - множество рёбер. Ребро обозначается как пара вершин [math](v, u)[/math], где [math]v[/math] - начало ребра, а [math]u[/math] - конец. Причём [math](v, u) \ne (u, v)[/math].


Определение:
Также ориентированным графом [math] G [/math] - называется четверка [math] G = (V, E, begin, end) [/math], где [math]begin, end: E \to V[/math].


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


Определение:
Ребро ориентированного графа называется дугой (arc).


Представление

Матрица и списки смежности

Ориентированный граф можно представить в виде матрицы смежности, где [math]graph[v][u] = true \Leftrightarrow (v, u) \in E[/math]. Также в ячейке матрицы может хранится вес ребра или их количество (если в графе разрешены паралелльные ребра). Для матрицы смежности существует теорема, позволяющая связать степень матрицы и количество путей из вершины [math]v[/math] в вершину [math]u[/math].

Если граф разрежен ([math]|E| \lt |V^2|[/math]), его лучше представить в виде списков смежности, где список для вершины [math]v[/math] будет содержать вершины [math]u: (v, u) \in E[/math]. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.

Матрица инцидентности

Имеет место и другое представление графа - матрица инцидентности, которая сопоставляет множество вершин множеству ребер. То есть:

  1. [math]graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)[/math].
  2. В остальных случаях ячейки матрицы равны 0.

Источник

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

См. также