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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
}}
 
}}
  
Для ориентированного графа справедлива [[лемма о рукопожатиях|Лемма о рукопожатиях]], связывающая количество ребер с суммой [[степеней вершин|Степень вершины]].
+
Для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов|степеней вершин]].
  
 
{{Определение
 
{{Определение

Версия 21:31, 20 октября 2011

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


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


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


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


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

Ребро обозначается как пара вершин [math](v, u)[/math], где [math]v[/math] - начало ребра, а [math]u[/math] - конец. Причём [math](v, u) \ne (u, v)[/math].

См. также