Talk:Minimum spanning tree

From Wikipedia, the free encyclopedia

[edit] 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?

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

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