Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Nicolas Villanueva May 3 '11 at 10:16
    
@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$? –  Amir May 3 '11 at 11:48
    
@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 cs.berkeley.edu/~vazirani/s99cs170/notes/lec12.pdf on page 2. –  Nicolas Villanueva May 3 '11 at 11:58
    
@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? –  Amir May 3 '11 at 12:20
    
@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 direction –  Nicolas Villanueva May 3 '11 at 15:18
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.