Маршруты в неориентированном графе

Определение: Маршрутом , соединяющий вершины 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 _кон)– конец маршрута (конечная вершина).

Для графа 13.1 построим маршрут, соединяющий вершину v₁ с вершиной v₅ :

v₁x₁v₃x₃v₃v₂x₅v₆x₇v₅ .

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

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

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

Длиной маршрута l называется количество ребер в нем.

В нашем маршруте 5 ребер, значит его длина l =5.

Познакомимся с видами маршрутов.

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

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

Виды незамкнутых маршрутов:

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

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

Виды замкнутых маршрутов:

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

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

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

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

Рис. 13.5.

Маршрут v₁v₂v₃v₄ – простая цепь.

Маршрут v₂v₄v₅v₆v₆v₄ – цепь, не являющаяся простой.

Маршрут v₃v₄v₅v₆v₅ – замкнутый маршрут.

Маршрут v₃v₂v₄v₅v₆v₄v₂v₃ – цикл, не являющийся простым.

Маршрут v₃v₂v₄v₃ – простой цикл.