Основные определения теории графов

Граф

Определение:

Графом [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]C = (v_0 e_1 v_1 ... e_k v_k)[/math], где [math]v_0 = v_k[/math] называется циклом.

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

Определение:

[math]C = (v_0 e_1 v_1 ... e_k v_k)[/math], где[math]v_0 = v_k[/math], а [math] e_i \ne e_{i+1}[/math] называется циклом.