Sales Toll Free No: 1-855-666-7446

Trees in Discrete Mathematics

Top
Sub Topics

A tree is a graph which contains not only a data structure of set of elements but also the connection among all the elements. The concept of trees was given by the mathematician 'Cayley' in the year 1857.

A tree in discrete mathematics is a set of collection of straight line segments, which have their connectivity at the end which contains the cyclic loops. In simple terms, it is a simple graph to plot and its direction is not defined. All trees are like bipartite graphs.

When no particular root is singled out from the tree, then it is sometimes known as free tree.

The point where they connect or their point of connection is known as fork and their segments are known as branches. Tree leaves in the tree graph are final segment and the nodes are present at the end. A binary tree is a tree which has two branches at the each side of the fork and at the end of their branches, there are one or two leaves.

Root is a special node which has been designed to turn a tree into a rooted tree. In this type of a tree, there exists one special node that is among the graph edge. 

Moreover, that given node is termed as its child, while its siblings are those root nodes which are connected to the same node with a same distance.

These trees are used in several fields such as in the field of computer science, the study of electrical circuits, computer networks, telephone networks, etc.

Trees in Discrete Mathematics

Rooted Tree

Back to Top
A tree can be defined as a graph G that satisfies the following condition:
  • Graph 'G' is connected by various edges and there is no cycle in the graph.
  • If any of the edge is removed, then graph 'G' is not connected.
  • Any two of the vertices are connected by a unique path.

If there are 'n' vertices in a graph, then there will be n - 1 edges in the graph and no cycle. Rooted tree can be defined as a tree with a vertex or node called root. In this tree, edges have a natural generation away or towards the root. Another term is the tree order which can be defined as the partial sequencing on the nodes (vertices) of a tree with A $leq$ B if and only if the path from the root to B passes through A.

Rooted tree can also be defined as sub graph of a graph, which is an ordinary tree if the ends of every edge in the graph 'G' are equivalent in this tree order whenever the ends of the edges (lines) are vertices of the tree. Origin of vertex is also a vertex attached to it on the path to the root in a rooted tree.

Rooted tree can also be defined as a tree which has countable number of vertices (nodes). In this tree, a particular node is differentiated from other nodes and is referred as root.

Following tree shows roots in red color:
Rooted Tree
Rooted trees can be finite or infinite. If rooted tree contains infinite number of nodes, then it is referred as infinite rooted tree and if there are finite nodes (vertices), then it is referred as finite rooted tree.