JOIN ADRE 2.0 Telegram Group

Graph Theory MCQs | Graph Theory Multiple Choice Questions and Answers

Questions
1 A graph is a collection of.... ?
A Row and columns
B Vertices and edges
C Equations
D None of these

Answer: Vertices and edges
2 The degree of any vertex of graph is .... ?
A The number of edges incident with vertex
B Number of vertex in a graph
C Number of vertices adjacent to that vertex
D Number of edges in a graph

Answer: The number of edges incident with vertex
Advertisement
Article and Schedule Quiz Start Test!

DOWNLOAD CURRENT AFFAIRS PDF FROM APP

3 A graph with no edges is known as empty graph. Empty graph is also known as... ?
A Trivial graph
B Regular graph
C Bipartite graph
D None of these

Answer: Trivial graph
4 If the origin and terminus of a walk are same, the walk is known as... ?
A Open
B Closed
C Path
D None of these

Answer: Closed
5 Radius of a graph, denoted by rad(G) is defined by.... ?
A max {e(v): v belongs to V }
B min { e(v): v belongs to V}
C max { d(u,v): u belongs to v, u does not equal to v }
D min { d(u,v): u belongs to v, u does not equal to v }

Answer: max {e(v): v belongs to V }
6 A graph G is called a ..... if it is a connected acyclic graph
A Cyclic graph
B Regular graph
C Tree
D Not a graph

Answer: Tree
7 A graph is a collection of
A Row and columns
B Vertices and edges
C Equations
D None of these

Answer: Vertices and edges
8 How many relations are there on a set with n elements that are symmetric and a set with n elements that are reflexive and symmetric ?
A 2n(n+1)/2 and 2n.3n(n–1)/2
B 3n(n–1)/2 and 2n(n–1)
C 2n(n+1)/2 and 3n(n–1)/2
D 2n(n+1)/2 and 2n(n–1)/2

Answer: 2n(n+1)/2 and 2n(n–1)/2
9 In a graph if e=(u, v) means
A u is adjacent to v but v is not adjacent to u
B e begins at u and ends at v
C u is processor and v is successor
D both b and c

Answer: both b and c
10 A minimal spanning tree of a graph G is
A A spanning sub graph
B A tree
C Minimum weights
D All of above

Answer: All of above
11 A partial ordered relation is transitive, reflexive and
A Antisymmetric
B Bisymmetric
C Anti reflexive
D Asymmetric

Answer: Antisymmetric
12 A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are
A greater than n–1
B less than n(n–1)
C greater than n(n–1)/2
D less than n2/2

Answer: greater than n–1
13 A vertex of a graph is called even or odd depending upon
A Total number of edges in a graph is even or odd
B Total number of vertices in a graph is even or odd
C Its degree is even or odd
D None of these

Answer: Its degree is even or odd
14 The expression a+a c is equivalent to
A a
B a+c
C c
D 1

Answer: a+c
15 A graph with no edges is known as empty graph. Empty graph is also known as
A Trivial graph
B Regular graph
C Bipartite graph
D None of these

Answer: Trivial graph
16 A continuous non intersecting curve in the plane whose origin and terminus coincide
A Planer
B Jordan
C Hamiltonian
D All of these

Answer: Jordan
17 A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are
A more than n
B more than n+1
C more than (n+1)/2
D more than n(n-1)/2

Answer: more than n(n-1)/2
18 Which of the following pair is not congruent modulo 7?
A 10, 24
B 25, 56
C -31, 11
D -64, -15

Answer: 25, 56
19 The maximum degree of any vertex in a simple graph with n vertices is
A n–1
B n+1
C 2n–1
D n

Answer: n–1
20 Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true ?
A Weight (u, v) <= 12
B Weight (u, v) = 12
C Weight (u, v) >= 12
D Weight (u, v) > 12

Answer: Weight (u, v) >= 12

ADRE 2.0 FULL LENGTH MOCK TEST

Take Mock Tests

Missiles Mock Test Start Test!
SSC MTS Mock Test Start Test
IBPS CLERK MOCK TEST Start Test
SSC MTS 2022 JULY 26 Shift 1 (ENGLISH) Start Test!
SSC GD Previous Year Paper 2021 Nov 17 Shift - I (Hindi) Start Test!
SSC CGL Tier - 1 PYP 2022 April 21 Shift- 1 (ENGLISH) Start Test!
MPSC PAPER I MOCK TEST 1 (ENGLISH) Start Test!
IB Security Assistant Mock test 1 (english) Start Test!
UP POLICE CONSTABLE MOCK TEST 1 Start Test!
DELHI POLICE CONSTABLE MOCK TEST 1 (HINDI) Start Test!
Advertisement
Assam Direct Recruitment Test Series