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

Why does the Eulerian Tour Algorithm actually work?
Автор desik, история, 8 лет назад, По-английски

I actually understood the method done in Euler Tour algorithm but don't understand why it works? Here is the pseudo.

dfs (v):
           for u in adj[v]:
               erase the edge v-u and dfs(u)
            push v at the end of e
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

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

Before running this algorithm, you need to check whether a Euler tour actually exists (even degree for all vertices in connected undirected graph). Suppose you start at node v. Then for ALL other nodes, since degree is even, if you can "enter" that node by some edge, you can most definitely "exit" it too. Because for every incoming edge, there is some outgoing edge (as degree is even). So, the only way for your algorithm to terminate is at vertex v, i.e. when you've exhausted every edge in the graph.

This is the most intuitive explanation for me. :)

→ Ответить