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

(tag as stub; add fact)
Line 2: Line 2:
  
 
The converse is also true: an undirected and connected graph with <math>n</math> vertices and <math>n-1</math> edges is a tree.
 
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''s 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.
 +
 +
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", (0,0), NE);
 +
 +
add(pic.fit(),(0,1),10N);
 +
</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}}
 
{{stub}}

Revision as of 13:56, 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. 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 $\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.

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", (0,0), NE); add(pic.fit(),(0,1),10N); [/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=221734"