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

Posted by Martin on Stack Overflow See other posts from Stack Overflow or by Martin
Published on 2010-04-11T12:31:05Z Indexed on 2010/04/11 12:33 UTC
Read the original article Hit count: 362

Filed under:

minimum-spanning-tree

|

mst

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 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.

Thanks

© Stack Overflow or respective owner

Related posts about minimum-spanning-tree

Updating a Minimum spanning tree when a new edge is inserted

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I've been presented the following problem in University: Let G = (V, E) be an (undirected) graph with costs ce = 0 on the edges e € E. Assume you are given a minimum-cost spanning tree T in G. Now assume that a new edge is added to G, connecting two nodes v, tv € V with cost c. a) Give an… >>> More
A minimum spanning tree / shortest path in a directed graph

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a directed graph with weighted edges, what algorithm can be used to give a sub-graph that has minimum weight, but allows movement from any vertex to any other vertex in the graph (under the assumption that paths between any two vertices always exist). Does such an algorithm exist? >>> More
A two way minimum spanning tree of a directed graph

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a directed graph with weighted edges, what algorithm can be used to give a sub-graph that has minimum weight, but allows movement from any vertex to any other vertex in the graph (under the assumption that paths between any two vertices always exist). Does such an algorithm exist? >>> More
Minimum spanning tree [closed]

as seen on Stack Overflow - Search for 'Stack Overflow'
Iam having difficulty in implementing a minimum spanning tree. So please can someone please post a link to it's source code. >>> More
Is there a minimum spanning tree that does not contain the min/max weighted edge?

as seen on Stack Overflow - Search for 'Stack Overflow'
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 maximum weighted edge? Also, I'm more thankful if someone can give a hint of the key things one must… >>> More

Related posts about mst

Prim's MST algorithm implementation with Java

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to write a program that'll find the MST of a given undirected weighted graph with Kruskal's and Prim's algorithms. I've successfully implemented Kruskal's algorithm in the program, but I'm having trouble with Prim's. To be more precise, I can't figure out how to actually build the Prim… >>> More
What is the easier way to edit .MST video on Mac

as seen on Super User - Search for 'Super User'
I couldn't find any easy way to edit .MST file from the Canon camera. Do I need to convert it before editing or is there a software that can automatically import .MST files and edit it. >>> More
Is there a minimum spanning tree that does not contain the min/max weighted edge?

as seen on Stack Overflow - Search for 'Stack Overflow'
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 maximum weighted edge? Also, I'm more thankful if someone can give a hint of the key things one must… >>> More
How to create an MST for silent install using Orca?

as seen on Server Fault - Search for 'Server Fault'
Hi. I'm trying to deploy 7zip via GPO; I assigned the original MSI, but the package installation simply doesn't take place. What I've gathered is that I need to create an MST. In the spirit of trying to learn as much as possible about it, I've opted to use Orca rather than a third-party automagic… >>> More
Second min cost spanning tree.

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello. I'm writing an algorithm for finding the second min cost spanning tree. my idea was as follows: 1) Use kruskals to find lowest MST. 2) Delete the lowest cost edge of the MST. 3) Run kruskals again on the entire graph. 4) return the new MST. My question is this: Will this work? Is there… >>> More