Graph Theory MCQs | Graph Theory Multiple Choice Questions and Answers

Sports GK Questions and Answers 2024 (Latest Updated)

Awards & Honours GK Questions 2024 (Latest Updated)

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
Assam Direct Recruitment Test Series

Teacher Eligibility Test

Assam Direct Recruitment Test Series