hell_hacker's blog

Help with star graph !
By hell_hacker, history, 9 years ago, In English

In this question http://mirror.codeforces.com/contest/330/problem/B I want to ask why the star graph would give minimum number of paths. Thank You.

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

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

You want to use minimal amount of edges, so we are going to build a tree, because it is the smallest possible connected graph. The longest possible path in any tree is given by the tree diameter. The diameter is twice the distance from the center of the tree to the farthest vertex from the center. In the star graph, the center is 1 edge away from every other vertex, so the diameter and thus the longest path length is clearly 2 edges.

→ Reply