Difference between revisions of "Tree (graph theory)"
(clean up code) |
|||
| Line 5: | Line 5: | ||
A '''forest''' is an undirected graph where there is '''at most''' one path from any vertex to another. A forest is an undirected graph that is acyclic in which all connected components are trees; it is a disjoint union of trees. The number of trees in a forest could be found by <math>|V|-|E|</math>. | A '''forest''' is an undirected graph where there is '''at most''' one path from any vertex to another. A forest is an undirected graph that is acyclic in which all connected components are trees; it is a disjoint union of trees. The number of trees in a forest could be found by <math>|V|-|E|</math>. | ||
| − | + | ==Rooted Tree== | |
A '''rooted tree''' is a tree that has a node designated as the root. We can assign the nodes directions going either to the root or outwards from the root. | A '''rooted tree''' is a tree that has a node designated as the root. We can assign the nodes directions going either to the root or outwards from the root. | ||
| Line 14: | Line 14: | ||
A '''<math>\boldsymbol{k}</math>-ary tree''' is a tree in which all nodes have at most <math>k</math> children. When <math>k=2</math>, it is a binary tree; when <math>k=3</math>, it is a ternary tree. | A '''<math>\boldsymbol{k}</math>-ary tree''' is a tree in which all nodes have at most <math>k</math> children. When <math>k=2</math>, it is a binary tree; when <math>k=3</math>, it is a ternary tree. | ||
| + | ===Example=== | ||
Here is an example of a rooted tree: | Here is an example of a rooted tree: | ||
<asy> | <asy> | ||
| Line 23: | Line 24: | ||
draw(pic,bt,condensed=false); | draw(pic,bt,condensed=false); | ||
| − | label("node 1 is the root", ( | + | label("node 1 is the root", (10,0), NE); |
| − | add(pic.fit(),(0, | + | add(pic.fit(),(0,0)); |
</asy> | </asy> | ||
Revision as of 14:12, 5 July 2024
A tree is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph 
such that for any two vertices 
with 
, there is exactly one path connecting 
and 
in 
. Every tree that has 
vertices has exactly 
edges.
The converse is also true: an undirected and connected graph with 
vertices and edges is a tree.
A forest is an undirected graph where there is at most one path from any vertex to another. A forest is an undirected graph that is acyclic in which all connected components are trees; it is a disjoint union of trees. The number of trees in a forest could be found by 
.
Rooted Tree
A rooted tree is a tree that has a node designated as the root. We can assign the nodes directions going either to the root or outwards from the root.
For every node except the root, there is only 
parent; the parent is the other end of the edge going into the node, assuming the edges are going out from the root. Childs of a node is the nodes where this node's outward edges reach (assuming the edges are going out from the root).
The height of a vertex in a rooted tree is the length of the longest downward path to a leaf from that vertex. The depth of a vertex is the length of the path going from the root to itself. The height of a tree is the height of the root. The depth of a tree is the maximum depth of all vertices in the tree.
A 
-ary tree is a tree in which all nodes have at most 
children. When 
, it is a binary tree; when 
, it is a ternary tree.
Example
Here is an example of a rooted tree:
![[asy] import binarytree; picture pic; binarytree bt=binarytree(1,2,3,4,5,nil,nil,6,nil,nil,7,8,nil,nil,nil,nil,9,10,11,nil,nil,12,nil,nil,13,14,nil,15); draw(pic,bt,condensed=false); label("node 1 is the root", (10,0), NE); add(pic.fit(),(0,0)); [/asy]](http://latex.artofproblemsolving.com/2/1/5/2154a881ffeb05b9267b8259083fdd33157c2c7d.png)
In the graph above, it is a binary tree since each node has at most 2 children.
For example, node 3 is a child of node 2, node 6 is a child of node 4. Node 4 has 2 children: 5 and 6 and 1 parent: 3.
This article is a stub. Help us out by expanding it.
