Is there a minimal spanning tree that does not contain a weighted min / max edge?

Question

If we have a (arbitrary) connected undirected graph G whose edges have different weights,

• does each MST of G contain a minimum weighted edge?
• Is there an MST from G that does not contain a maximum weighted edge?

In addition, I am more grateful if someone can give a hint of the key things to keep in mind when dealing with such MST issues.

This is a domestic problem. Thanks.

Answer 1

is there an MST from G that does not contain a maximum weighted edge?

Maybe, but not necessary. Consider a 4-vertex graph as follows:

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

A minimal spanning tree consists of a set of edges {CA, AB, BD}. The maximum edge weight is 50, {CD}, but it is not part of the MST. But if G was already equal to its own MST, then, obviously, it will contain its own maximum edge.

each MST of group G contains a minimum weighted edge

Yes. MST has a slice property. A cut is simply a partition of the vertices of a graph into two disjoint sets. For any section, you can do it if the weight of the edge in this section is less than the weight of other edges in the section, then this edge belongs to all MSTs in the graph. Since you guaranteed that the weights of the edges are different, you also guaranteed that there is an edge that is smaller than all the other edges.

In addition, I am more grateful if someone can give a hint of the key things to keep in mind when dealing with such MST issues.

It’s best to talk about things using the properties of MST in general, and try to build specific counterexamples that, in your opinion, will confirm your case. I gave an example of each line of reasoning above. Due to the properties of the cut and the loop, you can always determine exactly which edges are in the MST, so you can systematically test each edge to determine if it is in the MST.

Answer 2

Does every MST from G contain a minimally weighted edge?

Yes. Suppose we have an MST that does not contain a minimum weight edge. Now, including this edge in MST will lead to a cycle . Now there will always be another edge in the cycle that can be removed to remove the cycle and still maintain the schedule ( MST ) connected.

Is there an MST from G that does not contain a maximum weighted edge?

Depends on the schedule. If graph itself is a tree, then we must include all its n-1 edges in the MST , so that the maximum edge weight cannot be excluded. In addition, if the maximum weight of the edge is cut-edge so that its exclusion will never lead to bonds, then the maximum weight of the edge cannot be excluded. But if the maximum edge weight is part of a cycle , then it can be excluded from the MST .

Answer 3

There is no answer for your first question, and Kruskal's algorithm proves. He will always choose the lowest price.

For the second question, the answer is yes, and it is 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 loop. Therefore, basically, if the edge with the maximum cost creates a cycle, if it is inserted in the MST, it will not be inserted.

Answer 4

I see that you also study at CSC263 through the 2009 test? (Same thing here!)

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

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

(Assume this has connections with other vertices). Now, in order to NOT be included in the final MST, at some point we have, without loss of generality, v1 in MST, but not v2. However, the only way to add v2 without adding e would be to say that adding v1 did not add e to the queue (because by definition e will be at the top of the queue because it has the lowest priority), but this contradicts the MST construction theorem.

Thus, it is essentially impossible that the edge with the minimum weight does not get in the queue, which means that any MST built would have this.