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] Discussion

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

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