Data Structures :: Graphs

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

NA
SHSTTON
31
Solv. Corr.
18
Solv. In. Corr.
49
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
15
Solv. Corr.
26
Solv. In. Corr.
41
Attempted
0 M:0 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
9
Solv. Corr.
30
Solv. In. Corr.
39
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
18
Solv. Corr.
30
Solv. In. Corr.
48
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
6
Solv. Corr.
31
Solv. In. Corr.
37
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
8
Solv. Corr.
20
Solv. In. Corr.
28
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
9
Solv. Corr.
28
Solv. In. Corr.
37
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
11
Solv. Corr.
28
Solv. In. Corr.
39
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
25
Solv. Corr.
17
Solv. In. Corr.
42
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
24
Solv. Corr.
12
Solv. In. Corr.
36
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