Page 279 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 13.5 Summary

z Graphs provide in excellent way to describe the essential features of many applications.

z Graphs are mathematical structures and are found to be useful in problem solving. They
may be implemented in many ways by the use of different kinds of data structures.
z Graph traversals, Depth First as well as Breadth First, are also required in many
applications.
z Existence of cycles makes graph traversal challenging, and this leads to fi nding some
kind of acyclic subgraph of a graph. That is we actually reach at the problems of fi nding a

shortest path and of finding a minimum cost spanning tree problems.
13.6 Keywords

Adjacent: Two vertices in an undirected graph are called adjacent

Edges: A graph G consists of a set V, whose members are called the vertices of G, together with a
set E of pairs of distinct vertices from V. These pairs are called the edges of G.

Free Tree: A free tree is defined as a connected undirected graph with no cycles.
Graph: Graph is a mathematical structure and fi nds its application in many areas of interest in
which problems need to be solved using computers.
Undirected Graph: If the pairs are unordered, then G is called an undirected graph

13.7 Self Assessment

Fill in the blanks:

1. A graph may have many ...............................
2. The weight of a tree is just the sum of weights of its .............................
3. The ............................. ends when no more paths are found.
4. In an undirected graph, pair of vertices representing any edge is .............................
5. In a Digraph the path is called a directed path and a cycle as ...............................
State whether the following statements are true or false:

6. E.W. Dijkstra developed an algorithm to determine the shorted path between two nodes in
a graph.
7. The algorithm is not equally applicable to a graph, a digraph, or even to a mixed graph
with only some of its sides directed.
8. A cycle is not a path in which first and last vertices are the same.

9. A good deal of nomenclature is associated with graphs.
10. In a Digraph the path is called a directed path and a cycle as directed cycle.

13.8 Review Questions

1. What do you mean by shortest path?
2. Find out the minimum number of edges in a strongly connected diagraph on n vertices.

274 LOVELY PROFESSIONAL UNIVERSITY