Нахождение пути всех ребер на графе

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

Итак, в простом случае ниже мне нужно пройти по узлам в таком порядке 1-2-3-4-5 (или 5-4-3-2-1):

простой

В более сложном случае ниже путь будет 1-2-3-4-2 (или 1-2-4-3-2):

--график

Ниже также приведен допустимый график с двумя конечными точками: 1-2-4-3-2-5.

комплекс

Я попытался найти название алгоритма для решения этой проблемы и подумал, что это «проблема китайского почтальона», но реализовал это на основе кода на https://github.com/rkistner/chinese-postman/blob/master/postman.py не дал ожидаемых результатов. .

Путь Эйлера выглядит почти так, как нужно, но реализация networkx будет работать только для закрытых (петлевых) сетей.

Я также просмотрел гамильтоновский путь и попробовал алгоритм networkx, но типы графиков не поддерживались.

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


python algorithm networkx graph-theory
person geographika    schedule 10.03.2017    source источник
comment
Гамильтонов путь покрывает все вершины, вы можете проверить Эйлеров путь, который вместо этого покрывает ребра. Кажется, у GeeksForGeeks есть пример реализации для Python.   -  person niemmi    schedule 10.03.2017
comment
@niemmi - спасибо! Похоже, термин Эйлера (а не цепь) — это термин, который я ищу. Я рассмотрю алгоритм и посмотрю, можно ли его упростить, используя существующие методы networkx.   -  person geographika    schedule 10.03.2017
comment
@niemmi Ваше право, вы также можете превратить это в ответ, добавив соответствующие ссылки ..   -  person Abhishek Jebaraj    schedule 10.03.2017
comment
Это называется Эйлеровым путем графа. Теперь он добавлен в networkx как eulerian_path()< /а>.   -  person iacob    schedule 08.04.2021

Ответы (2)


arrow_upward
3
arrow_downward

Вы ищете путь Эйлера, который посещает каждое ребро ровно один раз. Вы можете использовать алгоритм Флери для создания пути. Алгоритм Флери имеет временную сложность O(E^2), если вам нужен более эффективный алгоритм, проверьте алгоритм Хиерхольцера, который вместо этого равен O(E).

Существует также неслитный запрос на вытягивание для библиотеки networkx, которая это реализует. источник прост в использовании.

(Для networkx 1.11 .edge необходимо заменить на .edge_iter).

person niemmi    schedule 10.03.2017
comment
Как только я был уверен в названии типа пути, который искал, я мог найти реализацию в networkx. - person geographika; 10.03.2017
comment
Примечание. указанный запрос на включение был закрыт, поскольку возникла фундаментальная проблема. с реализацией в нем алгоритма поиска пути. - person iacob; 21.04.2019

arrow_upward
0
arrow_downward

Это называется Эйлеровым путем графа. Теперь он добавлен в NetworkX как eulerian_path()< /а>.

person iacob    schedule 26.03.2021