Today, we learned in university basics of Graphs. We learned about trees and aboout Greedy Algorithm to find minimal spanning tree of graph. I will visualize my question in this concrete graph.
By using Greedy Algorithm you can find different minimal spanning trees :
For example :
Minimal Spanning Tree 1
Minimal Spanning Tree 2
My question is about length of maximum path distance in both spanning trees:
$P_1 = \{42, 21, 10, 03, 36 , 65, 57\} $
$P_2 = \{42, 20, 03, 36, 65, 57\} $
$ |P_1| = 8 $
$ |P_2| = 7 $
Both of those examples are spanning tree but my intuition tells me , if there is shorter way from one end to another , that the graph is somehow superior, more optimalized. I don't know how to name this property so I'm asking, if there is any term, and what it is of this property of graph?
Thank you so much for answers
Best Answer
What you are asking for is the diameter of the minimal spanning tree. The diameter of a graph is the largest distance between any two points, which in your scenario of a tree, is the longest path.
It is uncertain what greedy algorithm you are using, but it appears you might be using Prim's algorithm which is always optimal for connected graphs so it might not make as much sense for the graph to be more superior, optimised, without defining what you meant by those words.