Data Structures :: Graphs

Home > Technical Aptitude > Data Structures > Graphs > General Questions

NA
SHSTTON
52
Solv. Corr.
41
Solv. In. Corr.
93
Attempted
0 M:0 S
Avg. Time

1 / 12

Choose the correct option.

Which of the following is an invalid path for the following graph?


comvolt-written-graph-1

AC B A

BC D E F G

CC D A C B A

DC D A

Answer: Option C

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
47
Solv. Corr.
68
Solv. In. Corr.
115
Attempted
2 M:10 S
Avg. Time

2 / 12

Choose the correct option.

An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?


AO(n)

BO(e)

CO(e+n)

DO(e^2)

Answer: Option C

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
21
Solv. Corr.
76
Solv. In. Corr.
97
Attempted
0 M:0 S
Avg. Time

3 / 12

Choose the correct option.

A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are


Amore than n

Bmore than n+1

Cmore than (n+1)/2

Dmore than n(n-1)/2

Answer: Option D

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
52
Solv. Corr.
69
Solv. In. Corr.
121
Attempted
0 M:0 S
Avg. Time

4 / 12

Choose the correct option.

The maximum degree of any vertex in a simple graph with n vertices is


An-1

Bn+1

C2n-1

Dn

Answer: Option A

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
20
Solv. Corr.
77
Solv. In. Corr.
97
Attempted
0 M:0 S
Avg. Time

5 / 12

Choose the correct option.

A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are


Agreater than n-1

Bless than n(n-1)

Cgreater than n(n-1)/2

Dless than (n^2)/2

Answer: Option A

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
20
Solv. Corr.
51
Solv. In. Corr.
71
Attempted
0 M:0 S
Avg. Time

6 / 12

Choose the correct option.

Let A be an adjacency matrix of a graph G. The ij entry in the matrix A^k , gives


AThe number of paths of length K from vertex Vi to vertex Vj.

BShortest path of K edges from vertex Vi to vertex Vj.

CLength of a Eulerian path from vertex Vi to vertex Vj.

DLength of a Hamiltonian cycle from vertex Vi to vertex Vj.

Answer: Option B

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
33
Solv. Corr.
59
Solv. In. Corr.
92
Attempted
0 M:0 S
Avg. Time

7 / 12

Choose the correct option.

For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to


A2n

B(2n-1)/2

C2e

D(e^2)/2

Answer: Option C

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
34
Solv. Corr.
67
Solv. In. Corr.
101
Attempted
0 M:10 S
Avg. Time

8 / 12

Choose the correct option.

An adjacency matrix representation of a graph cannot contain information of :


Anodes

Bedges

Cdirection of edges

Dparallel edges

Answer: Option D

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
64
Solv. Corr.
56
Solv. In. Corr.
120
Attempted
0 M:0 S
Avg. Time

9 / 12

Choose the correct option.

In Breadth First Search of Graph, which of the following data structure is used?


AStack.

BQueue.

CLinked List.

DNone of these.

Answer: Option B

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
58
Solv. Corr.
29
Solv. In. Corr.
87
Attempted
0 M:0 S
Avg. Time

10 / 12

Choose the correct option.

For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is


Ane

B2n

C2e

De^n

Answer: Option C

Explanation:

Here is no explanation for this answer

Workspace