Scribd
Upload
163 views3 pages

3 5 3 C Q 4 F 3 4 2 L 1 10

This document contains the questions and diagrams for a comprehensive exam on graph and network theory. It includes 17 questions ranging from proving properties of graphs to finding spanning trees, matchings, independent sets, and applying graph algorithms like Prim's, Dijkstra's, and depth-first search. Diagrams are provided for questions requiring graphical representations.

Uploaded by

Koustubh Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
163 views3 pages

3 5 3 C Q 4 F 3 4 2 L 1 10

This document contains the questions and diagrams for a comprehensive exam on graph and network theory. It includes 17 questions ranging from proving properties of graphs to finding spanning trees, matchings, independent sets, and applying graph algorithms like Prim's, Dijkstra's, and depth-first search. Diagrams are provided for questions requiring graphical representations.

Uploaded by

Koustubh Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 3

Birla institute of technology & Science, Pilani

II Semester 2015-16 Math F243 Graph & network Comprehensive examination


Date : 13/5/2016 Time : 3 hours Weightage : 45%

1 If G is disconnected prove compliment of G is connected . [5]

2(i) Find the minimal spanning tree in the weighted graph G through Prim s starting at vertex u write the order in
which edges are selected. Find the weight of minimal spanning tree. [8]
(ii) Find the length of shortest path from vertex a to every other vertex in the weighted graph below using Dijkstras Algo
a(tabular representation) , show final labels on all the vertices & find shortest path from a to w. [8]

f
q
3 4
c m 3 3
z
4 10 3 1
3 l 5
5 s 2
a 3
3
d w
3 3 3 7 4
4
4

u 1 v 2 y

3(i) Write a maximum Matching of G (ii) write


minimum edge covering and edge covering number
(G) [3+2]

4 (i) write (G) and a maximum independent set (ii)


write minimum vertex cover & (G) [3+2]

5Construct a connected graph G on 10 vertices in which degree


of every vertex is 3 and G has exactly two cut vertices . . Justify.
[4]

6 Find a tree on string (not degree sequence)


( 10,3,2,4,7,4,2,3,2,4,3) of length (n-2) [5]
7 Let G be a simple graph with m edges .
1 1
Prove that y (G) + 2m + [4]
2 4
8 Find the number of nonisomorphic graphs on degree
sequence (2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2) [4]

G for q4
9 Is the following graph planar?If planar find a planar drawing. If non planar prove through kuratwaski theorem[4]
\

10 Find number of labelled Spanning trees of K3 , 10 with help of matrix tree theorem [8]

11 Prove A independent set of vertices is maximal independent iff it is a dominating set. [8]

12If G is a simple planar connected graph on n vertices . Does G contain a vertex of degree at most
degree 4. Explain your answer. [8]

13 Is there a planar graph G on n vertices and 3n -6 edges in which every vertex has degree 4 ?
Justify your answer. [4]

14 For a graph G , prove (n/y(G)) (G) [4]

15 Define vertex independence number (G) and vertex covering number (G)prove for a simple
connected graph G on n2 vertices (G)+ (G)=n [10]

16 Are graphs isomorphic? Explain [5]


17 Find a DFS directed spanning tree (systematic DFS ) mark that on G starting at vertex . Find dfi(v)
& l(v) for all vertices label the vertices with (dfi, l(v)) pair in G . [10]

G for q17

G for question on
planar
G & G for q 16

You might also like