Data Structure Multiple Choice Questions on “Incidence Matrix and Graph Structured Stack”.
1. Incidence matrix and Adjacency matrix of a graph will always have same dimensions?
a) True
b) False
Answer: b
Clarification: For a graph having V vertices and E edges, Adjacency matrix have V*V elements while Incidence matrix have V*E elements.
2. The column sum in an incidence matrix for a simple graph is __________
a) depends on number of edges
b) always greater than 2
c) equal to 2
d) equal to the number of edges
Answer: c
Clarification: For every edge only the vertices with which it is connected would have the value 1 in the matrix, as an edge connects two vertices sum will always be 2.
3. 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) Number of edges * (1⁄2 * number of vertices)
Answer: b
Clarification: Columns may represent edges and vertices may be represented by the rows.
4. 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
Clarification: Under every edge column there would be either all 0 values or a pair of -1 and +1 value exists.
5. 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
Clarification: We have to check for all edges, in the worst case the vertices will have no common edge.
6. 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
Answer: a
Clarification: Two graphs are isomorphic if their Incidence Matrices differ only by permutation of columns and rows.
7. 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
Clarification: Every column of the incidence matrix may contain only +1 and -1 as non zero entries rank would be less than n.
8. In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack.
a) 1
b) 2
c) 3
d) 4
Answer: c
Clarification: Path ADE, BDE and BCE are possible.
9. A Graph Structured Stack is a _____________
a) Undirected Graph
b) Directed Graph
c) Directed Acyclic Graph
d) Regular Graph
Answer: c
Clarification: A Graph Structured Stack is a Directed Acyclic Graph with each path representing a stack.
10. 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) Source – 4, Sink – 1,8
Answer: c
Clarification: Every Stack of the Graph Structured Stack represents a path, each path starts with the source vertex and ends with the sink vertex.
11. Graph Structured Stack finds its application in _____________
a) Bogo Sort
b) Tomita’s Algorithm
c) Todd–Coxeter algorithm
d) Heap Sort
Answer: b
Clarification: Tomita’s is a parsing algorithm which uses Graph Structured Stack in its implementation.
12. 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
Answer: b
Clarification: The answer would depend on the intermediate vertices also.