Talk:Tree (graph theory)
From Wikipedia, the free encyclopedia
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)
[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)
