UNIT -04
Graph Theory
UNIT -04/ LECTURE- 01
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 348-356}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Define What is Graph? |
June 2006 |
2
|
|
Q 2 |
Define the following (i) Multi Graph (ii) Pendant vertex (iii)Isomorphic graphs |
June 2013 |
7 |
|
Q. 3 |
Define the following (i) Regular Graph (ii) Homeomorphic graph |
Dec 2011 |
4 |
SUBGRAPHS, WALKS, PATHS, CIRCUITS AND CYCLES
UNIT- 04/ LECTURE-02
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 357-359}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Define walk path and circuit in a directed graph? |
June 2007 |
10
|
|
Q 2 |
Prove that the maximum number of edges in a simple graph with n vertices is n(n-1)/2 |
Dec 2008, June 2011, Dec 2013 |
7 |
DIFFERENT TYPES OF GRAPHS, SHORTEST PATH IN WEIGHTED GRAPHS
UNIT- 04/ LECTURE- 03
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 364-366}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Prove that a simple graph with n vertices and k components can have at most (n-k)(n-k+1)/2 edges |
June 2010,June 2012 |
7
|
|
Q 2 |
Define weighted graph |
June 2013 |
2 |
|
Q. 3 |
Define Bipartite graph |
Dec 2003 |
2 |
|
|
Write an algorithm for shortest path in weighted graph and use it to find shortest path from a to z in the graph b 2
4 4
7 8 3 9
6
|
June 2004 |
7 |
|
Q.4 |
Write an algorithm to find the shortest path in a weighted graph |
June 2014 |
7 |
PROBLEMS ON SHORTEST PATH IN WEIGHTED GRAPHS
UNIT- 04/ LECTURE -04
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 365-370}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Find shortest path in weighted graph and use it to find shortest path from a to z in graph b 7 d
1
a z 6
c 1 e
|
Dec 2012 |
7
|
|
Q 2 |
Use Dijkstra algorithm to find the shortest path between a to z in this graph
2 2 1
a 2 7 3 4
|
June 2010 |
7 |
EULERIAN PATH, CIRCUITS AND GRAPHS, HAMILTONIAN PATHS
UNIT -04/ LECTURE -05
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 371-373}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Determine shortest path between a and z
22 4 2 20 4
16 7 10 3 9
d 6 f |
June 2011 |
10
|
|
Q 2 |
Define Eulerian path |
June 2006, Dec 2013 |
2 |
|
Q. 3 |
Define Euler graph |
Dec 2013, June 2014 |
2 |
|
Q. 4 |
Define Hamiltonian path and circuits |
June 2013 |
4 |
OPERATIONS ON GRAPH, DIRECTED GRAPH
UNIT-04/ LECTURE -06
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 374-378}
MATRIX REPRESENTATION OF GRAPHS
UNIT- 04/ LECTURE -07
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 382-386}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
||||||
|
Q.1 |
Write the adjacency matrix of the graph
v1 v2 |
Dec 2012 |
7
|
||||||
|
Q 2 |
Find the adjacency matrix of digraph e1
e4
d e6 c e7 |
Dec 2010 |
7 |
PLANAR GRAPH
UNIT- 04/ LECTURE-08
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 389-392}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Write down the adjacency and incidence matrix of the graph V1 e7 v3
V2e3 e5 e9 V4 |
Dec 2011 |
7 |
|
Q 2 |
Define Planar graph |
Dec 2002,2003,2004 |
2 |
EULER’s FORMULA, GRAPH COLORING AND CHROMATIC NUMBER
UNIT- 04/ LECTURE- 09
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 394-399}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Explain Graph coloring and chromatic numbers |
June 2013 |
4
|
|
Q.2 |
Show that every tree with two or more vertices is 2-chromaic |
June 2014 |
3 |
UNIT- 04/ LECTURE- 10
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 394-399}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Prove that in a graph G with n- vertices always has a Hamiltonian path if the sum of degrees of every pairs of vertices vi, vj in G satisfies the condition d(vi) + d(vj) >= n-1 |
June 2013 |
4
|