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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Основные определения)
Строка 8: Строка 8:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>beg, end: E \to V</tex>.
+
Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>begin, end: E \to V</tex>.
 
}}
 
}}
  
Строка 23: Строка 23:
 
=== Матрица и списки смежности ===
 
=== Матрица и списки смежности ===
  
Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра либо их количество, если в нашем графе разрешены паралелльные ребра.
+
Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра или их количество (если в графе разрешены паралелльные ребра).
 
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы  и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
 
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы  и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
  
Если граф разрежен, его лучше представить в виде списков смежности, что позволит сэкономить память.
+
Если граф разрежен, его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
  
 
=== Матрица инцидентности ===
 
=== Матрица инцидентности ===

Версия 19:36, 22 октября 2011

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

Определение:
Ориентированный граф (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]v[/math] будет содержать вершины [math]u: (v, u) \in E[/math]. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.

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

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

  1. [math]graph[v][numberOfArc] = 1 \wedge graph[u][numberOfArc] = -1 \Leftrightarrow (v, u) \in E[/math]
  2. [math]graph[v][numberOfArc] = 0 \wedge graph[u][numberOfArc] = 0 \Leftrightarrow (v, u) \notin E[/math].

См. также