![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
|
My textbook (Discrete Mathematics and Its Applications) doesn't say anything about the supplied graph has to be either directed or undirected - just that it has to be a weighted, connected graph. However, this article states it has to be undirected. Why is that so? A directed, weighted graph will only limit the possible number of forests. Thanks. Anders Sørensen
"A minimum spanning tree is in fact the minimum-cost subgraph connecting all vertices, since subgraphs containing cycles necessarily have more total weight."
Correct me if I'm wrong, but this is not true for a graph with negative weights - for example, in a complete graph with all weights equal -1, every spanning tree is a minimum spanning tree, but the minimum-cost subgraph connecting all vertices is the complete graph itself.
trees are good —Preceding unsigned comment added by 69.124.89.74 ( talk) 22:26, 5 December 2007 (UTC)
Someone thinks this article is or was missing citations. In the current state I disagree. I do also miss any explanation here, which I would expect accompanying with a tag so dominantly placed on an article. Therefore, I have decided to remove the tag. KKoolstra ( talk) 10:01, 9 April 2009 (UTC)
It seems to me that there is a mistake in the proof given under "Uniqueness". In the last line where it says "If the weight of e1 is larger than that of e2, a similar argument involving tree {e2} A - {e1} also leads to a contradiction. Thus, we conclude that the assumption that there can be a second MST was false.", it assumes that {e2} A - {e1} is a spanning tree. This is not necessarily the case because it could be that the cycle C contains several edges which are in B but not in A. This means that attaching the edge e2 to A and subtracting e1 does not necessarily create a cycle. — Preceding unsigned comment added by 70.112.206.154 ( talk) 23:21, 9 March 2012 (UTC)
I agree with that. But also there is a mistake. Attaching the edge e2 to A surely creates a cycle, however, this cycle does not necessarily contains e1. So {e2} A - {e1} may not be a spanning tree. The original proof in the reference is correct. The e1 is not picked casually. It's the minimum weight edge which is in one but not both MST. So the weight of e1 is lower than that of e2 definitely, and the original proof needs to be revised.
I don't know if this section is out-of-date and all the corrections have been made, but the proof in its current form looks logically correct to me. One thing I'd change though is in the fourth step, just reorganizing the points to make it easier to grasp:
I would change it to say:
Jeffxtreme ( talk) 13:49, 1 October 2014 (UTC)
A diagram's text states "T is the only MST of the given graph", but the given graph actually has 2 MSTs. This could be fixed by changing the weight of EC to be at least 5. — Preceding unsigned comment added by 2620:4F:0:101:15A4:738E:AB92:D953 ( talk) 00:40, 9 January 2014 (UTC)
The figure showing the Cut Property has as its first sentence "This figure shows the cut property of MSP." Should MSP be changed to MST? I cannot find a definition for MSP on this page. Rellims2012 ( talk) 14:19, 17 March 2015 (UTC)
Can anybody knowing this stuff take a look at random minimal spanning tree? I find that one not so clear. Thanks. Oleg Alexandrov 03:23, 25 Jun 2005 (UTC)
Does anyone know how to solve the problem for directed graphs? Ali Hassan — Preceding unsigned comment added by 39.42.63.81 ( talk) 14:50, 11 September 2016 (UTC)
I believe there are Russian articles with Tarjan's criterion:
Wumbolo ( talk) 22:09, 6 August 2017 (UTC)
Hello fellow Wikipedians,
I have just modified one external link on Minimum spanning tree. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 02:25, 1 February 2018 (UTC)
It will be helpful to include the general Selection-Rejection rules from Ottman, Widmayer -- Algorithmen und Datastrukturen (pg.576). They can be used for proving Kruskal's algorithm, Jarnik's algorithm, Boruvka's algorithm. Cheater no1 ( talk) 10:55, 1 August 2019 (UTC)
Why on Earth does the diagram showing the cut remove some, but not all, of the edges? That's very odd. Doesn't really hurt anything other than adding to confusion. Hobit ( talk) 15:04, 3 February 2021 (UTC)
![]() | This edit request by an editor with a conflict of interest was declined. A reviewer felt that this edit would not improve the article. |
Fallin et al. (2023) show how parallelizations of Kruskal's and Boruvka's algorithms can converge to identical implementations. [1]
A connection between these two classical MST algorithms that has not yet been mentioned
Included in text to be added
Burtscher ( talk) 19:14, 17 December 2023 (UTC)
Burtscher ( talk) 19:14, 17 December 2023 (UTC)