DIGRAPH

       

                    A  graph  G consists of a non empty set v called the set of nodes(points, vertices)of the graph ,a set E which is the set of edges of the graph , and the mapping from the set of edges  E to a set of pair of elements of V. Assume that the no. of element in V,E are finite such that G=(V,E).Let an edge xÎE is thus associated with a pair of nodes (u, v) where u, vÎV, then we say that the edge x connects or joins the node u and v. Any two nodes which are connected by an edge in a graph is called adjacent nodes.

 

                    In a graph G=(V,E) , an edge which is directed from one node to another is called a directed edge, while an edge which has no specific direction is called an undirected edge. A graph in which every edge is directed is called a directed graph, or a digraph. A graph in which every edge is undirected  is called an undirected graph . If  some of the edges are directed and some are undirected in a graph, then the graph is a mixed graph.

 

                   In the diagrams the directed edges are shown by means of arrows which also show the directions. The graphs in fig 1 b and e are directed graphs, c and f are undirected graph while d is a mixed graph,  fig 1a can be  considered as either directed or undirected.

 

 

          

                 v1     (a)      v2                     v1    (b)          v2         v1      (c)       v2

             

               1                                                                1                                               

   

2                                                3                2                                                                                  1

 


                          4                                                            4                 3                         2                                                3

 

       

                 (d)                                          (e)                                         (f)       4

 

                                        figure 1

 

 

 

 

Let  (V, E) be a graph and let xÎE be a directed graph associated  with ordered pair of nodes (u, v), then the edge x is said to be initiating or originating in the node u and terminating in the node v. the n9odes u and v are called the initial and the terminal nodes of the edge x. x joins nodes u and v  whether it be directed or undirected  is said to be incident to the nodes u and v.

 

          In cases of certain digraphs  as well as undirected graphs  certain pair of nodes are joined by more than one edge such edges are called  parallel .  any graph which contains parallel  edges are called multigraph. If there are no more than one directed edge between a pair of nodes in the case of a digraph  then such a graph is  called a simple graph.

 

 

ACYCLIC  GRAPHS    

 

 

          A  path which originates and ends in the same node is called a cycle(circuit).A cycle is called elementary if it does not traverse through any node more than once.A simple digraph which does not have any cycles is known as acyclic . Naturally such graphs cannot have any loops. A directed tree is an acyclic digraph which has one node called its root node, with indegree 0,while all other nodes have indegree 1.Every directed tree must have atleast one node. An isolated node is also called a directed tree.

 

In a directed tree,any node with outdegree 0 is called the terminal node or a leaf, all other nodes are called branch nodes. The level of any node is the length of its path from the root. The level of the root of a directed tree is 0, while the level of any  node is equal to its distance  from the root. All the paths in a directed tree are elementary and the lengths of a path from any node to another node , if such a path exists, is the disatance  between the nodes, because a directed tree  is acyclic.

 

Figure 2 shows directed tree..The directed tree of our example has 2 nodes at level 1, five nodes at  level 2 and three nodes at level 3.Figure shows  the way the trees grow from its root down and ending in the leaves at different leaves at different levels

                                                       V0       

                            

                                V1                                v7

 

 


                      V2                   v3         v4       v8       v9

 

 


 

                      V5             v6                                                                v7

 

                                   Figure 2