Graph Theory Objective type Questions and Answers

21 How many onto (or surjective) functions are there from an n-element (n => 2) set to a 2-element set?

A 2n

B 2n - 1

C 2n - 2

D 2(2n – 2)

View Answer

Answer: 2n - 2

22 Hasse diagram are drawn

A Partially ordered sets

B Lattices

C Boolean algebra

D None of these

View Answer

Answer: Partially ordered sets

23 In how many ways can 5 balls be chosen so that 2 are red and 3 are black

A 910

B 990

C 970

D None of these

View Answer

Answer: 990

24 Circle has ____________

A No vertices

B Only 1 vertex

C 8 vertices

D None of these

View Answer

Answer: No vertices

25 The proposition ~qvp is equivalent to

A p?q

B q?p

C p?q

D p?q

View Answer

Answer: q?p

26 If B is a Boolean Algebra, then which of the following is true

A B is a finite but not complemented lattice

B B is a finite, complemented and distributive lattice

C B is a finite, distributive but not complemented lattice

D B is not distributive lattice

View Answer

Answer: B is a finite, complemented and distributive lattice

27 If R is a relation “Less Than” from A = {1,2,3,4} to B = {1,3,5} then RoR-1 is

A {(3,3), (3,4), (3,5)}

B {(3,1), (5,1), (3,2), (5,2), (5,3), (5,4)}

C {(3,3), (3,5), (5,3), (5,5)}

D {(1,3), (1,5), (2,3), (2,5), (3,5), (4,5)}

View Answer

Answer: {(3,3), (3,5), (5,3), (5,5)}

28 The number of distinguishable permutations of the letters in the word BANANA are,

A 60

B 36

C 20

D 10

View Answer

Answer: 60

29 Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to

A 3

B 4

C 5

D 6

View Answer

Answer: 6

30 A graph is tree if and only if

A Is planar

B Contains a circuit

C Is minimally

D Is completely connected

View Answer

Answer: Is minimally

31 How many different words can be formed out of the letters of the word VARANASI?

A 64

B 120

C 40320

D 720

View Answer

Answer: 720

32 Suppose v is an isolated vertex in a graph, then the degree of v is

A 0

B 1

C 2

D 3

View Answer

Answer: 0

33 The complete graph with four vertices has k edges where k is

A 3

B 4

C 5

D 6

View Answer

Answer: 6

34 Which one of the following statements is incorrect ?

A The number of regions corresponds to the cyclomatic complexity

B Cyclometric complexity for a flow graph G is V(G) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph

C Cyclometric complexity for a flow graph G is V(G) = E–N+2, where E is the number of edges & N is the number of nodes in the flow graph

D Cyclometric complexity for a flow graph G is V(G) = P + 1, where P is the number of predicate nodes contained in the flow graph G

View Answer

Answer: Cyclometric complexity for a flow graph G is V(G) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph

35 Choose the most appropriate definition of plane graph

A A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices

B A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non - empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y

C A simple graph which is Isomorphic to Hamiltonian graph

D None of these

View Answer