Изменения

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

В неориентированном графе <tex>(v, u) = (u, v)</tex>.

Ребром называют неупорядоченную пару вершин <mathtex> (v, u) \in E </mathtex>.

Ребром называют упорядоченную пару вершин <mathtex> (v, u) \in E </mathtex>.

Степенью вершины v_i называется число рёбер инцидентных v<subtex>iv_i</subtex>, и обозначается deg v<subtex>iv_i</subtex>

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

Полустепенью входа вершины v_i называется число рёбер, входящих в эту вершину, и обозначается deg<suptex>deg^+</suptex> v<subtex>iv_i</subtex>.

Полустепенью выхода вершины v<subtex>iv_i</subtex> называется число рёбер, выходящих из этой вершину, и обозначается deg<suptex>deg^-</suptex> v_i.

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

Путём в графе называется последовательность вида v₀ e₁ v<sub>1</subtex> v_0 e_1 v_1 ... e_k v<sub>ke_k v_k</subtex>; где e<sub>i</subtex> e_i = (v_{v_(i-1}); v<sub>iv_i)</subtex>).

Циклом называется путь, начало и конец которого совпадают, тоесть v<sub>0</subtex> v_0 = v<sub>kv_k</subtex>

Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v<sub>0</subtex> v_0 = v<sub>kv_k</subtex>