81. What are the dimensions of an incidence matrix?
a. Number of edges*number of edges
b. Number of edges*number of vertices
c. Number of vertices*number of vertices
d. None of the mentioned statements
Answer: (b).Number of edges*number of vertices

82. The column sum in an incidence matrix for a directed graph having no self loop is __________
a. 0
b. 1
c. 2
d. equal to the number of edges
Answer: (a).0

83. Time complexity to check if an edge exists between two vertices would be ___________
a. O(V*V)
b. O(V+E)
c. O(1)
d. O(E)
Answer: (d).O(E)

84. The graphs G1 and G2 with their incidences matrices given are Isomorphic.

e1 e2 e3 e4 e5 e6
v1 1 0 0 0 0 0
v2 1 1 0 0 0 1
v3 0 1 1 0 1 0
v4 0 0 1 1 0 0
v5 0 0 0 1 1 1



e1 e2 e3 e4 e5 e6
v1 0 0 1 0 0 0
v2 1 0 1 0 1 0
v3 1 1 0 1 0 0
v4 0 1 0 0 0 1
v5 0 0 0 1 1 1
a. True
b. False
c. May be
d. Can't say
Answer: (a).True

85. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?
a. n-1
b. values greater than n are possible
c. values less than n-1 are possible
d. insufficient Information is given
Answer: (a).n-1

86. A Graph Structured Stack is a _____________
a. Undirected Graph
b. Directed Graph
c. Directed Acyclic Graph
d. Regular Graph
Answer: (c).Directed Acyclic Graph

87. If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?
a. Source – 1, 8 Sink – 7,4
b. Source – 1 Sink – 8,4
c. Source – 1, 8 Sink – 4
d. None of the Mentioned
Answer: (c).Source – 1, 8 Sink – 4

88. Graph Structured Stack finds its application in _____________
a. Bogo Sort
b. Tomita’s Algorithm
c. Todd–Coxeter algorithm
d. All of the mentioned
Answer: (b).Tomita’s Algorithm

89. If in a DAG N sink vertices and M source vertices exists, then the number of possible stacks in the Graph Structured Stack representation would come out to be N*M.
a. True
b. False
c. May be
d. Can't say
Answer: (b).False

90. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________
a. O(E)
b. O(V*V)
c. O(E+V)
d. O(V)
Answer: (c).O(E+V)