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?

# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 203 |

2 | Errichto | 202 |

3 | rng_58 | 194 |

3 | SecondThread | 194 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

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?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/17/2021 01:09:32 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by venkycodes (previous revision, new revision, compare).` 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 `

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$$$.

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

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$$$.