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

(more complete description of a tree)
(→‎Example)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
A '''tree''' is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph <math>G=(V,E)</math> such that for any two vertices <math>u, v \in V</math> with <math>u \neq v</math>, there is exactly one path connecting <math>u</math> and <math>v</math> in <math>G</math>. Every tree on <math>|V|=n</math> vertices has exactly <math>n-1</math> edges.
+
A '''tree''' is an undirected [[Graph (graph theory)|graph]] which is both connected and acyclic. Equivalently, a tree is a graph <math>G=(V,E)</math> such that for any two vertices <math>u, v \in V</math> with <math>u \neq v</math>, there is exactly one path connecting <math>u</math> and <math>v</math> in <math>G</math>. Every tree that has <math>|V|=n</math> vertices has exactly <math>n-1</math> edges.
 +
 
 +
The converse is also true: an undirected and connected graph with <math>n</math> vertices and <math>n-1</math> 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 <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.
 +
 
 +
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.
 +
 
 +
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:
 +
<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.
 +
 
 +
{{stub}}

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"