2014-02-12
7615
Маршрутом в графе G =(V, E) называется конечная последовательность смежных ребер вида: (v 0, v 1), (v 1, v 2), (v 2, v 3), ¼,(vk‑ 1, vk), или маршрутом можно считать такую последовательность вершин: (v 0, v 1,¼, vk), что любая пара вершин (vi‑ 1, vi), где 1£ i £ k является ребром графа G. Такой маршрут называется (v 0‑ vk)–маршрутом, а вершины v 0 и vk – начальной и конечной или терминальными вершинами маршрута. Все другие вершины маршрута называются внутренними. Заметим, что ребра и вершины в маршруте могут повторяться.
Маршрут называется открытым, если его концевые вершины различны, и замкнутым или циклическим в противном случае.
Открытый маршрут называют цепью, если все ребра в нем различны (вершины могут повторяться).
Цепь, в которой не повторяются вершины, называется путем (простой цепью).
Замкнутая цепь называется циклом, замкнутый путь – простым циклом (в орграфе – контуром). Ребро графа называется циклическим, если в графе существует цикл, содержащий это ребро.
Неорграф без циклов называется ациклическим, орграф без контуров – бесконтурным.
Длиной маршрута (пути, цикла) называется число содержащихся в нем ребер. Наименьшая из длин простых циклов называется обхватом графа.
Пример:
Для графа на рис.24: открытый маршрут: (v 2, v 4, v 1, v 2, v 3, v 4, v 1)
Замкнутый маршрут: (v 2, v 3, v 5, v 4, v 3, v 2)
Открытая цепь: (v 2, v 5, v 1, v 2, v 4)
Замкнутая цепь (цикл): (v 2, v 4, v 1, v 2, v 3, v 5, v 2)
Путь: (v 2, v 5, v 1, v 4, v 3)
Простой цикл: (v 2, v 5, v 1, v 3, v 2). Обхват графа равен 3.
