determinism's blog

By determinism, 9 years ago, In English

In the solution of tutorial of this problem, levels are represented by vertices and transfers are represented by edges. Graph also has a start vertex. It says that the result is a minimum spanning tree of the graph. I couldn't understand why the answer is a minimum spanning tree. Can't a vertex of a minimum spanning tree have more than one adjacent vertex which is impossible for a tree to be the result? Can someone explain where I'm wrong?

Tags mst
  • Vote: I like it
  • -1
  • Vote: I do not like it

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

Consider a directed graph. Edge (A -> B) means that you use level A as a base, or send level B entirely if A == 0. There are obviously no cycles, and each vertex but 0 has exactly one edge that enters it. So this graph is always a tree as you can see.

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I understood that the result is a tree. What I could't understand was how a minimal spanning tree always fulfils the requirement that for each vertex you can only go to one vertex. For instance, minimum spanning tree could have every edge from vertex 0 to others.

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

      Well I don't really understand what you mean. If you go by dfs(0), all conditions will take place