B.Sc. (E.C.S.) I (Semester (CBCS) Examination, 2018
Mathematics (Paper VI)
Discrete Structure
Day and Date Saturday, 3-11-2018 Max. Marks 70
Time 10.30 a.m. to 1.00 p.m.
Instructions All questions are compulsory.
Figures to the right indicate full marks.
Use of calculator is allowed.
1. Choose correct alternative for each of the following. 14
The degree of each vertex in a complete graph K6 is
10 15 5 6
In adjacency matrix of graph if all the diagonal elements are 0 and
non-diagonal elements are zero or 1 then graph G is graph.
null multi complete none of these
A walk in which no vertex is repeated is called as
Path Trial Circuit Tour
algorithm is used to find shortest spanning tree.
Dijkstar's Fleury's
Warshall's None of these
A binary tree has always number of vertices.
even odd any infinite
A graph G which have parallel edges but no loop is called as
graph.
simple multi pseudo regular
If 37, 23 and 48 then
108 62
12 cannot be determined
The number of edges in a graph with 8 vertices each of degree 4
16 4 8 32
A connected graph G is Eulerian if degree of each vertex in G is
same prime even odd
10) Order of incidence matrix of a graph having 4 vertices and 7 edges is
4×7 7×4 4×4 7×7
11) is a particular case of Hamiltonian graph.
Travelling salesman problem Chinese postman problem
Both a and b None of the above
12) If a simple graph G is isomorphic to its own complement then the graph G
is called as graph.
Isomorphic Complement
Self complementary None of these
13) A trail which covers all the edges of a connected graph G is called as
Eulerian circuit Eulerian trail
Closed trail Hamiltonian trail
14) The complement of a complete graph is graph.
Complete Simple Null None of these
2. Answer the following (any four) 8
State principle of inclusion-exclusion for three sets.
Define vertex disjoint subgraphs and edge disjoint subgraphs.
Define linear recurrence relation with constant coefficient of order K.
Draw the graphs K4, 2 and K3, 2.
Define a complete graph with suitable example.
Answer the following (any two). 6
Define Hamiltonian path, trail and Eulerian Trail.
Define Bipartite graph and complete Bipartite graph.
Define complement of a graph. Hence draw complement of the following
graph.
3. Answer the following (any two) 8
Find the adjacency and incidence matrix for the following graph.
Write a brief note on Konigsberg's seven bridge problem.
Find eccentricity of every vertex of following tree. Also find its centre
and radius.
Answer the following (any one). 6
Apply Dijkstar's algorithm to a graph given below to find the shortest
path from a to all.
Find all Fundamental circuits and cut sets for the following connected
graph G w.r. to the spanning tree T.
4. Answer the following (any two) 10
Show that the following two graphs are isomorphic.
Explain the Chenese postman problem.
From the following graph, draw one pair of each of the following
subgraphs.
Vertex disjoint
II) Edge disjoint
III) Neither vertex disjoint nor edge disjoint.
Answer the following (any one). 4
Find and draw G1 × G2 for the following pairs of graphs.
Give an example of graph which is
Eulerian but not Hamiltonian
Neither Hamiltonian nor Eulerian
5. Answer the following (any two). 14
Define spanning tree and by using Kruskal's algorithm find a shortest
spanning tree and its weight of the following graph.
State and prove principle of Inclusion-Exclusion for three sets.
By starting with vertex solve the Travelling salesman problem for the
graph.