World's most popular travel blog for travel bloggers.

[Solved]: Can the heaviest edge ever be in an MST?

, , No Comments
Problem Detail: 

Is it true that the heaviest edge in a directed graph can not be in the MST of that graph?

I don't think it is true because we might end up with a heaviest edge that is not part of a cycle.

Can anyone confirm?

Asked By : 372

Answered By : Juho

No, it is not true. Consider a graph with 2 vertices and an edge between them. This is the heaviest edge, and it will be in the minimum spanning tree of $G$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11902

0 comments:

Post a Comment

Let us know your responses and feedback