Материал из Викиконспекты
|
|
| (не показаны 23 промежуточные версии этого же участника) |
| Строка 1: |
Строка 1: |
| − | {{Определение
| + | #REDIRECT [[Основные определения теории графов#Ориентированные графы]] |
| − | |definition =
| |
| − | '''Ориентированный граф (directed graph) <tex> G </tex>''' - это пара <tex> G = (V, E) </tex>, где <tex>V</tex> - конечное множество вершин, а <tex>E \subset V \times V </tex> - множество рёбер.
| |
| − | }}
| |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | Также '''ориентированным графом <tex> G </tex>''' - называется четверка <tex> G = (V, E, begin, end) </tex>, где <tex>beg, end: E /to V</tex>.
| |
| − | }}
| |
| − | | |
| − | Для ориентированного графа справедлива [[лемма о рукопожатиях|Лемма о рукопожатиях]], связывающая количество ребер с суммой [[степеней вершин|Степень вершины]].
| |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | Ребро ориентированного графа называется '''дугой (arc)'''.
| |
| − | }}
| |
| − | | |
| − | [[Файл:Directed-graph.png|thumb|Ориентированный граф]]
| |
| − | | |
| − | Ребро обозначается как пара вершин <tex>(v, u)</tex>, где <tex>v</tex> - начало ребра, а <tex>u</tex> - конец. Причём <tex>(v, u) \ne (u, v)</tex>.
| |
| − | | |
| − | == См. также ==
| |
| − | *[[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
| |
| − | | |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Основные определения теории графов]]
| |
Текущая версия на 03:40, 18 января 2012
