Разница между гамильтоновским путем и эйлеровым путем

Ответ 1

Путь Эйлера - это путь, который пересекает каждое ребро ровно один раз, не повторяя, если он заканчивается в начальной вершине, то это цикл Эйлера.

A Гамильтонова траектория проходит через каждую вершину (обратите внимание не на каждое ребро) ровно один раз, если она заканчивается в начальной вершине, то это гамильтонов цикл.

В пути Эйлера вы можете проходить через вершину более одного раза.

В гамильтоновском пути вы не можете проходить через все ребра.

Ответ 2

Эйлеровский путь должен посещать каждый край ровно один раз, а гамильтоновский путь должен посещать каждую вершину ровно один раз.

Ответ 3

Определения теории графов

(В порядке убывания общности)

• Прогулка: последовательность ребер, где конец одного края отмечает начало следующего ребра

• Трейл: прогулка, которая не повторяет никаких ребер. Все тропы - это прогулки.

• Путь: прогулка, где каждая вершина проходит ровно один раз. (пути, используемые для обозначения открытых прогулок, определение теперь изменилось). Свойство пересечения вершин только один раз означает, что ребра также пересекаются только один раз, поэтому все пути являются трассами.

Гамильтоновы пути и эйлеровы траектории

• Гамильтонов путь: посещает каждую вершину в графе (ровно один раз, потому что это путь)

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

Ответ 4

Гамильтоновский путь посещает каждый node (или вершину) ровно один раз, а эйлеровский путь пересекает каждое ребро ровно один раз.

Ответ 5

Они связаны друг с другом, но не являются ни зависимыми, ни взаимоисключающими. Если граф имеет цикл Eurler, он может иметь или не иметь гамильтонианский кайл и наоборот.

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

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

Ответ 6

Я буду использовать общий пример в биологии; восстановление генома путем создания образцов ДНК.

Установка De-novo

Чтобы построить геном из коротких чтений, необходимо построить график этих чтений. Мы делаем это, разбивая чтения на k-mers и собираем их в график.

Мы можем восстановить геном, посетив каждый node один раз, как на диаграмме. Это называется гамильтоновским путем.

К сожалению, построение такого пути NP-hard. Невозможно получить эффективный алгоритм его решения. Вместо этого в биоинформатике мы строим эйлеровский цикл, где ребро представляет собой перекрытие.

Ответ 7

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

Ответ 8

Путь Эйлера - это граф, использующий каждое ребро (ПРИМЕЧАНИЕ) графа ровно один раз. Схема Эйлера представляет собой траекторию эйлеров, которая возвращает ей начальную точку после покрытия всех ребер.

В то время как путь Гамильтона - это граф, который охватывает всю вершину (ПРИМЕЧАНИЕ) ровно один раз. Когда этот путь возвращается к исходной точке, этот путь называется схемой гамильтона.