Talk:Tree (graph theory)

Untitled

A tree is called a rooted tree if one vertex has been designated the root and every edge is directed away from it.

Trees are defined here as undirected graphs, so what does it mean for every edge to be directed away from the designated root? Josh Cherry 03:34, 26 Jun 2004 (UTC)

You are quite correct. As it stands, this article is about trees in graph theory, which have undirected edges unless they are called "directed trees" or something similar. The additions here belong in Tree data structure or somewhere like that. Also, in CS the edges are often directed towards the root rather than away from it. --Zero 00:46, 31 Oct 2004 (UTC)

Actually, rooted trees are also important in combinatorics. An example that springs to mind is Wilson's algorithm, which despite the name is actually more important in combinatorics than in computer science — actually I already started writing a page that will describe it. The rest of these additions do belong in the other page, I agree. Gadykozma 16:11, 31 Oct 2004 (UTC)

Mathematically terse definitions: A forest is a cycle-free graph. A tree is a connected forest. Obvious! --Dbenbenn 04:57, 18 Dec 2004 (UTC)

Terseness. Overrated. --Trovatore 16:40, 13 July 2005 (UTC)[reply]

Directed Tree

Someone should add the directed trees too.

something like this: A digraph without directed cycles and with a (necessarily unique) root is called a directed tree. A vertex v in a directed tree, which is not the tail of an arrow, is called a leaf of the tree.

helohe 08:18, 8 Jun 2005 (UTC)

Well, that is not a correct definition. For example, 1->2, 2->3, 1->4, 4->3 satisfies your definition but is not a directed tree. Also, some people define directed trees so that the edges point towards the root rather than away. --Zero 08:39, 8 Jun 2005 (UTC)

In the book "Data Structures and Algorithm Analysis in C", it takes a tree as a directed tree. The direction is from the side close to the root to the side far from the root. And we can also see the same usage in Binary_tree. Both the graph and expression "For any non-empty binary tree with n0 leaf nodes and n2 nodes of degree 2, n0 = n2 + 1.[24]" are suggesting that a tree is a directed tree. So maybe we should change the expression into "directed graph"? And in that case the degree would become "out-degree" 183.157.160.25 (talk) 10:24, 12 October 2014 (UTC)[reply]

Trees not necessarily planar

The article claims that trees are always planar. But that's not true. Start with a root vertex, and now add κ more vertices, where κ is greater than the cardinality of the continuum. Attach the root directly to each of the other vertices and add no other edges. This is clearly a tree, but it can't be embedded into the plane, purely for cardinality reasons. Perhaps there's another notion of planar that would fix this, or maybe the article should say that finite trees are always planar. Is countable enough? --Trovatore 16:30, 13 July 2005 (UTC)[reply]

Answer: Yes, countable is sufficient. Sketch of proof: We can embed the complete ω-splitting graph into the plane as follows:

Put the root at the origin
Choose ω disjoint open intervals on the unit circle. Place one level-1 vertex at the midpoint of each, and add the edges.
Subdivide each of the angular ranges on the unit circle into ω more angular ranges and project them out to the circle of radius 2. Place one level-2 vertex at the midpoint of each, and add the edges.
And so on.

The argument is trivial, but I don't recall reading it anywhere, so it's probably "original research" by the quirky WP definition of that phrase. Still, surely it's referenced somewhere, so I've gone ahead and updated the article accordingly. If someone could find a ref it'd be appreciated. --Trovatore 20:08, 13 July 2005 (UTC)[reply]

CS tree--image appropriate?

Is Image:Tree diagram.png really appropriate here? The text right next to it says we're talking about undirected graphs. It's a good image, but perhaps belongs at Tree (data structure) or similar. --Trovatore 21:51, 19 September 2005 (UTC)[reply]

Point taken -- I've moved it there. Andre (talk) 21:58, 19 September 2005 (UTC)[reply]

Irreducible Trees

an irreducible is a tree in which there is no of vertices of degree 2.

Regular trees

Quote: "A regular (or homogeneous) tree is a tree in which every vertex has the same degree. See Regular_graph."

This would mean that the tree is either K1, K2 or it is infinite, correct?

My reasoning is that because any finite tree (other than K1) will have 'end vertices' (leaves) with degree 1. Thus, if all vertices have the same degree, then every vertex must have degree 1. The only connected graph which is 1-regular is K2.
Thus, the only regular finite trees are K1 and K2

Is that what is meant by the term 'regular tree'? Or does it mean that every vertex that is not a leaf has the same degree?
202.72.155.125 13:53, 16 May 2006 (UTC)[reply]

Yes, that seems like a silly definition.

I was on the verge of changing the article to say

"A regular (or homogeneous) tree is a tree in which every vertex that is not a leaf has the same degree. See regular graph. Examples of regular trees include binary trees, quadtrees, and octrees."

But a google search didn't back up my intuition -- I found papers saying things like

"The trees described by a finite graph are all regular." -- Gert Smolka 2002

So what is a better definition of a "regular tree" ?

--65.70.89.241 21:59, 23 August 2006 (UTC)[reply]

As this has not been fixed, I have removed the offending sentence. -- Jitse Niesen (talk) 06:33, 21 September 2007 (UTC)[reply]

Seems that graph theory and formal language theory use a different definition of regularity. In formal language theory, a regular tree is a tree which has only finitely many subtrees. In this context, trees may be finite or infnite; every finite tree can of course have only finitely many subtrees, but an infinite tree may also have only finitely many subtrees. An example is the infinite binary tree defined by the equation x=f(x,x), which has only itself as a subtree. This is the same as saying that a tree is regular if and only if it can be obtained by (possibly infinite) unfolding of a (possibly cyclic) finite graph. This is the definition used in the citation by Smolka above.

Ralf.treinen (talk) 21:22, 10 August 2010 (UTC)[reply]

Sometimes, in graph theory a "regular tree" is not a tree whose nodes all have same degree, but rather a rooted tree all of whose nodes at same distance from the root have the same degree.--217.190.183.145 (talk) 18:57, 4 November 2010 (UTC)[reply]

t(n)

Does anyone have a list of the known values of t(n), or a reference its asymptotic behaviour? 129.128.210.68 23:09, 28 March 2007 (UTC)[reply]

See [1]. McKay

I added what seems to be the canonical reference. -- Jitse Niesen (talk) 06:59, 29 March 2007 (UTC)[reply]

Cycles of length 2 mess up the definition

The definition of cycle allows cycles of length 2. In an undirected graph, these are somewhat degenerate: any two vertices that are connected by an edge are a cycle. Most graphs that we call trees have a lot of these cycles. So unless one changes the definition of cycle, these cycles have to be ruled out in the definition of tree.

Kees.huizing (talk) 10:44, 6 March 2008 (UTC)[reply]

What definition of "cycle" are you using? In my experience, the edges that make up a cycle should be all different, and thus cycles of length 2 do not exist (unless you're considering directed or multigraphs). -- Jitse Niesen (talk) 15:13, 6 March 2008 (UTC)[reply]

Agreed, but this definition of cycle is not used here in the wikipedia. Here, a cycle is some kind of path and a path is a sequence of connected vertices. So either the definition of path has to be adapted, or the definition of the definition of tree. Kees.huizing (talk) 22:22, 13 March 2008 (UTC)[reply]

Cycles are not the same thing as paths. Cycles must be closed, i.e. they are topologically like a circle (when they're planar graphs). linas (talk) 01:38, 27 March 2008 (UTC)[reply]

Although Kees has inadvertently noted a problem: the definition says that trees cannot contain any "simple cyles", leaving open the possibility that a tree can contain cycles that are not simple! WTF. fixing now. linas (talk) 01:43, 27 March 2008 (UTC)[reply]

Basic definitions are missing.

March 18 2017: Basic definitions are still missing; could someone please define a "leaf" before its use? Thank you. — Preceding unsigned comment added by Theor-phys (talk • contribs) 19:53, 19 March 2017 (UTC)[reply]

The first use of "leaf" is the sentence "an external vertex (or outer vertex, terminal vertex or leaf) is a vertex of degree 1.", which is exactly the definition you are requesting. —David Eppstein (talk) 23:28, 19 March 2017 (UTC)[reply]

I'd like to see the article expanded to define basic concepts like "the root of a tree", "leaf nodes", "depth", "breadth", etc. I was trying to remember the correct name for the number of child nodes of a given node. Is this the "degree" of a node? Or is it called "order"? or "node width"? It sure would be nice if this info was provided! Standard notation & symbols would be nice too. linas (talk) 01:33, 27 March 2008 (UTC)[reply]

April 20 2020: Basic definitions are still missing. The article does not introduce edges and does not give a proper definition of the term path. In particular, there is no relation between edges and paths specified in the article. — Preceding unsigned comment added by 145.64.254.243 (talk • contribs)

How low do we need to go? You'll notice that other terms in the infobox, notably the numbers 1 and 2, the subtraction operation −, and the comparison operation >, are also not defined. —David Eppstein (talk) 16:17, 20 April 2020 (UTC)[reply]

There are links to edge (graph theory) and path (graph theory) in the appropriate places. I don't see a problem here; not every article has to contain everything. XOR'easter (talk) 18:29, 20 April 2020 (UTC)[reply]

The CS tree is not the graph theory tree

It should be clearly explained in the first paragraphs that in computer science, a tree (i.e. a tree (data structure)) is rarely if ever a tree as defined here, but rather, an arborescence, usually with an ordering on the siblings of every parent node. Rp (talk) 00:15, 10 March 2009 (UTC)[reply]

I've taken the liberty to do so. Rp (talk) 19:34, 12 March 2009 (UTC)[reply]

Merge articles?

May I ask why there are two articles---Tree (data structure) and this one---who describe both nearly the same content? —Preceding unsigned comment added by 130.73.75.14 (talk) 10:07, 5 June 2009 (UTC)[reply]

See Arborescence (graph theory). The article Tree (data structure) describes precisely this. --PS T 14:59, 30 October 2009 (UTC)[reply]

F and G ?

there is something strange when the formula for enumeration of trees with isomorphism. Just below the formula it refered to some f and g that does not appear there. —Preceding unsigned comment added by 200.17.35.253 (talk) 14:47, 30 October 2009 (UTC)[reply]

Normal Spanning Trees

Currently the article states in the Facts section that "Every connected graph even admits a normal spanning tree (Diestel 2005, Prop. 1.5.6)". In fact this section of Diestel's book assumes that "our graphs will be finite unless otherwise stated" (Diestel 2005, pg 2).

Entry has been changed to "Every countable graph admits a normal spanning tree (Diestel 2005, Theorem 8.2.4.)" with an additional note that "There exist graphs with uncountably many vertices which do not admit a normal spanning tree (Diestel 2005, Theorem 8.5.2.)" —Preceding unsigned comment added by Sms97 (talk • contribs) 02:57, 29 March 2010 (UTC)[reply]

Irreducible CS / language tree?

One example of a tree is objects such as "A ((B C) D E)" (this has a root with two branches, one of which has three branches, one of which has two branches, and 5 leaves in total). These sometimes occur in computer science, and are especially common in parsing of languages.

In some sense this type of object represents an ordered irreducible tree because the expression "A ((B))" is functionally identical to "A B".

But it is certainly not a normal ordered irreducible tree, because the simplest tree corresponding to "A B" is A-R-B where the root vertex has exactly 2 links, which is disallowed by series-reduction.

It also seems very similar to an ordered irreducible planted tree (note planted implies the root vertex having a single link). So "A B" may correspond to R-={A,B} (this tree has a fourth vertex at which it branches). But there is no irreducible planted tree without leaves so there is nothing corresponding to the expression " " (which might otherwise just be a root vertex with zero links). Also, it breaks a certain behaviour: that anyplace having a leaf node can have further leaf nodes added at the same level (simply by appending the symbols immediately after it in the appropriate location in the expression). But the irreducible planted tree for one node "A" is R-A, and adding sibbling nodes to A causes the tree to cease being planted, instead the nodes need to all be shifted a level deeper into the tree, which fundamentally changes how the position of A would be addressed most naturally.

It still seems possible to have a one-to-one correspondence between theses expressions and ordered irreducible planted tree graphs. However, it seems that a different type of graph would have a more natural correspondence. This type of graph should permit the root to have any number of links (including zero and two). But it should still be irreducible in some sense (not technically in the usual topological sense, but still the number of vertices is minimal out of the possible graphs with the same relationship among their leaf nodes, although I'm not sure how to be entirely specific about the fashion of that relationship)..

Can anyone expand better on the relationship between graph theory and the types of tree structure encountered in applications? Cesiumfrog (talk) 05:39, 12 October 2010 (UTC)[reply]

Chromatic Number

I don't think the chromatic number is strictly right in the infobox, since the trivial graph with 1 vertex can be counted as a tree and has chromatic number of 1.

I suggest we change it to chromatic number <=2 or 2 if v>1 as per Theorem 8-1 from [2] Enigmaster (talk) 17:06, 24 November 2010 (UTC)[reply]

Is an empty graph a tree?

According to the first 5 definition (which generalize to infinite graphs), an empty graph should be a tree. But then there's 2 definitions for finite graphs, an tree with 0 vertex should have -1 edge, which is impossible. So is an empty graph a tree? Bbbbbbbbba (talk) 15:54, 14 January 2011 (UTC)[reply]

Inconsistency?

From "Definitions":

"A leaf is a vertex of degree 1"
"A terminal vertex of a tree is a vertex of degree 1"

Does it mean that "a leaf" is exactly the same as "a terminal vertex"? No, it is not:

"the root, if not a leaf itself, is a terminal vertex if it has precisely one child"

So, what exactly is a leaf and a terminal vertex (in a rooted tree)? Boris Tsirelson (talk) 15:24, 11 December 2012 (UTC)[reply]

Rooted plane trees

The definition of a rooted plane tree was incorrect. I removed the references to embedded homo/isotopy and to counter/clockwise ordering. The usual definition has a plane tree read left to right, not circularly, and has the root at the top with edges descending. (Or perhaps, but equivalently, the reverse.) The circular and left-to-right definitions are not equivalent, as (for instance) the former has no first leaf. I replaced the topology and circularity with top-down and left-right definitions. Zaslav (talk) 05:51, 29 June 2013 (UTC)[reply]

It is still not right. There is a common distinction between "plane tree" and "rooted plane tree" that is missing. Also the text has a concept of "lower" in the plane, which has no actual geometric meaning. Commonly a plane tree just means a tree (without root) embedded in the plane. Some people call it a rooted plane tree if a vertex is specified as a root, and some people use this terminology for an ordered tree. All three concepts are widespread. McKay (talk) 02:09, 19 August 2013 (UTC)[reply]

otter constant bounds?

Does anyone know if how many digits claimed for Otter's constant are actually proved?

E.g., does a proof appear somewhere that 2.9<α<3 ?

(I am worried that these expansions are just excellent guesses based on the behavior of low-order terms. For example, it seems like the sequence of digits for α at the Encyclopedia of Integer Sequences has been revised at least once to correct erroneous digits.) 128.2.116.226 (talk) 19:20, 4 November 2013 (UTC)[reply]

The topic is discussed in Knuth's TAOCP Vol. 1, Chap. 2.3.4.4; and he is well-known for making very few mistakes. Unfortunately, I do not have Knuth's book at hand at the moment, so I cannot check if he derives the constants, and if they are cited correctly in this wikipedia article. Also, (I haven't looked at it carefully, but...) your question seems to be addressed on page 476f. of Flajolet & Sedgewick's book (in particular, Note VII.21). Hermel (talk) 23:19, 9 November 2013 (UTC)[reply]

Thanks for the reply! My first reading of Note VII.21 in that book seems to suggest again that these are just 'excellent guesses', no? "For instance, a conservative estimate of the accuracy attained ... is ... Accuracy appears to be a little better than ...". Are there actually bounds? It looks like these are estimates based on the assumption that the initial terms of the sequence capture its asymptotic behavior well (which is supported by the experimental evidence, which is why the "accuracy appears to be a little better than ..."). Am I missing something?

Merge Arborescence (graph theory)?

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.

There is an objection voiced to a merger of Rooted binary tree (which is now a redirect) which in any case was not tagged with a merger proposal tag. There is doubt expressed about a merger of Arborescence (graph theory), so after many months of no further discussion, I'll close this as Do not merge and remove the merge tags. Shhhnotsoloud (talk) 13:41, 19 May 2017 (UTC)[reply]

I've expanded it a bit, but I'm not sure it's really justified as its own article. It could be a section here as it is now. JMP EAX (talk) 19:53, 24 July 2014 (UTC)[reply]

Also Rooted binary tree should be merged here, as it's not actually describing a data structure. JMP EAX (talk) 19:09, 25 July 2014 (UTC)[reply]

I strongly disagree re rooted binary trees. As combinatorial objects, they are different from trees (and rooted trees and plane trees) because they specify which of their children is left and which is right (even when there is only one child). And they have important applications that are irrelevant to other kinds of trees. There's a better case for merging arborescences, because those really are combinatorially equivalent to rooted trees, but I'm still not entirely convinced. —David Eppstein (talk) 18:38, 7 October 2014 (UTC)[reply]

(non-admin closure)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Metaphors of up, down, ascendant etc should be made explicit

nomenclature "down" and "up" tree are used but not defined. This could confuse reader. Apparently in this article "up" is in the direction defined as "ascendent", i.e. toward root, away from leaves, toward parent, etc. Root is higher than other nodes but also less than all other nodes in the meaning of the partial ordering operator "<". The imagery is compatible with metaphor of inverted tree. The nomenclature has evolved thusly for good reasons, and is well known among practitioners, but it is counterintuitive and should be made explicit where terms like "up" or "height" are introduced. — Preceding unsigned comment added by 98.109.203.248 (talk) 01:07, 21 October 2020 (UTC)[reply]

Labeled tree

"A labeled tree is a tree in which each vertex is given a unique label."
I disagree. Up to my understanding, the role of labeled trees is to have a possibility to give the same label to various nodes. Consider e.g. parse trees (of context-free grammars), where nodes are labeled by non-terminal symbols, and various nodes may be given the same label. Wlodr (talk) 17:35, 25 January 2022 (UTC)[reply]

Rooted tree term used before its definition

In the introduction there is this: "The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees." At this point, "rooted tree" has not been defined and so a reader coming upon this and not knowing what a rooted tree is will be confused. Should be fixed. 2601:600:877F:DD20:E052:B208:100D:5462 (talk) 16:42, 16 March 2024 (UTC)[reply]

The introduction is not the place for going on and on about precise technical definitions. —David Eppstein (talk) 17:59, 16 March 2024 (UTC)[reply]