View source for Talk:Minimum spanning tree

{{WikiProject banner shell|class=C|
{{WikiProject Computer science|importance=high}}
{{WikiProject Mathematics|importance=Mid}}
}}

==Directed graphs==
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. [[User:anars|Anders Sørensen]]

:That's probably the "minimum branching"/"optimum branching" problem: [http://www.ce.rit.edu/~sjyeec/dmst.html]. In many textbooks, "graph" means "undirected graph" (without multiple edges, halfedges, ...) unless stated otherwise. --[[User:Lukas Mach|Lukas Mach]] 20:00, 7 April 2007 (UTC)
:it is a good ideal  <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/117.191.16.85|117.191.16.85]] ([[User talk:117.191.16.85|talk]]) 14:58, 4 November 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
:This article concerns undirected graphs because finding the MST of a digraph is a different (harder) problem.  Consider that neither Prim's nor Kruskal's algorithms will even give the correct answer if their initial "arbitrary" vertex selection is not the root of a DAG.  Does your textbook say that an the graph has to be strongly connected, unilaterally connected, or weakly connected in order for an MST to exist?  See the [[Minimum spanning tree#Related problems|Related problems]] section of this article for the digraph case.  [[User:AHMartin|AHMartin]] ([[User talk:AHMartin|talk]]) 16:59, 12 July 2019 (UTC)

==Negative weights?==
"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  <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/69.124.89.74|69.124.89.74]] ([[User talk:69.124.89.74|talk]]) 22:26, 5 December 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

==Missing citations?==
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. [[User:KKoolstra|KKoolstra]] ([[User talk:KKoolstra|talk]]) 10:01, 9 April 2009 (UTC)

==Mathematical problem==

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'''} <math>\cup</math> '''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'''} <math>\cup</math> '''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.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/70.112.206.154|70.112.206.154]] ([[User talk:70.112.206.154|talk]]) 23:21, 9 March 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

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'''} <math>\cup</math> '''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: 
* Then C has an edge e2 whose weight is greater than the weight of e1, since all edges in B with less weight are in A by the choice of e1, and C must have at least one edge that is not in A because otherwise A would contain a cycle in contradiction with its being an MST.

I would change it to say:
* C must contain at least one edge e2 that is not in A because otherwise A would contain a cycle in contradiction with its being an MST.  Thus, edge e2 is only in B.  
* From our particular choice of e1, we that the edge e2 has a greater weight than e1.
*  Then C has an edge whose weight is greater than the weight of e1. 
[[User:Jeffxtreme|Jeffxtreme]] ([[User talk:Jeffxtreme|talk]]) 13:49, 1 October 2014 (UTC)

== Incorrect diagram ==

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.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2620:4F:0:101:15A4:738E:AB92:D953|2620:4F:0:101:15A4:738E:AB92:D953]] ([[User talk:2620:4F:0:101:15A4:738E:AB92:D953|talk]]) 00:40, 9 January 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== Figure title may be incorrent ==

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.
[[User:Rellims2012|Rellims2012]] ([[User talk:Rellims2012|talk]]) 14:19, 17 March 2015 (UTC)

==Request==

Can anybody knowing this stuff take a look at [[random minimal spanning tree]]? I find that one not so clear. Thanks. [[User:Oleg Alexandrov|Oleg Alexandrov]] 03:23, 25 Jun 2005 (UTC)

Does anyone know how to solve the problem for directed graphs?
Ali Hassan  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/39.42.63.81|39.42.63.81]] ([[User talk:39.42.63.81|talk]]) 14:50, 11 September 2016 (UTC)</small> <!--Autosigned by SineBot-->
:Did you search for "directed graphs" in this article? Because if you did you would have found an answer. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:55, 11 September 2016 (UTC)

== Tarjan's criterion ==

I believe there are Russian articles with Tarjan's criterion:

:Some spanning tree is minimal if and only if the weight of any other edge (''x'', ''y'') (not from spanning tree) is not less than the weight of the heaviest edge on the path from ''x'' to ''y'' in spanning tree.

[[User:Wumbolo|Wumbolo]] ([[User talk:Wumbolo|talk]]) 22:09, 6 August 2017 (UTC)

== External links modified (February 2018) ==

Hello fellow Wikipedians,

I have just modified one external link on [[Minimum spanning tree]]. Please take a moment to review [[special:diff/823410699|my edit]]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:
*Added archive https://web.archive.org/web/20040824184059/http://akpublic.research.att.com/~dsj/papers/3way.pdf to http://akpublic.research.att.com/~dsj/papers/3way.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

{{sourcecheck|checked=false|needhelp=}}

Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 02:25, 1 February 2018 (UTC)

==Proving correctness==
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. [[User:Cheater no1|Cheater no1]] ([[User talk:Cheater no1|talk]]) 10:55, 1 August 2019 (UTC)

:You mean the cycle property and cut property, already listed in separate subsections of the "properties" section? —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 19:18, 1 August 2019 (UTC)

== MST Cut example ==

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. [[User:Hobit|Hobit]] ([[User talk:Hobit|talk]]) 15:04, 3 February 2021 (UTC)

== Convergence of Kruskal's and Boruvka's algorithms ==

{{edit COI|D|T}}

* Specific text to be added in the section on "Parallel and distributed algorithms":

{{harvtxt|Fallin|Gonzalez|Seo|Burtscher|2023}} show how parallelizations of Kruskal's and Boruvka's algorithms can converge to identical implementations.<ref>{{cite conference |last1=Fallin |first1=Alex |last2=Gonzalez |first2=Andres |last3=Seo |first3=Jarim |last4=Burtscher |first4=Martin |year=2023 |title=A High-Performance MST Implementation for GPUs |conference=International Conference for High Performance Computing, Networking, Storage, and Analysis |pages=77:1–13 |doi=10.1145/3581784.3607093 |s2cid=261564071}}.</ref>

* Reason for the addition:

A connection between these two classical MST algorithms that has not yet been mentioned

* References supporting change:

Included in text to be added

[[User:Burtscher|Burtscher]] ([[User talk:Burtscher|talk]]) 19:14, 17 December 2023 (UTC)
<references />
[[User:Burtscher|Burtscher]] ([[User talk:Burtscher|talk]]) 19:14, 17 December 2023 (UTC)

:{{not done}}. We would need secondary sourcing to indicate that this primary source is worth writing about. - [[User:MrOllie|MrOllie]] ([[User talk:MrOllie|talk]]) 19:31, 17 December 2023 (UTC)
::If it's parallel, it's not Kruskal's algorithm, but something else. Why should it be surprising that a paper modifying classical algorithms to produce a different parallel algorithm produces only one algorithm? In what sense can implementations be said to converge? —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 20:01, 17 December 2023 (UTC)