Маршруты, цепи, циклы

Маршрутом от вершины u к вершине v или (u,v) маршрутом в графе G называется всякая последовательность вида

,

где e_k – ребро, соединяющее вершины и В случае орграфа – начало ребра е_k , a v_k – его конец. При этом вершину u называют началом маршрута, а вершину v – его концом. В маршруте некоторые вершины и ребра могут совпадать. Маршрут можно задавать последовательностью вершин а также последовательностью ребер . Число ребер в маршруте называется его длиной. Маршрут называется цепью, если в нем нет совпадающих ребер, и простой цепью – если дополнительно нет совпадающих вершин, кроме, может быть, начала и конца цепи. Если начало цепи (простой цепи) совпадает с ее концом, то такая цепь называется циклом (простым циклом). Граф без циклов называется ациклическим.

Пример 4.9.

(1,2,4,7) – простая цепь;

(1,2,4,7,8,4) – цепь, не являющаяся простой;

(1,2,4,7,8,4,2) – маршрут, не являющийся цепью;

(1,2,4,7,8,4,1) – цикл, не являющийся простым;

(1,2,4,1) – простой цикл.

Граф называется связным, если любые две вершины u и v в нем можно соединить (u,v) маршрутом. Легко видеть, что отношение связности на множестве вершин является отношением эквивалентности. Данное отношение разбивает множество вершин графа на классы, объединяющие вершины, которые можно связать друг с другом маршрутом. Такие классы называются компонентами связности. Связный граф имеет одну компоненту связности.

Пример 4.10.

Граф на рисунке имеет две компоненты связности.