Engineering Questions with Answers - Multiple Choice Questions

Home » MCQs » Aeronautical Engineering » Data Structure MCQ – Incidence Matrix and Graph Structured Stack

# Data Structure MCQ – Incidence Matrix and Graph Structured Stack

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

a) True

b) False

**
View Answer**

Answer: b

Explanation: For a graph having V vertices and E edges, Adjacency matrix have V*V elements while Incidence matrix have V*E elements.

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

**
View Answer**

Answer: c

Explanation: 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.

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)

**
View Answer**

Answer: b

Explanation: Columns may represent edges and vertices may be represented by the rows.

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

Answer: a

Explanation: Under every edge column there would be either all 0 values or a pair of -1 and +1 value exists.

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

Answer: d

Explanation: We have to check for all edges, in the worst case the vertices will have no common edge.

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

**
View Answer**

Answer: a

Explanation: Two graphs are isomorphic if their Incidence Matrices differ only by permutation of columns and rows.

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

**
View Answer**

Answer: a

Explanation: Every column of the incidence matrix may contain only +1 and -1 as non zero entries rank would be less than n.

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

**
View Answer**

Answer: c

Explanation: Path ADE, BDE and BCE are possible.

A Graph Structured Stack is a _____________

a) Undirected Graph

b) Directed Graph

c) Directed Acyclic Graph

d) Regular Graph

**
View Answer**

Answer: c

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

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

**
View Answer**

Answer: c

Explanation: Every Stack of the Graph Structured Stack represents a path, each path starts with the source vertex and ends with the sink vertex.

Graph Structured Stack finds its application in _____________

a) Bogo Sort

b) Tomita’s Algorithm

c) Todd–Coxeter algorithm

d) Heap Sort

**
View Answer**

Answer: b

Explanation: Tomita’s is a parsing algorithm which uses Graph Structured Stack in its implementation.

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

**
View Answer**

Answer: b

Explanation: The answer would depend on the intermediate vertices also.