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

Граф

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

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

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

Ребро

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

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

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

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

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

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

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

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

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

Степенью вершины vi называется число рёбер инцидентных vi, и обозначается deg vi

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

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

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

Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается deg+ vi.

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

Полустепенью выхода вершины vi называется число рёбер, выходящих из этой вершину, и обозначается deg- vi.

Петля

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

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

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

Путь

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

Путём в графе называется последовательность вида v0 e1 v1 ... ek vk; где ei = (vi-1; vi).

Цикл

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

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

Циклом называется путь, начало и конец которого совпадают, тоесть v0 = vk

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

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

Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v0 = vk