Trees in Graph

tutorial and example
tutorial and example

What is tree?

A tree is an undirected graph in which two vertices are connected together by exactly one path. A tree with N number of vertices contains (N−1) number of edges.

The edges of a tree are known as branches.

Elements of trees are called their nodes.

The nodes without child nodes are called leaf nodes.

A labelled tree diagram with 6 vertices and 5 edges

Spanning Tree: Spanning tree is the subtree of the graph that contains all the vertices of that graph. The edges of spanning tree are called Branches.

Forest: A forest is an undirected graph in which all the connected components are trees. For every tree number of vertices (V) – number of edges (E) = 1, we can count the number of trees that are within a forest by subtracting the difference between total vertices and total edges.

Figure showing difference between Tree and Forest

Polytree: A Polytree also known as Oriented tree is a directed acyclic graph whose underlying undirected graph is a tree. If we replace the directed edges with undirected edges, undirected graph is obtained.

Rooted Tree : A rooted tree is a tree in which one node is designated as root. The edges of the rooted tree can have orientation either away from the tree or towards the tree.

When the edges of rooted tree are directed away from the tree than it is known as arborescence, branching, or out-tree and when the edges of rooted tree are directed towards the root than it is known as anti-arborescence or in-tree.

Properties of graph :

  1. Every tree is a median graph and bipartite graph
  2. In every connected graph G there is a spanning tree .
  3. For any three vertices in a tree the path between them has exactly one vertex in common .