This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Incidence Matrix and Graph Structured Stack”.

**1. A Graph Structured Stack is a _____________**

A) Undirected Graph

B) Directed Graph**C) Directed Acyclic Graph**

D) Regular Graph

Explanation: A Directed Acyclic Graph with each path representing a stack is known as a Graph Structured Stack.

**2. 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

Explanation: Every Stack in the Graph Structured Stack represents a path, with the source vertex at the beginning and the sink vertex at the end.

**3. Graph Structured Stack finds its application in _____________**

A) Bogo Sort**B) Tomita’s Algorithm**

C) Todd–Coxeter algorithm

D) Heap Sort

Explanation: Tomita’s is a parsing algorithm that is implemented using Graph Structured Stack.

**4. 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**

Explanation: The response will also be determined by the intermediate vertices.

**5. 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

Explanation: If the only difference between two graphs’ Incidence Matrices is the permutation of columns and rows, they are said to be isomorphic.

**6. 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

Explanation: Since non-zero entries rank less than n, each column of the incidence matrix can only contain +1 and -1.

**7. Incidence matrix and Adjacency matrix of a graph will always have same dimensions?**

A) True**B) False**

Explanation: Adjacency matrix has V*V elements for a graph with V vertices and E edges, while Incidence matrix has V*E elements.

**8. 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

Explanation: Only the vertices in which an edge is connected will have a value of 1 in the matrix, since an edge connects two vertices and their number would always be 2.

**9. 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)

Explanation: Edges could be represented by columns, while vertices could be represented by rows.

**10. 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

Explanation: There will be either all 0 values or a pair of -1 and +1 values under each edge column.

**11. 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)**

Explanation: All edges must be checked; otherwise, the vertices would have no common edge.

**12. 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

Explanation: Path ADE, BDE and BCE are possible.

If a vertex is incident upon an edge, the incidence matrix of a graph is the (0,1)-matrix, which has a row for each vertex and a column for each edge. (p. 135) (Skiena 1990). Some authors, on the other hand, define the incidence matrix as the transpose of this, with one column for each vertex and one row for each edge. A graph’s adjacency matrix should be differentiated from its incidence matrix, which is a separate matrix representation whose elements indicate whether or not vertex–edge pairs are incident, and its degree matrix, which includes details about each vertex’s degree.