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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Для неориентированного графа)
(Для ориентированного графа)
Строка 29: Строка 29:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Полустепенью входа вершины v<sub>i</sub> называется число рёбер, входящих в эту вершину, и обозначается <tex>deg^+</tex> <tex>v_i</tex>.
+
Полустепенью входа вершины v<sub>i</sub> называется число рёбер, входящих в эту вершину, и обозначается <tex>deg^+v_i</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Полустепенью выхода вершины <tex>v_i</tex> называется число рёбер, выходящих из этой вершину, и обозначается <tex>deg^-</tex> v<sub>i</sub>.
+
Полустепенью выхода вершины <tex>v_i</tex> называется число рёбер, выходящих из этой вершину, и обозначается <tex>deg^-v_i</tex>.
 
}}
 
}}
  

Версия 03:16, 17 января 2011

Граф

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

В неориентированном графе [math](v, u) = (u, v)[/math].

Ребро

Для неориентированного графа

Определение:
Ребром называют неупорядоченную пару вершин [math] (v, u) \in E [/math].

Для ориентированного графа

Определение:
Ребром называют упорядоченную пару вершин [math] (v, u) \in E [/math].


Степень вершины

Для неориентированного графа

Определение:
Степенью вершины vi называется число рёбер инцидентных [math]v_i[/math], и обозначается deg [math]v_i[/math]

Говорят, что ребро [math] e = (u, v) [/math] инцидентно вершине [math]a[/math], если [math]u = a[/math] или [math]v = a[/math].

Для ориентированного графа

Определение:
Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается [math]deg^+v_i[/math].


Определение:
Полустепенью выхода вершины [math]v_i[/math] называется число рёбер, выходящих из этой вершину, и обозначается [math]deg^-v_i[/math].


Петля

Определение:
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть [math]e=\{v,v\}[/math].

По умолчанию петли в неориентированном графе запрещены.

Путь

Определение:
Путём в графе называется последовательность вида [math]v_0 e_1 v_1 ... e_k v_k[/math]; где [math]e_i = (v_{i-1}, v_i)[/math].


Циклический путь

Для ориентированного графа

Определение:
Путь такой, в котором [math]v_0 = v_k[/math] называется циклическим путём.


Для неориентированного графа

Определение:
Путь такой, в котором [math]v_0 = v_k[/math], а так же [math] e_i \ne e_{(i+1) \mod k}[/math] называется циклическим путём.


Цикл

Определение:
Цикл - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если [math] \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}[/math]; где e и e' - это две последовательности ребер в циклическом пути.