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

Изоморфизм орграфов. Попарно неизоморфные (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 является простым циклом.