Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

Маршрут в графе представляет собой конечную чередующуюся последовательность вершин начинающуюся и кончающуюся на вершинах, причем являются концевыми вершинами ребра . С другой стороны, маршрут можно рассматривать как конечную последовательность таких вершин , что ребро графа G. Такой маршрут обычно называется -маршрутом, — концевыми или терминальными вершинами маршрута.

Все другие вершины маршрута называются внутренними. Заметим, что ребра и вершины в маршруте могут появляться более одного раза.

Маршрут называется открытым, если его концевые вершины различны, в противном случае он называется замкнутым.

В графе на рис. 1.6 последовательность является открытым маршрутом, а последовательность — замкнутым.

Рис. 1.6. Граф G.

Маршрут называется цепью, если все его ребра различны. Цепь называется открытой, если ее концевые вершины различны, в противном случае она называется замкнутой. На рис. 1.6 цепь — открытая, а — замкнутая.

Открытая цепь называется путем, если все ее вершины различны.

Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.

Например, на рис. 1.6 последовательность является путем, а последовательность — циклом.

Ребро графа G называется циклическим, если в графе G существует цикл, содержащий ребро. В противном случае ребро называется нециклическим. На рис. 1.6 все ребра, за исключением циклические.

Число ребер в пути называется длиной пути. Аналогично определяется длина цикла.

Необходимо указать следующие свойства путей и циклов.

1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1.

2. Каждая вершина цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл, — неверно. Более общий вопрос обсуждается в гл. 3.

3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.

<< Предыдущий параграф Следующий параграф >>
Оглавление