Is there a minimum spanning tree that does not contain the min/max weighted edge?_问答_开发者

If we have an (arbitrary) connected undirected graph G, whose edges have distinct weights,

does every MST of G contains the minimum weighted edge?
is there an MST of G that does not contain the开发者_C百科 maximum weighted edge?

Also, I'm more thankful if someone can give a hint of the key things one must keep in mind when dealing with such MST questions.

This is a homework problem. Thanks.

is there an MST of G that does not contain the maximum weighted edge?

There may be, but there doesn't have to be. Consider a 4-vertex graph as follows:

[A]--{2}--[B]
 |         |
 |         |
{1}       {3}
 |         |
 |         |
[C]-{50}--[D]

The minimum spanning tree consists of the edge set {CA, AB, BD}. The maximum edge weight is 50, along {CD}, but it's not part of the MST. But if G were already equal to its own MST, then obviously it would contain its own maximum edge.

does every MST of G contains the minimum weighted edge?

Yes. MSTs have a cut property. A cut is simply a partition of the vertices of the graph into two disjoint sets. For any cut you can make, if the weight of an edge in that cut is smaller than the weights of the other edges in the cut, then this edge belongs to all MSTs in the graph. Because you guaranteed that the edge weights are distinct, you have also guaranteed that there is an edge which is smaller than all other edges.

Also, I'm more thankful if someone can give a hint of the key things one must keep in mind when dealing with such MST questions.

Your best bet is to reason about things using the properties of MSTs in general, and to try to construct specific counterexamples which you think will prove your case. I gave an instance of each line of reasoning above. Because of the cut and cycle properties, you can always determine exactly which edges are in an MST, so you can systematically test each edge to determine whether or not it's in the MST.

Does every MST of G contains the minimum weighted edge?

Yes. Lets assume we have a MST which does not contain the min weight edge. Now the inclusion of this edge to the MST will result in a cycle. Now there will always be another edge in the cycle which can be removed to remove the cycle and still maintain the graph(MST) connected.

Is there an MST of G that does not contain the maximum weighted edge?

Depends on the graph. If the graph itself is a tree then we need to include all of its n-1 edges in the MST, so the max weight edge cannot be excluded. Also if the max weight edge is a cut-edge so that its exclusion will never result in connectivity, then the max weight edge cannot be excluded. But if the max weight edge is a part of a cycle then it is possible to exclude from the MST.

For your first question the answer is no, and kruskal's algorithm proves it. It will always select the minimum cost edge.

For the second question the answer is yes, and it's trivial to find an example graph:

1 - 2 (cost 10)
2 - 3 (cost 100)
3 - 1 (cost 1000)

The third edge will never be selected as it introduces a cycle. So basically, if the edge with the maximum cost would create a cycle if inserted in the MST, it won't be inserted.

I see you too are studying for CSC263 through the 2009 test? (Same here!)

Another way to see that the minimum is always in the MST is to look simply at this minimum edge (call it e):

          e 
v1 ---------------- v2

(Assume this has connections to other verticies). Now, for e NOT to be included in the final MST means at one point we have, without loss of generality, v1 in the MST but not v2. However, the only way to add v2 without adding e would be to say that the addition of v1 didn't add e to the queue (because by definition, e would be at the top of the queue because it has lowest priority) but this contradicts the MST construction theorem.

So essentially, it is impossible to have an edge with minimum weight not get to the queue which means that any MST constructed would have it.