venkycodes's blog

What is size of euler walk of a tree with n vertices?
By venkycodes, history, 7 years ago, In English

Hi. I was wondering if there is any upperbound to the size of euler walk with respect to number of vertices. If yes then what will be that maximizing condition?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by venkycodes (previous revision, new revision, compare).

→ Reply
»
7 years ago, hide # |
← Rev. 3  
Vote: I like it +3 Vote: I do not like it

` the number of times any node will be added to the euler walk is equal to number of its children every tree + 1 for non leaf nodes and 2 times for leaves (for upper bound we can assume that number of times a node occurs in a euler walk is equal to Nc + 2 where NcI is the number of children of a node I) for each node we can safely assume that every child gives it a single contribution and it has 2 contribution from itself in its frequency in euler path

now every node will be child of exactly one node except root (neglect it for now ) and this will contribute one frequency of its parent so total N(number of nodes in tree ) will be added to the euler vector size, and for each node 2 will be added as per above analysis hence at most 2*N will be added to the euler vector so total euler vector size should not increase 3*N

hope it is correct tell me if I am wrong somewhere `

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

If by "euler walk" you're referring to the Eulerian path/cycle in a general graph, then the length of that is exactly the number of edges in the graph. If you're talking about the Euler tour of a tree, then the number of vertices in the tour is exactly $$$2|V|-1$$$.

→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it +6 Vote: I do not like it

    can you tell me how it would be exactly 2v-1 ?

    → Reply
    • »
      »
      »
      7 years ago, hide # ^ |
       
      Vote: I like it +6 Vote: I do not like it

      There are $$$|V|-1$$$ edges, and we traverse each of them twice. Once going down, and once going back up. So that's a total of $$$2|V|-2$$$ edge traversals. We start out with the root vertex and each time we traverse an edge we add a new vertex, so total is $$$2|V|-1$$$.

      → Reply