Пути, контуры в ориентированном графе

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

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

Число дуг пути называется длиной пути.

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

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

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

Следует усвоить, что понятиям ребра, маршрз’та, цепи, цикла в неориентированном графе соответствуют понятия дуги, пути, ориентированной цепи, контура в ориентированном графе. Для лучшего запоминания приведем эти термины в таблице (табл. 3.6).

Соответствие понятий в ориентированном и неориентированном графах.

Пример 3.9. В приведенном на рис. 3.27 графе выделим следующие пути:

• • (х, х₂, х₃, х₄) — простой элементарный путь, гак как каждая вершина и каждая дуга используются не более одного раза;
• • (х₂, х₅, х₆, х₇, х₂) — простой элементарный контур, так как это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны.

Рис. 3.27. Граф (пример 3.9)