![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Пример. На рис. 2 последовательности дуг
а6, a5, a9, a8, a4 (1.1)
a1, a6, a5, a9 (1.2)
a1, a6, a5, a9, a10, a6, a4 (1.3)
являются путями.
Путем в графе G = <V, E> назовем последовательность вершин v 0, v 1,..., v k такую что k ≥ 0 п vi - vi+1 (или и vi → vi+1, если граф G — ориентированный), i = 0,..., k - 1. Термин «путь» в теории графов используется только в отношении орграфов, для графов используются термины «цепь» или «маршрут». Вершины v 0 и v k будем называть соответственно началом и концом пути, а число k — длиной пути. Путь, начало и конец которого совпадают, будем называть циклом. Введенный так термин «цикл» в теории графов используется только в отношении графов, для орграфов используется термин «контур».
Если все вершины пути v 0, v 1,..., v k различны, то будем говорить об элементарном пути. Соответственно цикл v 1,..., v k (v 1 = v k ) будем называть элементарным, если вершины v 1,..., v k различны.
Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер , в которой каждое ребро
, за исключением, возможно, первого и последнего ребер, связано с ребрами
и
своими двумя концевыми вершинами.
Пример.
Последовательности дуг
(1.4)
(1.5)
(1.6)
в графе, изображенном на рис. 2, являются маршрутами; черта над символом дуги означает, что ее ориентацией пренебрегают, т. е. дуга рассматривается как неориентированное ребро.
Дата публикования: 2014-11-04; Прочитано: 379 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!