edited by
708 views

2 Answers

3 votes
3 votes

There is a very important theorem that can test whether an edge is in MST or not: Source: SO Link

 

An edge is not in any MST if and only if it is a unique heaviest edge in some cycle

$$\text{Edge not in MST} \Leftrightarrow \text{it is a unique heaviest edge in some cycle} $$

In other words,

$$\text{Edge in MST} \Leftrightarrow \text{it is NOT a unique heaviest edge in some cycle} $$

if $x$ is in MST then it can not be a UNIQUE and HEAVIEST edge in some cycle.

$x$ can not be greater than $110$ which means $x$ is lesser than equal to $110$.

Same goes to $y$ and $z$.

To be in MST, $x, y$, and $z$ can not be the largest weight in the cycle.
i.e.,

  • $x \leq 110$
  • $y \leq 60$
  • $z \leq 80$

Maximum value of $x+y+z=110+60+80=250$.

Answer:

Related questions

2 votes
2 votes
1 answer
2