# Tree

Ankur Kulhari

###### Tree: is an undirected graph with properties:

Fig. 1: Connected Graph

• is to be connected graph – there should exist a path between any two nodes/vertices
• no cycles – there should not exist a path in which starting and ending nodes are same
• a simple cycle is formed if any edge is added it – an edge is the connecting link between two nodes.
Example: if a new edge, say between A and D is added a cycle (A-B-D-A) is formed.

Fig. 2: Cycle by adding a new edge

• if an edge is removed, it will no more connected.
Example: say if we remove the edge D-E, the graph is no more connected graph and hence no tree.

Fig. 3: disconnected graph if edge removed

• any two nodes/vertices should be connected by a unique simple path
###### For a tree with n nodes/vertices following condition should be satisfied:
• it is connected and has n − 1 edges.
Example: considering Fig. 1, number of nodes (n) = 7 => e=(n-1) =7-1=6.
• has no simple cycles and has n − 1 edges.
###### Terminologies of tree:
• Internal node/vertex: it (or inner vertex or branch vertex) is a vertex with degree ≥ 2.

Fig. 4: Internal Nodes (B, D, E and F with degree ≥ 2)

In fig. 4 nodes/vertices B, D, E and F with degree ≥ 2 are internal nodes.
• External node/vertex: it (or outer vertex, terminal vertex or leaf) is a vertex with degree = 1.
Example: In fig. 4 nodes A, C and G are External nodes.
• Path:A sequence of nodes traversed from node to node along the edges is called path.
###### Types of trees
• Polytree
• Rooted tree
• Ordered tree: An ordered tree (or plane tree) is a rooted tree in which an ordering is specified for the children of each vertex.
• Hyper tree

This site uses Akismet to reduce spam. Learn how your comment data is processed.