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 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

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

1 | Errichto | 194 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 176 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

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-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2020 01:51:55 (h1).

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