Маршруты, цепи, циклы в графах.

Изоморфизм орграфов. Попарно неизоморфные (p,q)-орграфы.

Орграфы G₁=(V₁,E₁) и G₂=(V₂,E₂) называются изоморфными, если существует биекция j: V₁®V₂, которая сохраняет отношение смежности между вершинами орграфа:

"u,vÎV₁ ((u,v)ÎE₁Û(j(u),j(v))ÎE₂).

Пример. Приведем все попарно неизоморфные (3,2)-орграфы:

 

Маршрут (или путь) в графе – это чередующаяся последовательность вершин и ребер u₁, p₁, u₂, p₂, …, u_n, p_n, u_n+1, начинающаяся и кончающаяся вершиной, и каждое ребро p_i инцидентно вершинам u_i и u_i+1, где i=1,…,n.

Этот маршрут обычно обозначается по вершинам: u₁u₂…u_nu_n+1.

Маршрут называется замкнутым, если u_n+1=u₁, и открытым, если u_n+1¹u₁. Цепь – это открытый маршрут, в котором все ребра различны. Простая цепь – это маршрут, в котором все вершины различны. Если в маршруте два ребра равны, то равны и вершины – их концы. Значит, если все вершины маршрута различны, то и все ребра различны, поэтому простая цепь является цепью.

Пример 1. Рассмотрим граф с вершинами 1, 2, 3, 4, 5 и 6 с ребрами {1,2}, {1,4}, {2,3}, {2,4}, {2,5}, {3,5}, {3,6} и {5,6}.

Приведем некоторые открытые маршруты в этом графе.

Маршрут 1253256 не является цепью.

Маршрут 1245236 является цепью, но не является простой цепью.

Маршрут 124536 является простой цепью.

Цикл – это замкнутая цепь. Простой цикл – это замкнутая простая цепь с числом вершин ³3.

Приведем некоторые замкнутые маршруты в графе примера 1.

Маршрут 12532541 не является циклом.

Маршрут 1235241 является циклом, но не является простым циклом.

Маршрут 1235241 является простым циклом.