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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 20 промежуточных версий этого же участника)
Строка 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>beg, end: E \to V</tex>.
 
}}
 
 
 
Для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов|степеней вершин]].
 
 
 
 
 
{{Определение
 
|definition =
 
Ребро ориентированного графа называется '''дугой (arc)'''.
 
}}
 
 
 
== Представление ==
 
 
 
Ориентированный граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы может хранится вес ребра либо их количество, если в нашем графе разрешены паралелльные ребра.
 
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и смежность и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>
 
 
 
Имеет место и другое представление графа -  матрица инцидентности.
 
 
 
[[Файл:Directed-graph.png|thumb|Ориентированный граф]]
 
 
 
== См. также ==
 
*[[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 

Текущая версия на 03:40, 18 января 2012