Разница между гамильтоновым и эйлеровым путями
Может кто-нибудь сказать мне разницу между гамильтоновым путем и путем Эйлера. Они кажутся похожими!
8 ответов
Путь Эйлера - это путь, который пересекает каждое ребро ровно один раз без повторения, если он заканчивается в начальной вершине, то это цикл Эйлера.
Путь гамильтониана проходит через каждую вершину (не каждое ребро), ровно один раз, если он заканчивается в начальной вершине, то это гамильтонов цикл.
На пути Эйлера вы можете проходить через вершину более одного раза.
На гамильтоновом пути вы не можете пройти через все ребра.
Определения теории графов
(В порядке убывания общности)
Ходьба: последовательность ребер, где конец одного ребра отмечает начало следующего ребра
Тропа: прогулка, которая не повторяет никаких краев. Все тропы являются прогулками.
Путь: прогулка, где каждая вершина пройдена ровно один раз. (пути, используемые для обозначения открытых прогулок, определение теперь изменилось) Свойство обхода вершин только один раз означает, что ребра также пересекаются только один раз, следовательно, все пути являются следами.
Гамильтоновы тропы и эйлеровы тропы
Гамильтонов путь: посещает каждую вершину графа (ровно один раз, потому что это путь)
Эйлерова тропа: посещает каждое ребро графа ровно один раз (поскольку это тропа, вершины могут пересекаться не раз).
Путь Эйлера должен посещать каждое ребро ровно один раз, а путь Гамильтона должен посещать каждую вершину ровно один раз.
Я буду использовать общий пример в биологии; реконструкция генома путем создания образцов ДНК.
Сборка de-novo
Чтобы построить геном из коротких чтений, необходимо построить график этих чтений. Мы делаем это, разбивая чтения в k-мерс и собирая их в график.
Мы можем восстановить геном, посетив каждый узел один раз, как на диаграмме. Это известно как гамильтонов путь.
К сожалению, построить такой путь непросто. Невозможно получить эффективный алгоритм для его решения. Вместо этого в биоинформатике мы строим эйлеров цикл, где ребро представляет собой перекрытие.
Они связаны, но не являются ни зависимыми, ни взаимоисключающими. Если у графа есть цикл Эрлера, он может иметь или не иметь также гамильтоновы cyle и наоборот.
Циклы Эйлера посещают каждое ребро графа ровно один раз. Если в графе есть вершины с более чем двумя ребрами, то по определению цикл будет проходить через эти вершины более одного раза. В результате вершины могут повторяться, а ребра - нет.
Гамильтоновы циклы посещают каждую вершину графа ровно один раз (аналогично задаче коммивояжера). В результате ни ребра, ни вершины не могут повторяться.
Путь Эйлера - Путь Эйлера - это путь, в котором каждое ребро проходит ровно один раз.
Гамильтонов путь. Гамильтонов путь - это путь, по которому каждая вершина проходит ровно один раз.
Если вы когда-нибудь запутались, вспомните E - Euler E - Edge.
Путь гамильтониана посещает каждый узел (или вершину) ровно один раз, а путь Эйлера проходит каждый край ровно один раз.
Путь Эйлера - это путь, который использует каждое ребро графа ровно один раз, и он должен иметь ровно две нечетные вершины. Путь начинается и заканчивается в другой вершине. Гамильтонов цикл - это цикл, который содержит каждую вершину графа, поэтому вы не можете использовать все ребра графа.
Путь Эйлера - это граф, использующий каждое ребро (ПРИМЕЧАНИЕ) графа ровно один раз. Эйлерова схема - это эйлерова траектория, которая возвращается к начальной точке после покрытия всех ребер.
В то время как путь Гамильтона - это граф, который охватывает все вершины (ПРИМЕЧАНИЕ) ровно один раз. Когда этот путь возвращается в начальную точку, этот путь называется гамильтоновым контуром.