1
$\begingroup$

I got this question, and I'd be happy for help.

G=(V,E). $G_S$ is a Strongly-Connected Components's Graph.

I need to prove, that if there is only one Component ($C_0$) which is not with incoming edge, that there is a DFS running in G that ruturn one tree, and only him.

I thought to start from the vertex with the lattest finish time in $C_0$. It works on my examples, but I dont know how to prove it, and if it is correct.

Thank you for your help.

  • 0
    Think of that Component as being the source of your graph. Also, think of each CC (Connected Component) as being it's own vertex in a graph.2011-05-03
  • 0
    @Nicolas Villanueva: Thank u, but I didn't understand What do you mean about thinking of each CC (Connected Component) as being it's own vertex in a graph? CC is composed from many vertex of the graph G. Do you talk about $G$ or G_s$?2011-05-03
  • 0
    @Amir Yes each individual CC is a set of vertices, but you can combine the vertices into 1 vertex. For example, look at Figure 2 of http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/lec12.pdf on page 2.2011-05-03
  • 0
    @Nicolas Villanueva: sorry, but I still don't understand how it helps me. The Graph $G_s$ is given, and I need to prove that there is DFS running on G. Now, How it helps me to combine all the vertex to CC in G? I need to prove for each CC that there is only one tree from DFS's scanning?2011-05-03
  • 0
    @Amir Yes. If you contract all CC's so they are represented by a single vertex, then only one of those contracted vertices will not have an in-deg = 0, this will be your source/starting vertex for DFS. I have finals in about an hour, but that should hopefully get you started in the correct direction2011-05-03
  • 0
    @Nicolas Villanueva: Which vertex in G will be my start point for the DFS? I need to prove that there is a DFS for G, and not for g_scc. I proved that if just one vertex in G is it with 0-degree then there is a DFS that return one tree. But that I saw that this don't help me. Thank u.2011-05-03
  • 0
    @Amir Pick a source in C_0 and start from there... It's not too hard to prove that if you have a tree in the contracted graph then you have a tree in the graph.2011-05-03
  • 0
    @Nicolas Villanueva: Can u give a clue how I prove that if I have a tree in a contracted graph then I have a tree in the graph. I tried everything: induction, contradiction..2011-05-04

0 Answers 0