Маршруты, цепи и циклы.

Пусть G(V,Е) – неориентированный граф. Рассмотрим конечную последовательность рёбер такую, что любые два соседние ребра имеют одну общую инцидентную вершину . Эту последовательность называется маршрутом графа.

Определение. Маршрутом в графе называется чередующаяся последовательность вершин и рёбер , в которой любые два соседних элемента являются инцидентными.

Определение. Длиной маршрута называется число ребер в нём с учётом повторений.

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

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

Определение. Циклом называется замкнутый маршрут с различными ребрами.

Определение. Простыми называются цепь и цикл с различными вершинами.

Пример. В графе, диаграмма которого приведена на рисунке 3 пункта 2:

последовательность является открытым маршрутом длиной 3; последовательность является простой цепью длиной 3; последовательность является простым циклом длиной 3.

(Рис. 3)

Дата добавления: 2015-10-13