Маршруты, пути и циклы в графах
Маршрутом в графе G=(V, E) называется конечная последовательность смежных ребер вида: (v0,v1), (v1,v2), (v2,v3), ¼,(vk‑1,vk), или маршрутом можно считать такую последовательность вершин: (v0,v1,¼,vk), что любая пара вершин (vi‑1,vi), где 1£ i £ k является ребром графа G. Такой маршрут называется (v0‑vk)–маршрутом, а вершины v0 и vk –начальной и конечной или терминальными вершинами маршрута. Все другие вершины маршрута называются внутренними. Заметим, что ребра и вершины в маршруте могут повторяться.
Маршрут называется открытым, если его концевые вершины различны, и замкнутым или циклическим в противном случае.
Открытый маршрут называют цепью, если все ребра в нем различны (вершины могут повторяться).
Цепь, в которой не повторяются вершины, называется путем (простой цепью).
Замкнутая цепь называется циклом, замкнутый путь – простым циклом (в орграфе – контуром). Ребро графа называется циклическим, если в графе существует цикл, содержащий это ребро.
Неорграф без циклов называется ациклическим, орграф без контуров – бесконтурным.
Длиной маршрута (пути, цикла) называется число содержащихся в нем ребер. Наименьшая из длин простых циклов называется обхватом графа.
Пример:
Для графа на рис.24: открытый маршрут: (v2,v4,v1,v2,v3,v4,v1)
Замкнутый маршрут: (v2,v3,v5,v4,v3,v2)
Открытая цепь: (v2,v5,v1,v2,v4)
Замкнутая цепь (цикл): (v2,v4,v1,v2,v3,v5,v2)
Путь: (v2,v5,v1,v4,v3)
Простой цикл: (v2,v5,v1,v3,v2). Обхват графа равен 3.