И код направления подготовки
Эйлеровы цепи и циклы. Гамильтоновы цепи и циклы
жүктеу/скачать 341.63 Kb.
|
- Бұл бет үшін навигация:
- Существование эйлерова цикла и эйлерова пути
- В неориентированном графе
- В ориентированном графе
- Поиск эйлерова пути в графе
- Поиск эйлерова цикла в графе
| Эйлеровы цепи и циклы. Гамильтоновы цепи и циклы.
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу. (ср. Гамильтонов путь) Эйлеров цикл — это эйлеров путь, являющийся циклом. Эйлеров граф — граф, содержащий эйлеров цикл. Полуэйлеров граф — граф, содержащий эйлеров путь (цепь). Существование эйлерова цикла и эйлерова путиЭйлеров цикл/путь существуют только в связных графах или в графах, которые после удаления всех одиночных вершин превратятся в связные. В неориентированном графе:Кроме того, согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени. Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени. Ввиду леммы о рукопожатиях, число вершин с нечётной степенью должно быть четным. А значит Эйлеров путь существует только тогда, когда это число равно нулю или двум. Причём когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл. В ориентированном графе:Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно связан и для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из неё и выходит. Поиск эйлерова пути в графеМожно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 2 вершины нечётной степени. Соединим эти вершины ребром, и получим граф, в котором все вершины чётной степени, и эйлеров цикл в нём существует. Найдём в этом графе эйлеров цикл (алгоритмом, описанным ниже), а затем удалим из ответа несуществующее ребро. Поиск эйлерова цикла в графеБудем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один. Реализовать это можно, например, так, рекурсивно: procedure find_all_cycles (v) var массив cycles 1. пока есть цикл, проходящий через v, находим его добавляем все вершины найденного цикла в массив cycles (сохраняя порядок обхода) удаляем цикл из графа 2. идем по элементам массива cycles каждый элемент cycles[i] добавляем к ответу из каждого элемента рекурсивно вызываем себя: find_all_cycles (cycles[i]) Достаточно вызвать эту процедуру из любой неодиночной вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл. Для поиска цикла на шаге 1 используем поиск в глубину. Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе. Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф — эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. жүктеу/скачать 341.63 Kb. Достарыңызбен бөлісу:
|