Минимальный путь - все ребра хотя бы один раз

Question

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

Я искал какой-то алгоритм или какой-то теоретический фон, но единственное, что я нашел, - это китайский алгоритм почтальона. Но это решение не для ориентированного графа.

Кто-нибудь может мне помочь? Спасибо

Редактировать >> Все ребра этого графика имеют одинаковую стоимость - например, 1

Answer 1

Взгляните на эту статью - Направленная проблема китайского почтальона . Это правильная классификация проблем (при условии, что больше нет ограничений).

Если вы только читаете теорию, прочитайте на этой странице из Руководства по разработке алгоритмов.

Ключевая цитата (вторая половина для направленной версии):

Оптимальное путешествие почтальона можно построить, добавив соответствующие ребра в граф G, чтобы сделать его эйлеровым. В частности, мы находим кратчайший путь между каждой парой вершин нечетной степени в G. Добавление пути между двумя вершинами нечетной степени в G превращает их обе в четную степень, тем самым приближая нас к эйлерову графу. Поиск наилучшего набора кратчайших путей для добавления в G сводится к идентификации идеального соответствия минимального веса в графе на вершинах нечетной степени, где вес ребра (i, j) - это длина кратчайшего пути от i до к. Для ориентированных графов это может быть решено с помощью двустороннего сопоставления, где вершины разделены в зависимости от того, имеют ли они больше входящих или исходящих ребер. Как только график является эйлеровым, фактический цикл можно извлечь за линейное время, используя процедуру, описанную выше.

Answer 2

то, что вы ищете, называется «эйлеровым путем». Вы можете погуглить, чтобы найти достаточно информации, основы здесь А что касается алгоритма, то есть алгоритм, который называется алгоритм Флери, для него Google или посмотрите здесь

Answer 3

Особый случай, когда сеть полностью состоит из направленных ребер, может быть решен за полиномиальное время. Я думаю, что оригинальная статья Сопоставление, туры Эйлера и китайский почтальон (1973 г.) - четкое описание алгоритма задачи ориентированного графа начинается на стр. 115 (стр. 28 в pdf):

Когда все ребра связного графа направлены и граф симметричный, есть особенно простой и привлекательный алгоритм для указание тура Эйлера ...

Алгоритм нахождения обхода Эйлера в ориентированном симметричном связном графе G состоит в том, чтобы сначала найти остовную дугообразность G. Затем в любой узел n, кроме корня r древовидности, задает любой порядок для края направлены от n до тех пор, пока край древа последний в заказе. Для корня r укажите любой порядок для края направлены от r.

Этот алгоритм использовался ван Аарден-Эренфестом и де Брюином для перечислить все обходы Эйлера в некотором ориентированном графе [1].

Answer 4

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