Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Tree (graph theory)"
(→‎Example)
 
(2 intermediate revisions by the same user not shown)
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===
+
==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.
  
−
For every node except the root, there is only <math>1</math> ''parent''; the parent is the other end of the edge going into the node, assuming the edges are going out from the root. ''Child''s of a node is the nodes where this node's outward edges reach (assuming the edges are going out from the root).
+
For every node except the root, there is only <math>1</math> ''parent''; the parent is the other end of the edge going into the node, assuming the edges are going out from the root. ''Child''ren 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.
 
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.
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", (0,0), NE);
+
label("node 1 is the root in this example", (10,0), NE);
  
−
add(pic.fit(),(0,1),10N);
+
add(pic.fit(),(0,0));
 
</asy>
 
</asy>
  

Latest revision as of 18:13, 5 July 2024

A tree is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph $G=(V,E)$ such that for any two vertices $u, v \in V$ with $u \neq v$, there is exactly one path connecting $u$ and $v$ in $G$. Every tree that has $|V|=n$ vertices has exactly $n-1$ edges.

The converse is also true: an undirected and connected graph with $n$ vertices and $n-1$ 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 $|V|-|E|$.

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 $1$ parent; the parent is the other end of the edge going into the node, assuming the edges are going out from the root. Children 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 $\boldsymbol{k}$-ary tree is a tree in which all nodes have at most $k$ children. When $k=2$, it is a binary tree; when $k=3$, 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 in this example", (10,0), NE); add(pic.fit(),(0,0)); [/asy]

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Tree_(graph_theory)&oldid=221747"