Question $1$

$[30$ marks$]$

Determine the maximum flow of the network $\backslash ($ G $\backslash )$ in Figure $1-1,$

Figure $1-1$

$1($a$)$ Using the max$-$flow min$-$cut theorem, consider only the edges formed between vertices S$,$ A$,$ B$,$ C$,$ E$,$ F and G $(5$ marks$)$

$1($b$)$ Using $($i$)$ Folk$-$Fulkerson algorithm, and then $($ii$)$ Edmonds$-$Karp algorithm. $(20$ marks$)$

$1($c$)$ Suppose a network $\backslash ($ G$^\{\backslash$prime$\}\backslash )$ is an undirected graph with the same vertices and edges $($without directions$)$ as in $\backslash ($ G $\backslash ).$ Find the minimum spanning tree $($MST$)$ from the network $\backslash ($ G $\backslash )\text{'}$ with Kruskal's Algorithm. $(5$ marks$)$