Q1: Find the SCCs
C1 = {a,b,c,d,f,g} C2 ={e,h,j}
Q2: Find the component graph
VSCC ={C1,C2,C3,C4}
Copyright By PowCoder代写 加微信 powcoder
ESCC ={(C1,C2),(C2,C3),(C2,C4)}
Q3: Algorithm to compute a component graph
1. Compute SCCs and label all vertices u with their SCC Cu 2. Create a vertex for each SCC
3. For each vertex u:
For each outgoing edge (u,v):
If v belongs to different SCC then add an edge (Cu,Cv)
Q4: Complexity
Theorem: In DFS of a connected undirected graph G, we get only tree and back edges. No forward or cross edges.
Proof (no forward edges):
• Let (u, v) be a forward edge.
• Thus, v is a descendant of u but (u,v) is not a tree edge.
• By parenthesis theorem, d(u) < d(v) < f(v) < f(u).
• When (u,v) explored, v is?
- White? No because it would be a tree edge
- Black? No because (v,u)=(u,v) would already be labelled as a back edge
- Gray? No. DFS would explore all paths out of u before reaching and continue processing v ⇒ f(u) < f(v), which contradict the hypothesis v is a descendant of u
There are other ways to build your proof.
Theorem: In DFS of a connected undirected graph G, we get only tree and back edges. No forward or cross edges.
Proof (no cross edges):
• Let (u, v) be a cross edge.
• Thus, neither u or v is a descendant of the other.
• By parenthesis theorem, d(u) < f(u) < d(v) < f(v) or d(v) < f(v) < d(u) < f(u).
• Assume u is discovered first. At d(u), v is still white.
• Since v can be reached from u. v is a descendant of u by the
White path theorem. Not possible.
• Thus v is discovered first, and at d(u), v is still white.
• But u can be reached from v because G is undirected and there is an edge (u,v)=(v,u). By white path theorem, u is a descendant of v, which also contradict the hypothesis.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com