Talk:Tree (graph theory)

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 High Priority  Field: Discrete mathematics

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)

Contents

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

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

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)

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

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

[edit] Irreducible Trees

I read somewhere that MIT had conducted research in this subject for 2 years before arriving at a solution, although I am not sure if this is fact or if it was made up for the movie Good Will Hunting (I never watched it, I just read that online.) Does anyone else know anything about this?

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

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)

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

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

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

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

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)
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)
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)
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)

[edit] Basic definitions are missing.

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)