logo
Лекции_по_ДМ

Маршруты, пути и циклы в графах

Маршрутом в графе 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.

    1.