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

Теория.

Пусть G - неориентированный граф.

Маршрутом в G называется такая последовательность ребер М(е₁, е₂,..., e_i,..., е_п), в которой каждые два соседних ребра е_i-1 и е_i имеют общую вершину. В маршруте одно и то же ребро может встречаться несколько раз. Начало маршрута – вершина v₀, инцидентная ребру е₁ и не инцидентная е₂; конец маршрута v_n инцидентен е_п и не инцидентен е_п-1.

Если е₁, е₂, (е_п-1, е_п) – кратные, требуется дополнительное указание, какую из двух инцидентных вершин считать началом (концом) маршрута.

Маршрут, в котором совпадают его начало и конец v₀ = v_n, (т.е замкнутый), называется циклическим. Маршрут, в котором все ребра разные, называется цепью. Цепь, не пересекающая себя, т.е. не содержащая повторяющихся вершин, именуется простой цепью.

Циклический маршрут называется циклом, если он является цепью, и простым циклом, когда это – простая цепь.

Пусть G - ориентированный граф

Последовательность ребер, в которой конец каждого предыдущего ребра е_i-1 совпадает с началом следующего е_i, называется путем (в нем все ребра проходят по их ориентации). В пути одно и то же ребро может встречаться несколько раз. Началом пути является начало v₀ ребра e₁ концом пути – конец v_n ребра е_п.

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

Эйлеров цикл – цикл графа, содержащий все ребра графа. Эйлеров граф –граф, имеющий эйлеров цикл (эйлеров цикл можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги).

Теорема Эйлера. Конечный неориентированный граф G эйлеров тогда и только тогда, когда он связен и степени всех его вершин четны.

Эйлерова цепь – цепь, включающая все ребра данного конечного н-графа G, но имеющая различные начало v_i и конец v_j. Чтобы в конечном н-графе G существовала эйлерова цепь, необходимы и достаточны его связность и четность степеней всех вершин, кроме начальной v_i и конечной v_j (v_i и v_j должны иметь нечетные степени). Чтобы в конечном орграфе существовал эйлеров цикл, необходимы и достаточны его связность а также равенство степеней вершин этого графа по входящим и выходящим ребрам, т.е. .

Алгоритм поиска эйлерового цикла задается следующими правилами:

1. Выбрать произвольную вершину a.

2. Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным).

3. Каждое пройденное ребро вычеркнуть и присвоить ему номер, на единицу больший номера предыдущего вычеркнутого ребра.

4. Находясь в вершине x, не выбирать ребро, соединяющее x с a, если имеется возможность другого выбора.

5. Находясь в вершине x, не выбирать ребро, которое является перешейком (т.е. ребром, при удалении которого граф, образованный невычеркнутыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы по одному ребру).

6. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл, причем порядок нумерации соответствует последовательности обхода ребер.

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

Пример 7. Найти эйлеров цикл в эйлеровом графе, изображенном на рис. 6.

Рис. 6

Решение.

Граф является эйлеровым на основании теоремы Эйлера, т.к. он связен и степени его вершин четные.

и т.д.

Рис. 7

После выбора вершины a и прохождения ребер 1 и 2 имеются три возможные выбора: ребра 3, 6 или 7. Так как ребро 7 является перешейком, выбираем следующее ребро из оставшихся, например 3. Далее обходим оставшиеся ребра и получаем эйлеров цикл: 1, 2, 3, 4, 5, 6, 7, 8, как показано на рис. 8.

Рис. 8

Пример 8. Имеют ли графы изображенный на рис. 9 гамельтоновы цепи и ли циклы?

Рис. 9

Решение.

Гамельтонов цикл как простой цикл, проходящий через все вершины графа, существует в графе G₁ – он проходит по ребрам, соеденяющим вершины a, b, c, d, e, f, g, q, n, m, l, h, a. В G₁ существует и гамельтонова цепь, для чего в гамельтоновом цикле достаточно удалить любое ребро.

В графе G₂ гамельтонова цикла нет: чтобы пройти через вершины a, b, c внешнего треугольника графа G₂ гамельтонов цикл должен содержать все лежащие на этих сторонах ребра, но тогда он не проходит через расположенную в центре треугольника вершину d. Однако гамельтонова цепь в графе G₂ существует, например с началом в вершине a, концом d и последовательностью ребер, соединяющих вершины a, f, b, g, c, e, d.