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 
View Answer Report Discuss Too Difficult! Search Google 
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 
View Answer Report Discuss Too Difficult! Search Google 
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) 
View Answer Report Discuss Too Difficult! Search Google 
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 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).True

85.  If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix? 
a.  n1 
b.  values greater than n are possible 
c.  values less than n1 are possible 
d.  insufficient Information is given 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).n1

86.  A Graph Structured Stack is a _____________ 
a.  Undirected Graph 
b.  Directed Graph 
c.  Directed Acyclic Graph 
d.  Regular Graph 
View Answer Report Discuss Too Difficult! Search Google 
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 
View Answer Report Discuss Too Difficult! Search Google 
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 
View Answer Report Discuss Too Difficult! Search Google 
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 
View Answer Report Discuss Too Difficult! Search Google 
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) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).O(E+V)
