Talk:Minimum spanning tree

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Mathematics Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Mid	This article has been rated as Mid-priority on the project's priority scale.

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. Anders Sørensen

That's probably the "minimum branching"/"optimum branching" problem: [1]. In many textbooks, "graph" means "undirected graph" (without multiple edges, halfedges, ...) unless stated otherwise. --Lukas Mach 20:00, 7 April 2007 (UTC)[reply]

it is a good ideal — Preceding unsigned comment added by 117.191.16.85 (talk) 14:58, 4 November 2015 (UTC)[reply]

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 Related problems section of this article for the digraph case. AHMartin (talk) 16:59, 12 July 2019 (UTC)[reply]

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 —Preceding unsigned comment added by 69.124.89.74 (talk) 22:26, 5 December 2007 (UTC)[reply]

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. KKoolstra (talk) 10:01, 9 April 2009 (UTC)[reply]

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} $\cup$ 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} $\cup$ 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)[reply]

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} $\cup$ 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.

Jeffxtreme (talk) 13:49, 1 October 2014 (UTC)[reply]

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. — Preceding unsigned comment added by 2620:4F:0:101:15A4:738E:AB92:D953 (talk) 00:40, 9 January 2014 (UTC)[reply]

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

Request

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)[reply]

Did you search for "directed graphs" in this article? Because if you did you would have found an answer. —David Eppstein (talk) 17:55, 11 September 2016 (UTC)[reply]

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.

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

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

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.

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

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 02:25, 1 February 2018 (UTC)[reply]

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

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

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

Convergence of Kruskal's and Boruvka's algorithms

This edit request by an editor with a conflict of interest was declined. A reviewer felt that this edit would not improve the article.

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

Fallin et al. (2023) show how parallelizations of Kruskal's and Boruvka's algorithms can converge to identical implementations.^[1]

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

Burtscher (talk) 19:14, 17 December 2023 (UTC)[reply]

^ Fallin, Alex; Gonzalez, Andres; Seo, Jarim; Burtscher, Martin (2023). A High-Performance MST Implementation for GPUs. International Conference for High Performance Computing, Networking, Storage, and Analysis. pp. 77:1–13. doi:10.1145/3581784.3607093. S2CID 261564071..

Burtscher (talk) 19:14, 17 December 2023 (UTC)[reply]

Not done. We would need secondary sourcing to indicate that this primary source is worth writing about. - MrOllie (talk) 19:31, 17 December 2023 (UTC)[reply]

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? —David Eppstein (talk) 20:01, 17 December 2023 (UTC)[reply]

[1] Fallin, Alex; Gonzalez, Andres; Seo, Jarim; Burtscher, Martin (2023). A High-Performance MST Implementation for GPUs. International Conference for High Performance Computing, Networking, Storage, and Analysis. pp. 77:1–13. doi:10.1145/3581784.3607093. S2CID 261564071..

[1]