Tree

Ankur Kulhari

Tree: is an undirected graph with properties:
Tree

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.
    Cycle_by_adding_edge

    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.
    not_connected_edge_removed

    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.
    Internal_nodes

    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

What do you think about the article?