Question 5

 (i) Directed Graph: In a directed graph, each edge has a sense of direction from u to v
and is written as an ordered pair <u,v> or u→v.
(ii) Undirected Graph: In an undirected graph, an edge has no sense of direction and is
written as an unordered pair {u,v} or u<->v.
(iii) Degree of Vertex: The number of edges with one endpoint on a given vertex is
called that vertex's degree. In a directed graph, the number of edges that point to a given
vertex is called its in-degree, and the number that point from it is called its out-degree.
(iv) Null Graph: A graph which containing only isolated nodes is called null graph.
In a graph, a node which is not adjacent to any other node is called an isolated node.    
            

Graphs by Adjacency Matrices.
A graph G= can be represented by a |V|*|V| adjacency matrix A. If G is directed,
Aij=true if and only if <vi,vj> is in E. There are at most |V|2 edges in E.
1 2 3 4 5 6
1 T
2 T
3 T
4 T T T
5 T T T
6 T
Adjacency Matrix of Directed Graph.
If G is undirected, Aij=Aji=true if {vi,vj} is in E and Aij=Aji=false otherwise. In this case
there are at most |V|*(|V|+1)/2 edges in E, A is symmetric and space can be saved by
storing only the upper triangular part Aij for i>=j.
1 2 3 4 5 6
1 T T T
2 T T T T
3 T T
4 T T T T
5 T T T
6 T T
Adjacency Matrix of Undirected Graph.
1 2 3 4 5 6
1 T T T
2 T T T
3 T
4 T
5 T
6
Upper Triangular Adjacency Matrix of Undirected Graph.
An adjacency matrix is easily implemented as an array.
Both directed and undirected graphs may be weighted. A weight is attached to each
edge. This may be used to represent the distance between two cities, the flight time, the
cost of the fare, the electrical capacity of a cable or some other quantity associated with
the edge. The weight is sometimes called the length of the edge, particularly when the
graph represents a map of some kind. The weight or length of a path or a cycle is the
sum of the weights or lengths of its component edges. Algorithms to find shortest paths
in a graph are given later.
The adjacency matrix of a weighted graph can be used to store the weights of the edges.
If an edge is missing a special value, perhaps a negative value, zero or a large value to
represent "infinity", indicates this fact.
1 2 3 4 5 6
1 4
2 4
3 3
4 3 2 3
5 4 5 1
6 5
Adjacency Matrix of Weighted Directed Graph.
1 2 3 4 5 6
1 4 3 5
2 4 3 4 4
3 3 2
4 3 4 2 3
5 4 3 1
6 5 1
Adjacency Matrix of Weighted Undirected Graph.
1 2 3 4 5 6
1 4 3 5
2 3 4 4
3 2
4 3
5 1
6
Upper Triangular Adjacency Matrix of Weighted Undirected Graph.
It is often the case that if the weights represent distances then the natural distance from
vi to itself is zero and the diagonal elements of the matrix are given this value.
A weighted adjacency matrix is easily defined in any imperative programming
language.
A graph is complete if all possible edges are present. It is dense if most of the possible
edges are present. It is sparse if most of them are absent, |E|<<|V|2. Adjacency matrices
are space efficient for dense graphs but inefficient for sparse graphs when most of the
entries represent missing edges. Adjacency lists use less space for sparse graphs.
Graphs by Adjacency Lists.
In a sparse directed graph, |E|<<|V|2. In a sparse undirected graph |E|<<|V|*(|V|-1)/2.
Most of the possible edges are missing and space can be saved by storing only those
edges that are present, using linked lists.
Consider the weighted directed case.
An edge <vi,vj> is placed in a list associated with vi. The edge is represented by the
destination vj and the weight.
1:--------->2,4:nil
2:--------->4,4:nil
3:--------->2,3:nil
4:--------->1,3:----->3,2:----->5,3:nil
5:--------->4,5:----->6,1:nil
6:--------->1,5:nil
Adjacency Lists for Weighted Directed Graph.
Consider now the undirected case:
1:--------->2,4:----->4,3:----->6,5:nil
2:--------->1,4:-----:3,3:----->4,4:----->5,4:nil
3:--------->2,3:----->4,2:nil
4:--------->1,3:----->2,4:----->3,2:----->5,3:nil
5:--------->2,4:----->4,3:----->6,1:nil
6:--------->1,5:----->5,1:nil
Adjacency Lists for Weighted Undirected Graph.
As before, half the space can be saved by only storing {vi,vj} for i>=j:
1:--------->2,4:----->4,3:----->6,5:nil2:--------->3,3:----->4,4:----->5,4:nil
3:--------->4,2:nil
4:--------->5,3:nil
5:--------->6,1:nil
6:nil
Reduced Adjacency Lists for Weighted Undirected Graph.
Adjacency lists can be defined using records (structs) and pointers.
Note that some questions, such as "are vi and vj adjacent in G", take more time to
answer using adjacency lists than using an adjacency matrix as the latter gives random
access to all possible edges.
            

(i) Height of the Tree: The height of a node is the longest path from that node to its
leaves. The height of a tree is the height of the root.
(ii) Binary tree: In binary tree, each node has zero, one, or two children.