Различие между гамильтоновым путем и эйлеровым путем
Может кто-то говорить мне различие между гамильтоновым путем и эйлеровым путем. Они кажутся подобными!
4 ответа
Путь Эйлера - это путь, который пересекает каждое ребро ровно один раз без повторения, если он заканчивается в начальной вершине, то это цикл Эйлера.
Гамильтонов путь проходит через каждую вершину (обратите внимание не на каждое ребро) ровно один раз, если он заканчивается в начальной вершине, то это гамильтонов цикл.
В пути Эйлера вы можете пройти через вершину более одного раза.
В гамильтоновом пути вы не можете пройти через все ребра.
Эйлеров путь должен посещать каждое ребро ровно один раз, а гамильтонов путь должен посещать каждую вершину ровно один раз.
Гамильтонов путь посещает каждый узел (или вершину) ровно один раз, а эйлеров путь проходит каждое ребро ровно один раз.
Они связаны, но не являются ни зависимыми, ни взаимоисключающими. Если граф имеет эйлеров цикл, он может иметь или не иметь также гамильтонов цикл, и наоборот.
Циклы Эйлера посещают каждое ребро в графе ровно один раз. Если в графе есть вершины с более чем двумя ребрами, то по определению цикл будет проходить через эти вершины более одного раза. В результате вершины могут повторяться, а ребра - нет.
Гамильтоновы циклы посещают каждую вершину в графе ровно один раз (аналогично задаче о путешествующем продавце). В результате ни ребра, ни вершины не могут повторяться.