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

2. Пути и маршруты

Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Так, на рис. 1.2 последовательности дуг

являются путями.

Рис. 1.2.

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

Ориентированной цепью (или, короче, орцепъю) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например, приведенные выше пути (1.1) и (1.2) являются орцепями, а путь (1.3) не является таким, поскольку дуга в нем используется дважды.

Простой орцепъю называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (1.2) является простой орцепью, а пути (1.1) и (1.3) — нет. Очевидно, что простая ордепь является также орцепью, но обратное утверждение неверно. Например, путь (1.1) является орцепью, но не простой орцепью, путь (1.2) является орцепью и простой орцепью, а путь (1.3) не является ни орцепью, ни простой орцепью. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь

направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер в которой каждое ребро за исключением, возможно, первого и последнего ребер, связано с ребрами своими двумя концевыми вершинами. Последовательности дуг

и

в графе, изображенном на рис. 1.2, являются маршрутами; черта над символом дуги означает, что ее ориентацией пренебрегают, т. е. дуга рассматривается как неориентированное ребро.

Точно так же, как мы определили орцепи и простые орцепи, можно определить цепи и простые цепи. Так, например, маршрут (1.4) есть цепь и простая цепь, маршрут (1.5) — цепь, но не простая цепь, а маршрут (1.6) не является ни цепью, ни простой цепью.

Путь или маршрут можно изображать также последовательностью вершин, что мы и будем использовать. Путь (1.1) можно представить также последовательностью вершин и такое представление часто оказывается более полезным в тех случаях, когда осуществляется поиск простых орцепей или простых цепей.

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