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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Представление)
Строка 24: Строка 24:
  
 
Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <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>.
  
 
Если граф разрежен, его лучше представить в виде списков смежности, что позволит сэкономить память.
 
Если граф разрежен, его лучше представить в виде списков смежности, что позволит сэкономить память.
Строка 30: Строка 30:
 
=== Матрица инцидентности ===
 
=== Матрица инцидентности ===
  
Имеет место и другое представление графа -  [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть <tex>graph[v][numberOfArc] = -1 and graph[u][numberOfArc] = 1 \Leftrightarrow (v, u) \in E</tex>
+
Имеет место и другое представление графа -  [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть <tex>graph[v][numberOfArc] = -1 \wedge graph[u][numberOfArc] = 1 \Leftrightarrow (v, u) \in E</tex> и <tex>graph[v][numberOfArc] = 0 \wedge graph[u][numberOfArc] = 0 \Leftrightarrow (v, u) \notin E</tex>.
  
 
[[Файл:Directed-graph.png|thumb|Ориентированный граф]]
 
[[Файл:Directed-graph.png|thumb|Ориентированный граф]]

Версия 22:10, 20 октября 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]beg, end: E \to V[/math].


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


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


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

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

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

Если граф разрежен, его лучше представить в виде списков смежности, что позволит сэкономить память.

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

Имеет место и другое представление графа - матрица инцидентности, которая сопоставляет множество вершин множеству ребер. То есть [math]graph[v][numberOfArc] = -1 \wedge graph[u][numberOfArc] = 1 \Leftrightarrow (v, u) \in E[/math] и [math]graph[v][numberOfArc] = 0 \wedge graph[u][numberOfArc] = 0 \Leftrightarrow (v, u) \notin E[/math].

Ориентированный граф

См. также