0
$\begingroup$

My problem is as follow, imagine a complete undirected graph with weighted edges, i would like to extract a connected graph keeping all the vertices and where the edge with the highest weight is the minimum one compared to all others possible configurations.

Is there another solution than bruteforce it.

$\endgroup$
  • $\begingroup$ A minimum spanning tree minimize the sum of all edges and prevent cycles. I don't care about have cycles, i'm focused on the heaviest edge exclusively, not the sum of edges. Thank you $\endgroup$ – KyBe Nov 4 '17 at 16:24
  • $\begingroup$ Can you give an example of when a minimum spanning tree is not a solution? $\endgroup$ – theyaoster Nov 4 '17 at 16:42
  • $\begingroup$ @KyBe I know you don't require the connected subgraph to be a tree, but it wouldn't hurt you if it was. So the only question is whether an MST also has the property of minimizing the weight of the heaviest edge. And Ariel's answer seems to show that MSTs work. $\endgroup$ – David Richerby Nov 4 '17 at 22:34
3
$\begingroup$

Clearly you can focus on trees, since removing edges can only reduce the weight of the maximal edge. What you're looking for is called a minimum bottleneck spanning tree, and an MST is also a minimum bottleneck spanning tree.

To see why, suppose for the purpose of contradiction that $T$ is an MST which does not minmize the maximum weight. Let $(u,v)$ be the maximal weight edge in $T$, and $T'$ be a minimum bottleneck spanning tree. By our assumption $(u,v)\notin T'$, hence there exists a path from $u$ to $v$ in $T'$ which does not contain $(u,v)$, let us denote this path by $P$. Note that all the edges in $P$ are lighter than $(u,v)$. Remove $(u,v)$ from $T$, now $u,v$ are in different connected components. Suppose $P=(w_1=u,...,w_k=v)$, and denote by $i$ the minimal index such that $w_i$ and $w_{i+1}$ are in different connected components in $T\setminus\{(u,v)\}$. Now, $\left(T\setminus\{(u,v)\}\right)\cup\{(w_i,w_{i+1})\}$ is a spanning tree of $G$ with smaller weight, contradicting the fact that $T$ is an MST.

$\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.