# Data Structure MCQ - Graph

Q1.The time complexity to calculate the number of edges in a graph whose information instored in form of an adjacency matrix is ____________

- O(V)
- O(E2)
- O(E)
- O(V2)

Answer:- (D).

**Explanations :**As V entries are 0, a total of V^2-V entries are to be examined- in,out
- out,in
- in,total
- total,out

Answer:- (B).

**Explanations :**Row number of the matrix represents the tail, while Column number representsthe head of the edge- (n*(n-1))/2
- (n*(n+1))/2
- n*(n-1)
- n*(n+1)

Answer:- (C).

**Explanations :**Out of n*n possible values for a simple graph the diagonal values will always be zero.- 15
- 3
- 1
- 11

Answer:- (B).

**Explanations :**By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.- Depends on the number of edges
- Depends on the number of vertices
- Is independent of both the number of edges and vertices
- It depends on both the number of edges and vertices

Answer:- (C).

**Explanations :**To check if there is an edge between to vertices i and j, it is enough to see if the value of A[i][j] is 1 or 0, here A is the adjacency matrix.- Many Hamiltonian paths are possible
- No Hamiltonian path is possible
- Exactly 1 Hamiltonian path is possible
- Given information is insufficient to comment anything

Answer:- (B).

**Explanations :**For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.- 15
- 3
- 1
- 13

Answer:- (B).

**Explanations :**By euler's formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.- 28
- 64
- 256
- 56

Answer:- (D).

**Explanations :**If a graph has V vertices than every vertex can be connected to apossible of V-1 vertices- O(S1)
- O(S2)
- O(S1+S2)
- O(1)

Answer:- (A).

**Explanations :**For each check of a word of length S1, we need to follow at most S1 edges.- 24
- 21
- 25
- 16

Answer:- (C).

**Explanations :**Let one set have n vertices another set would contain 10-n vertices. Total number of edges would be n*(10-n), differentiating with respect to n, would yield the answer.Copyright © 2022 Shineskill Software Pvt. Ltd., All rights reserved.