Определение 1.5

Пути и циклы

По аналогии с картой дорог, мы можем рассматривать различные типы маршрутов для графа. При этом актуальными могут оказаться вопросы типа: имеется ли маршрут, начинающийся и заканчивающийся в одном и том же городе (точке), который проходит через за­данное множество городов (точек) без прохождения дважды по одно­му и тому же пути? Как и прежде нам потребуется введение некоторых определений.

(i) Последовательностью ребер длины п графа Г называется последовательность ребер е₁, е₂,..., е_n (необязательно все ребра должны быть различны) таких, что е_i; и e_i+1 — смежные ребра для всех i=l, 2,..., n-1. Последовательность ребер определяет последовательность вершин (опять, не обязательно все должны быть различными) v₀, v_l, v₂,..., v_n-1, v_n где (e_i)={ v_i-1, v_i}. При этом v₀ —начальная вершина; v_n - конечная вершина.

(ii) Путь - это последовательность ребер, в которой все ребра различные. Если, к тому же, все вершины различны (за исключением, может быть v₀ = v_n), то путь называется простым.

(iii) Последовательность ребер называется замкнутой, если v₀ = v_n. Замкнутый простой путь, содержащий, по крайней мере, одно ребро, называется циклом.

Последовательность ребер графа — это такая последовательность которую можно прочертить карандашом без его отрыва от бумаги. При этом допускается повторное прохождение ребер, многократное прохождение по петлям и т, д. Когда мы говорим о пути, то наши возможности резко сужаются. Не разрешается проходить по одному и тому же ребру более одного раза. Если к тому же мы не проходим через одну и ту же вершину более одного раза (что исключает возможность прохождения по петле), то путь будет называться простым. Последовательность ребер или путь будет замкнутым, если мы начинаем и заканчиваем движения в одном и том же месте.

Дата добавления: 2014-12-27