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

Маршрут в графе (путь в орграфе) из вершины i в вершину j – последовательность вершин и ребер (дуг), инцидентных двум соседним вершинам.

Путь = ориентированный маршрут.

Первая вершина последовательности – начальная вершина маршрута (пути). Последняя вершина последовательности – конечная вершина маршрута (пути). Остальные вершины последовательности – внутренние вершины маршрута (пути).

Длина маршрута (пути) – количество ребер (дуг) маршрута (пути).

Цепь (орцепь) – маршрут (путь), в котором ребра (дуги) проходятся один раз.

Простая цепь (простая орцепь) – цепь (орцепь) без повторяющихся вершин.

Петля – цепь (орцепь), содержащая один узел и одно ребро (одну дугу).

Расстояние между двумя вершинами графа (орграфа) – длина кратчайшей цепи (орцепи) между этими вершинами.

Цикл – замкнутая цепь.

Контур – замкнутая орцепь.

Простой цикл (простой контур) – замкнутая простая цепь (простая орцепь) с совпадающими начальной и конечной вершинами.

Если две вершины соединены цепью, то существует простая цепь, соединяющая эти две вершины. Для этого надо в цепи удалить внутренние циклы.

Если две вершины соединены орцепью, то существует простая орцепь, соединяющая эти две вершины. Для этого надо в цепи удалить внутренние контуры.