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

Маршрут неориентированного графа G=(V, E) –чередующаяся, конечная последовательность вершин и рёбер такая, что начинается и заканчивается вершиной и каждое ребро в маршруте соединяет две вершины маршрута – предыдущую и последующую.

Обозначения или или , -маршрут.

Концевые (терминальные) вершины маршрута – v₀ и v_n, внутренние – все остальные вершины.

Замкнутый маршрут – концевые вершины совпадают , иначе– открытый .

Цепь – маршрут, все ребра которого различны (кроме, возможно, концевых).

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

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

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

Утверждение 1.

Любой (u-v) -маршрут неориентированном графе G содержит (u-v)-простую цепь.

Утверждение 2.

Любой цикл неориентированного графа содержит в себе простой цикл.

Граф, состоящий из одного простого цикла, обозначается , граф, состоящий из одной простой цепи, обозначается , здесь – количество вершин графа.

C₃ P₅

Например:

Дан граф G. Привести примеры маршрута, цепи, простой цепи, замкнутого маршрута, цикла и простого цикла.

Маршрут M1=(1, 3, 4, 7, 2, 3, 4, 6).

Для маршрута M1 вершини 1 и 6 – концевые; 2, 3, 4, 7 – внутренние.

Маршрут M1 – открытый маршрут, не цепь, не простая цепь (ребро (3, 4) повторяется).

Маршрут M2=(1, 3, 4, 7, 2, 3, 4, 6, 1).

Маршрут M2 – замкнутый маршрут, не цикл, не простой цикл(ребро (3, 4) повторяется).

Маршрут M3=(7, 5, 6, 7, 2, 4).

Маршрут M3 – не простая цепь (вершина 7 повторяется).

Маршрут M4==(7, 5, 6, 7, 2, 4, 7).

Маршрут M4 – не простой цикл (вершина 7 повторяется).

Маршрут M5=(1, 3, 4, 7, 6, 2).

Маршрут M5 – простая цепь.

Маршрут M6=(1, 3, 4, 5, 7, 6, 1).

Маршрут M6 – простой цикл.