0
$\begingroup$

Graph G has 4 vertices/nodes and 5 edges. It is also connected. Its edges have the following weights: 5, 8, 10, 16, 18.

The minimum length for a minimum spanning tree of graph G would be 5+8+10 which is 23.

But what would the maximum length for a minimum spanning tree of graph G be? and how would I go about calculating it?

$\endgroup$
  • $\begingroup$ If you know Kruskals algorithm for finding the minimum spanning tree then you can modify it to add maximal edges rather than minimal edges. $\endgroup$ – Ali Caglayan Jun 20 '16 at 16:25
0
$\begingroup$

I'll first consider the case with no parallel edges. Considering Kruskal's algorithm edges with weights 5 and 8 would be taken with any possible structure of the graph. Then if edges 5, 8 and 10 doesn't form a cycle Kruskal's algorithm will take edge with weight 10 and finish its work. Hence in optimal graph edges 5, 8 and 10 form a cycle. I'll denote the vertices of this cycle as $A$, $B$ and $C$. The fourth vertex will be denoted as $D$ Then edge of weight 16 have to connect $D$ with $A$ or $B$ or $C$ since parallel edges are not allowed. So, Kruskal's algorithm will take it and finish its work. The answer in that case is $5+8+16=29$

The case with parallel edges is more obvious. Kruskal's algirithm have to take edge with weight 5. Then graph with vertices $\{A,B,C,D\}$ and three edges between $A$ and $B$ with weights 5,8 and 10, edge between $B$ and $C$ with weight 16 and edge between $C$ and $D$ with weight 18 gives us maximal possible answer.

$\endgroup$
0
$\begingroup$

There are $\binom42=6$ potential edges between the vertices, so only one edge is missing, so the structure of $G$ is fully determined:

1-2
|\|
3-4

The minimal spanning tree uses the minimum of the weights incident at $2$, the minimum of the weights incident at $3$ and the minimum of the three remaining weights. Thus its length is maximised by putting $16$ and $18$ together, e.g. incident at $2$, leading to a maximal minimal spanning tree length of $5+8+16=29$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.