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

Question

Может кто-нибудь сказать мне разницу между гамильтоновым путем и путем Эйлера. Они кажутся похожими!

Answer 1

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

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

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

На гамильтоновом пути вы не можете пройти через все ребра.

Answer 2

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

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

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

• Trail : прогулка, которая не повторяет никаких ребер.Все тропы являются прогулками.

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

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

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

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

Answer 3

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

Answer 4

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

---

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

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

Answer 5

Гамильтонов путь проходит по каждому узлу (или вершине) ровно один раз, а путь Эйлера проходит по каждому ребру ровно один раз.

Answer 6

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

Сборка de-novo

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

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

Answer 7

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

Answer 8

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

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