Figure $2.$ The weighted undirected graph for Q$2.$

$1)$ Partition the graph into two sub$-$graphs so that the cut cost is minimum. Determine the sets of nodes belonging to the two subgraphs, respectively.

$(4$ marks$)$

$2)$ Determine the Laplacian matrix for the graph.

$(4$ marks$)$

$3)$ If the normalized graph cut $($Ncut$)$ method is used to partition this graph into two subgraphs, determine the sets of nodes belonging to the two subgraphs, respectively. $($Hint: You may use the Matlab function "eig" to solve the generalized eigenvalue decomposition problem after you determine the matrices $"\backslash (\backslash$boldsymbol$\{$L$\}\backslash )"$ and $"\backslash (\backslash$boldsymbol$\{$D$\}\backslash )"$ as specified in the lecture notes$).$

$(4$ marks$)$

$4)$ With the partition in Q$2-3),$ obtain the cut cost and the normalized cut value.

$(4$ marks$)$ Q$2$: Graph Cut $(16$ marks$)$

Figure $2$ shows a weighted undirected graph $\backslash ($ G$($V$,$ E$)\backslash )$ with the set of vertices denoted as $\backslash ($ V $\backslash )$ and the set of edges denoted as $\backslash ($ E $\backslash ).$ The weights of the edges are marked in the figure. Q$2$: Graph Cut $(16$ marks$)$

Figure $2$ shows a weighted undirected graph $\backslash ($ G$($V$,$ E$)\backslash )$ with the set of vertices denoted as $\backslash ($ V $\backslash )$ and the set of edges denoted as $\backslash ($ E $\backslash ).$ The weights of the edges are marked in the figure. Figure $2.$ The weighted undirected graph for Q$2.$

$1)$ Partition the graph into two sub$-$graphs so that the cut cost is minimum. Determine the sets of nodes belonging to the two subgraphs, respectively.

$(4$ marks$)$

$2)$ Determine the Laplacian matrix for the graph.

$(4$ marks$)$

$3)$ If the normalized graph cut $($Ncut$)$ method is used to partition this graph into two subgraphs, determine the sets of nodes belonging to the two subgraphs, respectively. $($Hint: You may use the Matlab function "eig" to solve the generalized eigenvalue decomposition problem after you determine the matrices $"\backslash (\backslash$boldsymbol$\{$L$\}\backslash )"$ and $"\backslash (\backslash$boldsymbol$\{$D$\}\backslash )"$ as specified in the lecture notes$).$

$(4$ marks$)$

$4)$ With the partition in Q$2-3),$ obtain the cut cost and the normalized cut value.

$(4$ marks$)$