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