Talk:Spanning tree

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)

I am not experienced with CS literature but I have never seen a CS article with your CS definition. Can you provide some evidence that it's common and the math one is not common in CS? The usage in (mathematical) graph theory is well nigh universally the one based on vertices. I rewrote the section to deal with that. If it needs rewriting, the usages should not be mixed up. Zaslav (talk) 21:23, 21 October 2022 (UTC)

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)

I take "minimum spanning forest" to be a short form of "minimum maximal (spanning) forest". This sort of shortening is common and should not be taken as meaning that "spanning forest" without "minimum" means a maximal forest. As I wrote to McKay, I want to see evidence that "spanning forest" meaning all vertices is rare in CS and the meaning of "maximal forest" is common in CS. I don't claim to know the CS literature; I do know the graph theory literature reasonably well. I'm looking forward to seeing specific evidence. Thanks in advance to both of you. Zaslav (talk) 21:27, 21 October 2022 (UTC)

I can only ever recall seeing the "maximal" usage. I believe the article's claim that this sense is rare is false. Examples:

• "we define a spanning forest of G to be a forest obtained by taking a spanning tree of each component of G": doi:10.1080/00029890.1973.11993318 (Note! This is mathematics, not computer science, in the Monthly from 1973).
• "A spanning forest of G is an acyclic subgraph of G containing all vertices of G and in which any connected component is a tree", doi:10.1007/s11590-017-1161-6 (not clearly explained but unambiguous).
• "In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than..." (would be false for the other definition): doi:10.1145/3055399.3055415.
• An article that defines "spanning" more generally as having the same components, and then uses that to infer what a spanning forest must mean: doi:10.1016/j.imavis.2009.06.017.

—David Eppstein (talk) 21:52, 21 October 2022 (UTC)

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)

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)

fundamental cycle?

The article on cycle space uses a term "fundamental cycle", which, I think, .. just guessing from context... must be the cycle that one gets when one adds one edge to the spanning tree. So I'm guessing that the set of fundamental cycles is in 1-1 correspondence with the set of edges that are not in the spanning tree. And I guess these do form a basis for cycle space, since all other cycles are generated from this set. And I guess also that this set is also the minimum generating set, too. Right? Could someone clarify that article?

Also: I assume that *all* spanning trees of a graph have the same number of edges in them, right? This is not exactly "trivially obvious", and yet, the article doesn't ever say this anywhere. (I mean, I have to appeal to the Euler characteristic to prove this, i.e. that V-E=1 for all trees, and since V is fixed ... and so I take this as "not obvious") ... Experts, please fix... Thanks ... linas (talk) 23:24, 7 September 2008 (UTC)

Never mind, that's clearly the correct definition. I'll just add this to the article; give me whack in the head if that's wrong. linas (talk) 01:23, 8 September 2008 (UTC)

I work in computational topology, and in this field a fundamental cycle is a cycle on a surface that cannot be continuously deformed into a point. A torus, for example, has two classes of fundamental cycles: Handles (those with the shape of a string tied around the torus passing through its center) and tunnels (what would be the shape of a string tied to the interior of the torus if it were hollow). There are ways to compute fundamental cycles using spanning trees, but not every edge that does not belong to the spanning tree spans a fundamental cycle (see Dynamic Generators of Topologically Embedded Graphs, by David Eppstein). 169.234.126.254 (talk) 08:31, 1 December 2008 (UTC)

Thanks for the plug. But that paper is about graphs embedded onto surfaces. But you can view the graph itself as a 1-dimensional complex, not embedded into anything bigger. With that view, all cycles are non-contractible, but they are not independent: e.g. in mod2 homology, two cycles that share a single edge add to form a third cycle that is their union minus that shared edge. It turns out that you get an independent cycle for each non-tree edge, formed by that edge together with the complementary path in the spanning tree. —David Eppstein (talk) 16:05, 1 December 2008 (UTC)

minimum cycle length

The first characterization of spanning tree is

a spanning tree of a connected graph G can also be defined as a maximal set of edges of G that contains no cycle

The wikipedia article on path says a 'simple cycle' is

[a sequence of vertices] with no repeated vertices aside from the start/end vertex

Something small is missing from one of these definitions. Cycles of length 3 are contained in minimum spanning trees.

More explicitly, let's say we have a spanning tree with at least two vertices. Pick two adjacent vertices and call them $a$ and $b$. Since they are adjacent, $(a,b)$ and $(b,a)$ are edges in the graph. Then the path $(a,b,a)$ is is contained in the spanning tree, and ($a,b,a)$ is a cycle because it starts and ends on $a$ and there are no repeated vertices aside from $a$. But spanning trees do not contain cycles.

I think we just need to say, either in the definition of cycle or in the definition of spanning tree, that we are only considering paths/cycles of length ≥ 4.

Wallers (talk) 16:52, 16 October 2009 (UTC)

You mean length ≥ 3, I hope. Anyway, my preference would be to fix the definition of cycle to disallow 2-cycles, because this occurs elsewhere as well; for instance in directed acyclic graph it is mentioned that forests are the undirected acyclic graphs, which again only makes sense if 2-cycles are not counted. One possibility would be, rather than putting in an unmotivated constraint about cycle lengths, to say that all edges on the cycle as well as all vertices should be distinct — that way multigraphs are allowed to have 2-cycles but simple undirected graphs aren't. —David Eppstein (talk) 17:08, 16 October 2009 (UTC)

Oh you're right, we measure path length as the number of edges not vertices. Good suggestion about the unique edges. Wallers (talk) 18:53, 16 October 2009 (UTC)

Ok, I made the change to the path article. —David Eppstein (talk) 05:10, 17 October 2009 (UTC)

By the way, Cycle (graph theory) and Walk (graph theory) might require the same clarification. — Miym (talk) 11:26, 17 October 2009 (UTC)

Style of defining Spanning Tree

Do any of you think a more formal style for the definition of spanning tree might be clearer? It comes down to taste, but I like this more

$T$ is a spanning tree of a connected, undirected graph $G$ if

i) $T$ is a subgraph of $G$,

ii) $T$ contains all the vertices $G$, and

iii) $T$ is a tree.

than what is currently written

A spanning tree $T$ of a connected, undirected graph $G$ is a tree composed of all the vertices and some (or perhaps all) of the edges of $G$.

Wallers (talk) 17:22, 15 December 2009 (UTC)

Maximum leaf spanning tree

Maximum leaf spanning tree redirects here, but it's not actually mentioned on the page. Also, it's mentioned in the list of NP-complete problems but there's no discussion of complexity here. 71.96.238.254 (talk) 08:06, 5 May 2010 (UTC)

I changed the redirect to Dominating set#Variants, where the max leaf spanning tree is actually mentioned. But it (and its equivalent problem of the smallest connected dominating set) could probably support a standalone article. —David Eppstein (talk) 15:18, 5 May 2010 (UTC)

Category:NP-complete_problems

This article is in a category NP-complete problems, however the other problems in the list are more defined by their names. For this problem, there is only "Spanning tree" label, which could incorectly imply that finding a spanning tree is a NP-complete problem, which isn't. — Preceding unsigned comment added by 212.80.83.198 (talk • contribs)

I took out the category. There is no discussion of NP-completeness anywhere in the text of the article; a spanning tree isn't even a problem, and as you say the most obvious computational problem associated with spanning trees (find one) is easy. —David Eppstein (talk) 16:55, 20 February 2011 (UTC)