SGT Sheet

Question 1

1. Use Identify Strongly Component Components (Algorithm):
   1. Begin by doing Topological Sort (Algorithm) Visit $E$, visit $H$. Backtrack, $L=\{E,H\}$. Visit $M$, $G$, $L$, $I$, $Q$, $P$, $O$, $B$, $N$, $D$. Backtrack, $L=\{M,G,L,I,Q,P,O,B,N,D,E,H\}$. Visit $C$, $A$, $F$. Backtrack. $L=\{C,A,F,M,G,L,I,Q,P,O,B,N,D,E,H\}$.
   2. For each element in $L$, perform DFS on transpose of the graph, add all visited to new component. Visit $C,F,A$. ($S_1$) Visit $M$ ($S_2$) Visit $G,L,I$ ($S_3$) Visit $B,O,P,Q,D,N$. ($S_4$) Visit $E,H$. ($S_5$) Each set $S_n$ described above must have all of its tasks done concurrently.
2. Draw the component graph $G^{SCC}$.

digraph {
	rankdir=LR
	S1->S2,S4
	S2->S3,S4,S5
	S3->S4
 
	S1 [label="A,C,F"]
	S2 [label="M"]
	S3 [label="G,I,L"]
	S4 [label="B,O,P,Q,D,N,K"]
	S5 [label="E,H"]
}

3. Topological sort would output $\{S_1,S_2,S_5,S_3,S_4\}$.
4. N/A

Question 2

1. Apply algorithm to the graph: Split into subgraphs containing:
   • $A,B,H,I,G$ Split into:
     • $A,B$: base case
     • $H,I,G$: which splits into: $H,I$: base case $G$: base case They combine on the edge $(G,H)$. They combine on the edge $(A,H)$.
   • $C,D,F,E$ Split into:
     • $C,D$: base case
     • $F,E$: base case They combine on the edge $(C,F)$. They combine on the edge $(C,I)$. Hence the final MST by this algorithm is found by combining the set of base cases with the set of lightest edges: $(A,B),(H,I),(G,H),(A,H),(C,D),(F,E),(C,F),(C,I)$
2. Yes, if and only if the whole graph is connected.
3. No. During the division stage we select two subgraphs at complete random not taking into consideration the weight of the edges between the nodes selected in the subgraphs. (This matters when we are down to 3-4 nodes as the resulting division causes nodes to link together.)