程序代写 Q1: Find the SCCs

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