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

Введем понятие маршрута для графа G = (V, E) (и соответственно понятие пути для орграфа D = (V, E)).

Определение. Маршрутом в данном графе G называется конечная последовательность ребер вида {v0, v1}, {v1, v2}, …, {vm-1, vm} (обозначаемая также v0®v1®v2®…®vm).

Каждому маршруту соответствует последовательность вершин v0v1v2…vm; v0 – начальная вершина, а vm – конечная вершина маршрута. Одна и та же вершина может одновременно оказаться начальной, конечной и внутренней. Таким образом, мы будем говорить о маршруте из v0 в vm.

Определение. Длиной маршрута называется число ребер в нем.

Определение. Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины тоже различны (кроме, может быть, начальной и конечной вершин).

Определение. Цепь или простая цепь замкнуты, если начальная и конечная вершины совпадают.

Определение. Замкнутая простая цепь, содержащая, по крайней мере, одно ребро, называется циклом.

Определение. Обхватом графа называется длина его кратчайшего цикла.