# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

## Data Structure Questions and Answers-Incidence Matrix and Graph Structured Stack

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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.