ainfoera.com – MCQs, Mock Tests | Mathematics Mathematics MCQs Set-3

1 What is a star tree?

A A tree having a single internal vertex and n-1 leaves B A tree having n vertices arranged in a line C A tree which has 0 or more connected subtrees D A tree which contains n vertices and n-1 cycles

✅ Correct Answer: 1

2 A polytree is called _______________

A directed acyclic graph B directed cyclic graph C bipartite graph D connected graph

✅ Correct Answer: 1

3 The tree elements are called __________

A vertices B nodes C points D edges

✅ Correct Answer: 2

4 A linear graph consists of vertices arranged in a line.

A false B true C either true or false D cannot determined

✅ Correct Answer: 2

5 Two labeled trees are isomorphic if ____________

A graphs of the two trees are isomorphic B the two trees have same label C graphs of the two trees are isomorphic and the two trees have the same label D graphs of the two trees are cyclic

✅ Correct Answer: 3

6 A graph which consists of disjoint union of trees is called ______

A bipartite graph B forest C caterpillar tree D labeled tree

✅ Correct Answer: 2

7 What is a bipartite graph?

A a graph which contains only one cycle B a graph which consists of more than 3 number of vertices C a graph which has odd number of vertices and even number of edges D a graph which contains no cycles of odd length

✅ Correct Answer: 4

8 If two cycle graphs Gm and Gn are joined together with a vertex, the number of spanning trees in the new graph is ______

A m+n-1 B m-n C m*n D m*n+1

✅ Correct Answer: 3

9 A binary cycle space forms a ______ over the two element field.

A triangular graph B vector space C binary tree D hamiltonian graph

✅ Correct Answer: 2

10 If G is a simple graph with n-vertices and n>=3, the condition for G has a Hamiltonian circuit is __________

A the degree of each vertex is at most n/2 B the degree of each vertex is equal to n C the degree of every vertex is at least n+1/2 D the degree of every vertex in G is at least n/2

✅ Correct Answer: 4

11 What is a separable graph?

A A disconnected graph by deleting a vertex B A disconnected graph by removing an edge C A disconnected graph by removing one edge and a vertex D A simple graph which does not contain a cycle

✅ Correct Answer: 1

12 How many edges are there in a complete graph of order 9?

A 35 B 36 C 45 D 19

✅ Correct Answer: 2

13 How many cycles are there in a wheel graph of order 5?

A 6 B 10 C 25 D 7

✅ Correct Answer: 4

14 Topological sorting of a graph represents _______ of a graph.

A linear probing B linear ordering C quadrilateral ordering D insertion sorting

✅ Correct Answer: 2

15 A bridge can not be a part of _______

A a simple cycle B a tree C a clique with size â‰¥ 3 whose every edge is a bridge D a graph which contains cycles

✅ Correct Answer: 1

16 Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______

A subgraph B tree C hamiltonian cycle D grid

✅ Correct Answer: 2

17 G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______

A Complete bipartite graph B Hamiltonian cycle C Regular graph D Euler graph

✅ Correct Answer: 4

18 Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.

A 98 B 13 C 6 D 34

✅ Correct Answer: 3

19 What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?

A 11 B 14 C 18 D 19

✅ Correct Answer: 3

20 The minimum number of edges in a connected cyclic graph on n vertices is _____________

A n â€“ 1 B n C 2n+3 D n+1

✅ Correct Answer: 2

21 The maximum number of edges in a 8-node undirected graph without self loops is ____________

A 45 B 61 C 28 D 17

✅ Correct Answer: 3

22 Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____

A n-1 and n+1 B v and k C k+1 and v-k D k-1 and v-1

✅ Correct Answer: 4

23 A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or _______ modulo 4(for integral values of number of edges).

A 6k, 6k-1 B 4k, 4k+1 C k, k+2 D 2k+1, k

✅ Correct Answer: 3

24 Every Isomorphic graph must have ________ representation.

A cyclic B adjacency list C tree D adjacency matrix

✅ Correct Answer: 4

25 A cycle on n vertices is isomorphic to its complement. What is the value of n?

A 5 B 32 C 17 D 8

✅ Correct Answer: 1

26 How many perfect matchings are there in a complete graph of 10 vertices?

A 60 B 945 C 756 D 127

✅ Correct Answer: 2

27 A graph G has the degree of each vertex is â‰¥ 3 say, deg(V) â‰¥ 3 âˆ€ V âˆˆ G such that 3|V| â‰¤ 2|E| and 3|R| â‰¤ 2|E|, then the graph is said to be ________ (R denotes region in the graph)

A Planner graph B Polyhedral graph C Homomorphic graph D Isomorphic graph

✅ Correct Answer: 2

28 What is the grade of a planar graph consisting of 8 vertices and 15 edges?

A 30 B 15 C 45 D 106

✅ Correct Answer: 1

29 A _______ is a graph with no homomorphism to any proper subgraph.

A poset B core C walk D trail

✅ Correct Answer: 2

30 Which algorithm efficiently calculates the single source shortest paths in a Directed Acyclic Graph?

A topological sort B hash table C binary search D radix sort

✅ Correct Answer: 1

31 The _______ of a graph G consists of all vertices and edges of G.

A edge graph B line graph C path complement graph D eulerian circuit

✅ Correct Answer: 4

32 A ______ in a graph G is a circuit which consists of every vertex (except first/last vertex) of G exactly once.

A Euler path B Hamiltonian path C Planar graph D Path complement graph

✅ Correct Answer: 2

33 A trail in a graph can be described as ______________

A a walk without repeated edges B a cycle with repeated edges C a walk with repeated edges D a line graph with one or more vertices

✅ Correct Answer: 1

34 Let a graph can be denoted as ncfkedn a kind of ____________

A cycle graph B line graph C hamiltonian graph D path graph

✅ Correct Answer: 1

35 Determine the edge count of a path complement graph with 14 vertices.

A 502 B 345 C 78 D 69

✅ Correct Answer: 3

36 The sum of an n-node graph and its complement graph produces a graph called _______

A complete graph B bipartite graph C star graph D path-complement graph

✅ Correct Answer: 1

37 In a directed weighted graph, if the weight of every edge is decreased by 10 units, does any change occur to the shortest path in the modified graph?

A 209 B 65 C 57 D 43

✅ Correct Answer: 3

38 Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)?

A BFS B DFS C Binary search D Radix sort

✅ Correct Answer: 1

39 The topological sorting of any DAG can be done in ________ time.

A cubic B quadratic C linear D logarithmic

✅ Correct Answer: 3

40 If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

A Many Hamiltonian paths are possible B No Hamiltonian path is possible C Exactly 1 Hamiltonian path is possible D Given information is insufficient to comment anything

✅ Correct Answer: 2

41 Which of the given statement is true?

A All the Cyclic Directed Graphs have topological sortings B All the Acyclic Directed Graphs have topological sortings C All Directed Graphs have topological sortings D All the cyclic directed graphs hace non topological sortings

✅ Correct Answer: 4

42 What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?

A Depends on a Graph B Will always be zero C Will always be greater than zero D May be zero or greater than zero

✅ Correct Answer: 2

43 In which of the following does a Directed Acyclic Word Graph finds its application in?

A String Matching B Number Sorting C Manipulations on numbers D Pattern Printing

✅ Correct Answer: 1

44 What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?

A O(S1) B O(S2) C O(S1+S2) D O(1)

✅ Correct Answer: 1

45 In which of the following case does a Propositional Directed Acyclic Graph is used for?

A Representation of Boolean Functions B String Matching C Searching D Sorting of number

✅ Correct Answer: 1

Mathematics — Learn

Mathematics MCQs Set-3