Пример 1. Для вершин и графа G на рис.4.4 привести примеры маршрута, цепи, простой цепи; определять в графе циклический маршрут

Для вершин и графа G на рис.4.4 привести примеры маршрута, цепи, простой цепи; определять в графе циклический маршрут, цикл, простой цикл, приняв вершину за их начало и конец.

Рис. 4.4. Граф G

Для вершин , :

· Маршрут, не являющийся цепью – или и т.п.;

· Цепь, не являющаяся простой цепью – ;

· Простая цепь - или

Для вершины :

· Циклический маршрут, не являющийся циклом -;

· Цикл, не являющийся простым циклом - ;

· Простой цикл -

При описании цикла в качестве его начала и конца может быть выбрана любая вершина, поэтому последовательности , , , представляют один и тот же цикл. Более того, часто считается, что можно менять порядок ребер цикла на противоположный, т.е. последовательность представляет тот же цикл.

Дата добавления: 2014-01-05