Consider the so$-$called $k-$Minimum Spanning Tree $(k-$MST$)$ problem, which is defined as follows.

An instance of the $k-$MST problem is given by a connected undirected graph $G=(V,E)$ with edge weights $w$:$EQ$ and a natural number $k2.$ The question is to find a tree with exactly $k$ nodes that is a subgraph of $G$ and minimises the weight among all such trees. Informally, $k-$MST is the variant of the minimum spanning tree problem, where instead of a spanning tree one wants to find a tree with exactly $k$ nodes.

What would be the result if we apply Prim's, respectively Kruskal's, algorithm to the problem by stopping both algorithms after $k-1$ edges have been added? In the following we refer to these versions of Prim's and Kruskal's algorithm as the modified algorithm of Prime or Kruskal, respectively.

Q$3\mathrm{.}1$ Modified algorithm of Kruskal

$5$ Points

Consider the following graph.

For which of the following edge weights, assigned to the graph above, does the modified algorithm of Kruskal provide a wrong result assuming that $k=4$ hick all answers for which this is the case.

$w(1,2)=4,w(2,3)=6,w(3,4)=5,w(4,5)=4$

$w(1,2)=6,w(2,3)=2,w(3,4)=3,w(4,5)=5$

$w(1,2)=2,w(2,3)=1,w(3,4)=3,w(4,5)=2$

$w(1,2)=1,w(2,3)=2,w(3,4)=3,w(4,5)=4$

Here, $w(a,b)=d$ means that the edge between vertices a and $b$ has weight $d.$

onsider the tollowing graph.

For which of the following edge weights, assigned to the graph above, and starting vertex $1$ does the modified algorithm of Prim provide a wrong result assuming that $k=4.$ Tick all correct answers.

$w(1,2)=4,w(2,3)=1w(3,4)=2,w(4,5)=3,w(1,5)=2$

$w(1,2)=3,w(2,3)=2,w(3,4)=2,w(4,5)=2,w(1,5)=2$

$w(1,2)=4,w(2,3)=5,w(3,4)=1,w(4,5)=1,w(1,5)=3$

$w(1,2)=3,w(2,3)=5,w(3,4)=1,w(4,5)=1,w(1,5)=4$

Here, $w(a,b)=d$ means that the edge between vertices a and $b$ has weight $d$ and $s=$a means that the start vertex for the modified alqorithm of Prim is set to the vertex $a.$