2015-01-07
3570
Понятия пути, контура в ориентированном графе аналогичны понятиям маршрута, цикла в неориентированном графе.
Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги.
Число дуг пути называется длиной пути.
Путь называется контуром, если его начальная вершина совпадает с конечной вершиной.
Путь (контур), в котором все дуги различны, называется простым.
Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным.
Следует усвоить, что понятиям ребра, маршрута, цепи, цикла в неориентированном графе соответствуют понятия дуги, пути, ориентированной цепи, контура в ориентированном графе. Для лучшего запоминания приведем эти термины в таблице.
| Неориентированный граф | Ориентированный граф |
| ребро маршрут цикл | дуга путь контур |
Пример 3.12.
В приведенном на рис 3.7 графе выделим следующие пути:
(x 1, x 2, x 3, x 4) – простой элементарный путь, т.к. каждая вершина и каждая дуга используются не более одного раза;
(x 2, x 5, x 6, x 7, x 2) – простой элементарный контур, т.к. это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны.
Рис. 3.7
