Talk:Spanning tree (mathematics)

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Discrete mathematics

Contents

[edit] Definition

The definition of "spanning forest" given here is not the usual one in graph theory. Usually a spanning forest is any forest which is a subgraph and whose vertices include all the vertices of the graph. Even the subgraph which has all of the vertices but no edges at all is a spanning forest. --McKay 15:04, 27 August 2006 (UTC)

I'm not sure about that. Such a definition doesn't seem as useful. For example, this paper maintains a spanning forest of a graph as edges and vertices are added and deleted, which would of course be trivial if it had the definition you give. Every other reference I found, at least in computer science, was also using it in this sense. I'd like to see a citation for your definition. Deco 23:16, 27 August 2006 (UTC)
Your suggestion that it is different in computer science seems to be correct. As far as (mathematical) graph theory is concerned, usually "spanning forest" is taken to be the conjunction of "spanning subgraph" and "forest"; i.e., any spanning subgraph that happens to be a forest. Most graph theory books (I looked at about 8-9) don't give a separate definition. Searching for "spanning forest" at arXiv gives 18 papers of which all but 1 seem to use this definition. Of course the solution to this problem is to give both definitions. I think we are fairly safe in saying that one is common in computer science and the other is common in graph theory. --McKay 14:13, 28 August 2006 (UTC)

[edit] Expert attention

The article claims that expert attention is needed. Is this re the "maximal" in the definition of spanning forest, or something else? It could certainly stand more and more focused sources, but the basic content looks ok to me. Regarding spanning forests: the main context I've seen this phrase in is "minimum spanning forest", where maximality is required for the concept to make sense, so the definition in the article looks ok to me. But if the other definition can be sourced as well, then we should probably describe both definitions. —David Eppstein 02:52, 17 April 2007 (UTC)

I put in both definitions. Now they are equally well sourced (;-). That raises a general question: if the evidence we have for a particular definition is a bunch of papers at arXiv that use it, what is the best way to cite it? None of those papers are especially relevant to this page, they just define a phrase in a particular way. --McKay 04:35, 17 April 2007 (UTC)

[edit] at least k vertices?

I'm not sure that "the minimum tree that spans at least k vertices" is a problem on spanning trees. On the other hand, I don't strongly object to its inclusion. McKay 05:01, 18 April 2007 (UTC)

I don't strongly object to its removal from this article, either, if you prefer that. It is commonly called the minimum k-spanning tree, but maybe it's a distinct enough concept that k-spanning tree should be a separate article. —David Eppstein 06:10, 18 April 2007 (UTC)

[edit] Image

The image of the graph with superimposed spanning tree has an accessibility problem. It appears solid black to red-green or totally colour blind people. Yellow on black would be better. --124.254.80.223 07:03, 2 September 2007 (UTC)

I have normal color vision and it wasn't very easy for me to distinguish the colors in that drawing either, and I don't think the nonplanarity of the drawing added to its readability. I've replaced it; please let me know whether the colors in the new version are good enough. —David Eppstein 15:42, 2 September 2007 (UTC)
Red-blue isn't a very comfortable colour combination either. The suggested yellow-black would probably look good. - Michh (talk) 14:03, 22 April 2008 (UTC)