Блог пользователя hiddentesla

Автор hiddentesla, история, 8 лет назад, По-английски

so im learning Euler circuit now, and i found this algorithm

'tour' is a stack

find_tour(u):
	for each edge e=(u,v) in E:
		remove e from E
		find_tour(v)
	prepend u to tour

to find the tour, clear stack 'tour' and call find_tour(u),
where u is any vertex with a non-zero degree.

source: http://www.algorithmist.com/index.php/Euler_tour

i coded it, and got AC in an euler circuit problem (the problem guarantees that there is an euler circuit) however, i noticed that in the bottom of the algorithm, it says [WARNING! There is some error in this pseudo-code. The algorithm is not correct!]

does this mean that the algo has a high chance to print euler circuit? or something else?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

I think this is Hierholzer's algorithm. Before applying it, you need to check that a Euler circuit actually exists for the given graph. Here is another good resource. Take a look at this problem which asks you to construct a Eulerian circuit. My code for the same can be found here.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Perhaps it is meant that it is advisable to consider loops separately

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

i was really confused on how this is equivalent to Hierholzer's algorithm, as the pseudo-code you wrote looks nothing like that at all. This is also the code present in CP algorithms. So I came up with a proof:

Proof that this algorithm is equivalent to Hierholzer's:

Claim: For an Eulerian graph [graph which is connected and each vertex has even degree] of size $$$n$$$, $$$findTour(v)$$$ outputs a euler tour starting and ending at any arbitrary vertex $$$v$$$.

We can prove this claim by strong induction on $$$n$$$. Consider for a graph of size $$$k$$$. Let's start $$$findTour(v)$$$ on any arbitrary vertex $$$v$$$. Since each vertex has even number of edges, we will never get "stuck" on any vertex, since once we enter a vertex, we can exit it also. Consider when the recursion comes back to $$$v$$$ for the first time. It has deleted all edges from the graph which forms a simple cycle consisting $$$v$$$.

This means that the graph is now divided into smaller Eulerian graphs, with each vertex of the cycle being part of one such smaller eulerian graph. By induction, $$$findTour()$$$ on these vertices returns an eulerian circuit starting and ending at these vertices. So we combine the path in the stack, thus finding the euler tour.