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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Представление)
Строка 30: Строка 30:
 
=== Матрица инцидентности ===
 
=== Матрица инцидентности ===
  
Имеет место и другое представление графа -  [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть <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>.  
+
Имеет место и другое представление графа -  [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:
 +
# <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:12, 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].

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

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

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

  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].
Ориентированный граф

См. также