Путь в ориентированном графе

Определение: Путем , соединяющим вершины v₁ и v_k+1 , называется последовательность v₁x₁v₂x₂…v_kx_kv_k+1 , где k 1, v_i  V, x_i X, дуга x_i соединяет вершины v_i с вершиной v_i+1 . Вершина v₁ (v _нач)– начало пути (начальная вершина), v_k+1 (v _кон)– конец пути (конечная вершина). Остальные вершины называются внутренними вершинами пути.

Найдем какой-либо путь из v₁ в v₃ : v₁x₁v₂x₃v₂x₄v₃ .

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

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

Перепишем наш путь, использую комбинированную запись: v₁x₁v₂v₂v₃. В последовательность включено только кратное ребро x₁ .

Длиной пути l называется количество дуг в нем.

В нашем пути 3 дуги, значит его длина l =3.

Познакомимся с видами путей.

Если v_нач = v_кон , то путь называется замкнутым.

Если v_нач  v_кон , то путь называется незамкнутым.

Виды незамкнутых путей:

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

Цепь, в которой все вершины попарно различны называется простой цепью.

Виды замкнутых путей:

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

Контур, в котором все вершины попарно различны называется простым контуром.

Заметим, что петля являются простым контуром.

Составим различные пути для приведенного выше орграфа :

v₁x₁v₂x₃v₂x₄v₃ – незамкнутый путь, являющийся цепью (в нем все дуги попарно различны);

v₂x₃v₂ – простой контур;

v₁x₂v₂x₄v₃ – простая цепь (все вершины и дуги попарно различны).

Для графа D(V,X) справедливы утверждения:

Из любого контура можно выделить простой контур.

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