Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

Например, для графа на рис. 8.1 последовательности дуг

M1: a6, a5, a9, a8, a4,

M2: a1, a6, a5, a9, a7,

M3: a1, a6, a5, a9, a10, a6, a4

являются путями. Пути могут быть различными.


Рис. 8.1. Орграф

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

Так пути M1 и M2 являются орцепями, а M3 нет, поскольку дуга a6 используется дважды.

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

Простой орцепью является путь M2.

Для неориентированного графа понятия маршрута, цепи и простой цепи аналогичны понятиям пути, орцепи и простой орцепи в орграфе. (В определениях следует заменить слово "дуга" на слово "ребро").

Путь или маршрут можно изображать также последовательностью вершин. Так путь M1 можно представить последователь-ностью вершин х2, х5, х4, х3, х5, х6, и такое представление часто оказывается более полезным.





Дата публикования: 2014-11-04; Прочитано: 375 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...