Граф
| Определение: |
| Графом [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] инцидентно вершине a, если [math]u = a[/math] или [math]v = a[/math].
Для ориентированного графа
| Определение: |
| Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается [math]deg^+[/math] [math]v_i[/math]. |
| Определение: |
| Полустепенью выхода вершины [math]v_i[/math] называется число рёбер, выходящих из этой вершину, и обозначается [math]deg^-[/math] vi. |
Петля
| Определение: |
| Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть [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; k \gt 0[/math], а так же [math]v_0 e_1 v_1 ... e_k v_k \sim u_0 f_1 u_1 ... f_k u_k[/math]; где [math]u_i = v_((i+j) \pmod k); f_i = e_((i+j) \pmod k); i = 1..k[/math] |
Для неориентированного графа
| Определение: |
| Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть [math]v_0 = v_k[/math] |
