Поиск эйлерова цикла в графе алгоритм
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 16 декабря 2020; проверки требует 1 правка.
Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует.
Каждая вершина этого графа имеет чётную степень, поэтому этот граф — эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл.
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу. (ср. Гамильтонов путь)
Эйлеров цикл — эйлеров путь, являющийся циклом, то есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
Эйлеров граф — граф, содержащий эйлеров цикл.
Полуэйлеров граф — граф, содержащий эйлеров путь.
Существование эйлерова цикла и эйлерова пути[править | править код]
В неориентированном графе[править | править код]
Согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный или будет являться связным, если удалить из него все изолированные вершины, и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени.[1][2] Ввиду леммы о рукопожатиях, число вершин с нечётной степенью должно быть чётным. А значит эйлеров путь существует только тогда, когда это число равно нулю или двум. Причём, когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе[править | править код]
Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно связан или среди его компонент сильной связности только одна содержит ребра (а все остальные являются изолированными вершинами) и для каждой вершины графа её входящая степень равна её исходящей степени , то есть в вершину входит столько же ребер, сколько из неё и выходит: .
Так как эйлеров цикл является частным случаем эйлерова пути, то очевидно, что ориентированный граф содержит эйлеров путь тогда и только тогда, когда он содержит либо эйлеров цикл, либо эйлеров путь, не являющийся циклом. Ориентированный граф содержит эйлеров путь, не являющийся циклом, тогда и только тогда, когда существуют две вершины и (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами и , а все остальные вершины имеют одинаковые полустепени исхода и захода: [3].
Поиск эйлерова пути в графе[править | править код]
Можно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 2 вершины нечётной степени. Соединим эти вершины ребром, и получим граф, в котором все вершины чётной степени, и эйлеров цикл в нём существует. Найдём в этом графе эйлеров цикл (алгоритмом, описанным ниже), а затем удалим из ответа несуществующее ребро.
Поиск эйлерова цикла в графе[править | править код]
Алгоритм Флёри[править | править код]
Основной источник: M. Fleury. Deux problèmes de Géométrie de situation (фр.) // Journal de mathématiques élémentaires [et spéciales]. — Paris: C. Delagrave, 1883. — Vol. 2, livr. 2nd ser.. — P. 257–261.
Алгоритм был предложен Флёри в 1883 году.
Пусть задан граф . Начинаем с некоторой вершины и каждый раз вычеркиваем пройденное ребро. Не проходим по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты (не считая изолированных вершин), т.е. необходимо проверять, является ли ребро мостом или нет.
Этот алгоритм неэффективен: время работы оригинального алгоритма O(|E|2). Если использовать более эффективный алгоритм для поиска мостов[4], то время выполнения можно снизить до , однако это всё равно медленнее, чем другие алгоритмы.
Алгоритм может быть распространен на ориентированные графы.
Алгоритм на основе циклов[править | править код]
Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.
Реализовать это можно, например, так, рекурсивно:
procedure find_all_cycles (v)
var массив cycles
1. пока есть цикл, проходящий через v, находим его
добавляем все вершины найденного цикла в массив cycles (сохраняя порядок обхода)
удаляем цикл из графа
2. идем по элементам массива cycles
каждый элемент cycles[i] добавляем к ответу
из каждого элемента рекурсивно вызываем себя: find_all_cycles (cycles[i])
Достаточно вызвать эту процедуру из любой вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл.
Для поиска цикла на шаге 1 используем поиск в глубину.
Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.
Примечания[править | править код]
См. также[править | править код]
- Гамильтонов цикл
- Граф (математика)
- Задача о ходе коня
- Дискретная математика
- Проблема семи мостов Кёнигсберга
- Список объектов, названных в честь Леонарда Эйлера
Ссылки[править | править код]
- Реализация алгоритма поиска эйлерова цикла (краткие описания и программы на C++)
- Реализация алгоритма поиска эйлерова цикла на codenet.ru
- Теория графов и комбинаторика
- Графы. Циклы и разрезы (ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ, Визуализаторы)
- Е. Гик. «Шахматы и математика» Конь-хамелеон
- Weisstein, Eric W. Eulerian Circuit (англ.) на сайте Wolfram MathWorld.
Источник
Алгоритм[править]
Описание алгоритма[править]
Алгоритм находит Эйлеров цикл как в ориентированном, так и в неориентированном графе. Перед запуском алгоритма необходимо проверить граф на эйлеровость. Чтобы построить Эйлеров путь, нужно запустить алгоритм из вершины с нечетной степенью.
Алгоритм напоминает поиск в ширину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в стеке . Когда наступает такой момент, что для текущей вершины все инцидентные ей ребра уже пройдены, записываем вершины из в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.
Псевдокод[править]
Код проверки графа на эйлеровость:
boolean checkForEulerPath():
int OddVertex
for
if () mod
OddVertex++
if OddVertex // если количество вершин с нечетной степенью больше двух, то граф не является эйлеровым
return false
boolean visited(, false) // массив инициализируется значениями false
for
if ()
dfs(, visited)
break
for
if () and not visited[] // если количество компонент связности, содержащие ребра, больше одной,
return false // то граф не является эйлеровым
return true // граф является эйлеровым
Код построения эйлерова пути:
function findEulerPath(): // если граф является полуэйлеровым, то алгоритм следует запускать из вершины нечетной степени
for
if () mod
break
.push() // — стек
while not .empty()
.top()
found_edge = False
for
if () // нашли ребро, по которому ещё не прошли
.push() // добавили новую вершину в стек
.remove()
found_edge = True
break
if not found_edge
.pop() // не нашлось инцидентных вершине рёбер, по которым ещё не прошли
print()
Доказательство корректности[править]
| Лемма: |
Данный алгоритм проходит по каждому ребру, причем ровно один раз. |
| Доказательство: |
Допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно не пройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из стека , и он не мог стать пустым. Значит алгоритм пройдёт по всем рёбрам хотя бы один раз. Но так как после прохода по ребру оно удаляется, то пройти по нему дважды алгоритм не может. |
Вершина , с которой начат обход графа, будет последней помещена в путь . Так как изначально стек пуст, и вершина входит в стек первой, то после прохода по инцидентным ребрам, алгоритм возвращается к данной вершине, выводит ее и опустошает стек, затем выполнение программы завершается.
| Лемма: |
Напечатанный путь — корректный маршрут в графе, в котором каждые две соседние вершины и будут образовывать ребро . |
| Доказательство: |
Будем говорить, что ребро представлено в или , если в какой-то момент работы алгоритма вершины и находятся рядом. Каждое ребро графа представлено в . Рассмотрим случай, когда из в перемещена вершина , а следующей в лежит . Возможны 2 варианта:
Из этого следует, что мы закончим обход в вершине . Следовательно, данная вершина первой поместится в вслед за , и ребро будет представлено в . |
| Теорема: |
Данный алгоритм находит корректный эйлеров путь. |
| Доказательство: |
| Из предыдущих лемм следует, что — искомый эйлеров путь и алгоритм работает корректно. |
Рекурсивная реализация[править]
function findEulerPath( : Vertex):
for
remove
findEulerPath()
print()
Время работы[править]
Если реализовать поиск ребер инцидентных вершине и удаление ребер за , то алгоритм будет работать за .
Чтобы реализовать поиск за , для хранения графа следует использовать списки смежных вершин; для удаления достаточно добавить всем ребрам свойство бинарного типа.
См. также[править]
- Гамильтоновы графы
- Покрытие рёбер графа путями
- Произвольно вычерчиваемые из заданной вершины графы
Источники информации[править]
- Википедия — Эйлеров цикл
- Статья про нахождение Эйлерова пути с реализацией на С++ на сайте e-maxx.ru
- Статья про нахождение Эйлерова пути с реализацией на Pascal на сайте ивтб.рф
Источник
добавлено: 10 Jun 2008 22:14
редактировано: 10 Jun 2008 22:15
Эйлеров путь – это путь в графе, проходящий через все его рёбра. Эйлеров цикл – это эйлеров путь, являющийся циклом.
Задача заключается в том, чтобы найти эйлеров путь в неориентированном мультиграфе с петлями.
Алгоритм
Сначала проверим, существует ли эйлеров путь. Затем найдём все простые циклы и объединим их в один – это и будет эйлеровым циклом. Если граф таков, что эйлеров путь не является циклом, то, добавим недостающее ребро, найдём эйлеров цикл, потом удалим лишнее ребро.
Чтобы проверить, существует ли эйлеров путь, нужно воспользоваться следующей теоремой. Эйлеров цикл существует тогда и только тогда, когда степени всех вершин чётны. Эйлеров путь существует тогда и только тогда, когда количество вершин с нечётными степенями равно двум (или нулю, в случае существования эйлерова цикла).
Кроме того, конечно, граф должен быть достаточно связным (т.е. если удалить из него все изолированные вершины, то должен получиться связный граф).
Искать все циклы и объединять их будем одной рекурсивной процедурой:
procedure FindEulerPath (V)
1. перебрать все рёбра, выходящие из вершины V;
каждое такое ребро удаляем из графа, и
вызываем FindEulerPath из второго конца этого ребра;
2. добавляем вершину V в ответ.
Сложность этого алгоритма, очевидно, является линейной относительно числа рёбер.
Но этот же алгоритм мы можем записать в нерекурсивном варианте:
stack St;
в St кладём любую вершину (стартовая вершина);
пока St не пустой
пусть V – значение на вершине St;
если степень(V) = 0, то
добавляем V к ответу;
снимаем V с вершины St;
иначе
находим любое ребро, выходящее из V;
удаляем его из графа;
второй конец этого ребра кладём в St;
Несложно проверить эквивалентность этих двух форм алгоритма. Однако вторая форма, очевидно, быстрее работает, причём кода будет не больше.
Задача о домино
Приведём здесь классическую задачу на эйлеров цикл – задачу о домино.
Имеется N доминошек, как известно, на двух концах доминошки записано по одному числу (обычно от 1 до 6, но в нашем случае не важно). Требуется выложить все доминошки в ряд так, чтобы у любых двух соседних доминошек числа, записанные на их общей стороне, совпадали. Доминошки разрешается переворачивать.
Переформулируем задачу. Пусть числа, записанные на донимошках, – вершины графа, а доминошки – рёбра этого графа (каждая доминошка с числами (a,b) – это ребра (a,b) и (b,a)). Тогда наша задача сводится к задаче нахождения эйлерова пути в этом графе.
Реализация
Приведенная ниже программа ищет и выводит эйлеров цикл или путь в графе, или выводит -1, если его не существует.
Сначала программа проверяет степени вершин: если вершин с нечётной степенью нет, то в графе есть эйлеров цикл, если есть 2 вершины с нечётной степенью, то в графе есть только эйлеров путь (эйлерова цикла нет), если же таких вершин больше 2, то в графе нет ни эйлерова цикла, ни эйлерова пути. Чтобы найти эйлеров путь (не цикл), поступим таким образом: если V1 и V2 – это две вершины нечётной степени, то просто добавим ребро (V1,V2), в полученном графе найдём эйлеров цикл (он, очевидно, будет существовать), а затем удалим из ответа “фиктивное” ребро (V1,V2). Эйлеров цикл будем искать в точности так, как описано выше (нерекурсивной версией), и заодно по окончании этого алгоритма проверим, связный был граф или нет (если граф был не связный, то по окончании работы алгоритма в графе останутся некоторые рёбра, и в этом случае нам надо вывести -1). Наконец, программа учитывает, что в графе могут быть изолированные вершины.
int main() {
int n;
vector < vector<int> > g (n, vector<int> (n));
… чтение графа в матрицу смежности …
vector<int> deg (n);
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
deg[i] += g[i][j];
int first = 0;
while (!deg[first]) ++first;
int v1 = -1, v2 = -1;
bool bad = false;
for (int i=0; i<n; ++i)
if (deg[i] & 1)
if (v1 == -1)
v1 = i;
else if (v2 == -1)
v2 = i;
else
bad = true;
if (v1 != -1)
++g[v1][v2], ++g[v2][v1];
stack<int> st;
st.push (first);
vector<int> res;
while (!st.empty())
{
int v = st.top();
int i;
for (i=0; i<n; ++i)
if (g[v][i])
break;
if (i == n)
{
res.push_back (v);
st.pop();
}
else
{
–g[v][i];
–g[i][v];
st.push (i);
}
}
if (v1 != -1)
for (size_t i=0; i+1<res.size(); ++i)
if (res[i] == v1 && res[i+1] == v2 || res[i] == v2 && res[i+1] == v1)
{
vector<int> res2;
for (size_t j=i+1; j<res.size(); ++j)
res2.push_back (res[j]);
for (size_t j=1; j<=i; ++j)
res2.push_back (res[j]);
res = res2;
break;
}
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (g[i][j])
bad = true;
if (bad)
puts (“-1”);
else
for (size_t i=0; i<res.size(); ++i)
printf (“%d “, res[i]+1);
}
Источник
Задачи, послужившие основой теории графов
Задача о кенигсбергских мостах
Постановка задачи(Л. Эйлер, 1736 г.). На рис. 36.9, а) схематически изображена карта города Кенигсберга, относящаяся к XVIII в. Город был расположен на берегах и двух островах реки Преголи (Прегель). Острова между собой и берегами были связаны семью мостами. Можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту только один раз?
Так как при решении задачи интересны только переходы по мостам, то план города можно представить в виде полностью неориентированного мультиграфа (рис. 36.9, б)). Вершины и соответствуют правому и левому берегам реки, вершины и – островам; ребра мультиграфа – мостам. На языке графов задача формулируется следующим образом: существует ли в мультиграфе простой цикл, содержащий все ребра?
Определение 42. Простой цикл, содержащий все ребра графа, называют эйлеровым циклом (циклом Эйлера).
Замечание.Другими словами, эйлеров цикл проходит по каждому ребру ровно один раз.
Л. Эйлер сформулировал и доказал необходимое и достаточное условие того, чтобы в произвольном полностью неорентированном связном мультиграфе существовал эйлеров цикл.
Теорема 6. Эйлеров цикл в симметрическом связном мультиграфе существует тогда и только тогда, когда все его вершины являются четными.
Заметим, что в задаче о кенигсбергских мостах все вершины графа являются нечетными. Поэтому данная задача решения не имеет.
Определение 43. Граф, все вершины которого четны, называют эйлеровым графом.
Определение 44. Простой путь, содержащий все ребра графа, называют эйлеровым путем (путем Эйлера).
Теорема 7. У связного графа с двумя единственными нечетными вершинами существует эйлеров путь тогда и только тогда, когда этот путь начинается в одной из нечетных вершин и заканчивается в другой.
Задача о размещении экспозиции.Устроители больших художественных выставок часто вынуждены решать одну и ту же задачу: как организовать осмотр так, чтобы дать возможность в отведенное время ознакомиться с экспозицией наибольшему числу желающих. Для этого нужно расставить указатели таким образом, чтобы, перемещаясь в соответствии с предложенными в них рекомендациями, любой посетитель мог побывать у каждой картины ровно по одному разу. Возникает вопрос: можно ли найти общую методику организации осмотра выставки?
Если рассматривать стены и стенды, на которых размещены картины, как ребра, а точки поворотов как вершины, то помещение, в котором проводится выставка, будет представлять собой некоторый граф. Тогда задача об оптимальном размещении экспозиции сводится к построению на этом графе эйлерова цикла, если вход на экспозицию совпадает с выходом, и эйлерова пути, если вход и выход различны.
Алгоритм построения эйлерова цикла
1) Убедиться, что граф эйлеров.
2) Построить любой цикл. После построения возникают 2 возможности:
а) в цикл входят все ребра, и тогда задача решена;
б) на графе остались не пройденные ребра.
3) В построенном цикле найти вершину, из которой выходит еще не пройденное ребро (таких ребер должно быть четное число, если граф эйлеров).
4) Построить цикл из не пройденных ребер.
Алгоритм продолжать до тех пор, пока не будут пройдены все ребра.
Задача о коммивояжере
Постановка задачи(У.Р. Гамильтон). Район, который должен посетить бродячий торговец (коммивояжер), содержит некоторое количество городов, расстояния между которыми известны. Требуется найти маршрут, проходящий через все пункты по одному разу и возвращающийся в исходную точку. Если таких маршрутов несколько, то выбрать наиболее короткий из них.
Определение 45. Цепь, проходящую через каждую вершину полностью неориентированного графа ровно по одному разу, называют гамильтоновой цепью.
Определение 46. Цикл, проходящий через все вершины полностью неориентированного графа ровно одному разу через каждую (за исключением исходной, совпадающей с последней), называют гамильтоновым циклом.
Определение 47. Путь, проходящий через все вершины графа ровно по одному через каждую, называют гамильтоновым путем.
В терминах теории графов задача о коммивояжере равносильна задаче поиска на некотором полностью неориентированном графе элементарного гамильтонова цикла.
Задача поиска гамильтонова цикла является более сложной по сравнению с задачей поиска эйлерова цикла, так как, во-первых, пока не найдено достаточно общих теорем существования гамильтоновых циклов; во-вторых, пока не получено достаточно эффективных алгоритмов, позволяющих находить кратчайший путь, отличающихся по объему вычислений от простого перебора вариантов. Однако, доказано несколько утверждений, позволяющих определять наличие гамильтонова цикла у графа.
Теорема 8. Если степень каждой вершины графа , имеющего вершин, удовлетворяет соотношению , то граф имеет гамильтонов цикл.
Теорема 9. Всякий полный граф является гамильтоновым.
К задаче о построении гамильтонова цикла сводится задача о выборе маршрута кругосветного путешествия или экскурсии по достопримечательностям города.
Читайте также:
Рекомендуемые страницы:
©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-04-14
Нарушение авторских прав и Нарушение персональных данных
Источник