Help authour, Buy PDF Ebook >>>Click Here<<<
Data Structure Questions and Answers-Incidence Matrix and Graph Structured Stack
Question 1 |
Incidence matrix and Adjacency matrix of a graph will always have same dimensions?
True | |
False |
Question 1 Explanation:
For a graph having V vertices and E edges, Adjacency matrix have V*V elements while Incidence matrix have V*E elements.
Question 2 |
The column sum in an incidence matrix for a simple graph is .....
depends on number of edges | |
always greater than 2 | |
equal to 2 | |
equal to the number of edges |
Question 2 Explanation:
For every edge only the vertices with which it is connected would have the value 1 in the matri, x as an edge connects two vertices sum will always be 2.
Question 3 |
What are the dimensions of an incidence matrix?
Number of edges*number of edges | |
Number of edges*number of vertices | |
Number of vertices*number of vertices | |
None of the mentioned statements |
Question 3 Explanation:
Columns may represent edges and vertices may be represented by the rows.
Question 4 |
The column sum in an incidence matrix for a directed graph having no self loop is .....
0 | |
1 | |
2 | |
equal to the number of edges |
Question 4 Explanation:
Under every edge column there would be either all 0 values or a pair of -1 and +1 value exists.
Question 5 |
Time complexity to check if an edge exists between two vertices would be .....
O(V*V) | |
O(V+E) | |
O(1) | |
O(E) |
Question 5 Explanation:
We have to check for all edges, in the worst case the vertices will have no common edge.
There are 5 questions to complete.