Замкнутый маршрут
Замкнутый маршрут — это маршрут в графе, который начинается и заканчивается в одной и той же вершине. По дороге можно проходить через вершины и рёбра повторно, поэтому замкнутый маршрут не обязательно является циклом.
Как распознать
Сначала найдите первую и последнюю вершины последовательности. Если они одинаковы, маршрут замкнутый. Например, последовательность \(A \to B \to C \to A\) начинается и заканчивается в вершине \(A\). Возврат может происходить после любого положительного числа переходов.
В графе есть рёбра \(AB\), \(BC\) и \(CA\). Последовательность \(A \to B \to C \to A\) — замкнутый маршрут длины \(3\). Если маршрут имеет вид \(A \to B \to A \to B \to A\), он также замкнутый: вершины и рёбра повторяются, но начало и конец совпадают.
Здесь \(v_0\) и \(v_k\) — начальная и конечная вершины, а \(L\) — длина маршрута, то есть число пройденных рёбер. У замкнутого маршрута длина не может быть равна нулю: должен быть выполнен хотя бы один переход.
Цикл — более специальное понятие. В цикле обычно требуют, чтобы внутри маршрута не повторялись вершины и рёбра, а совпадали только первая и последняя вершины. У замкнутого маршрута таких ограничений нет. Поэтому каждый цикл является замкнутым маршрутом, но не каждый замкнутый маршрут является циклом.
Какая последовательность является замкнутым маршрутом?
Главное
- Замкнутый маршрут начинается и заканчивается в одной вершине: \(v_0=v_k\).
- В нём могут повторяться вершины и рёбра.
- Маршрут в графе — более общее понятие, а цикл является частным случаем замкнутого маршрута.