Data Structures :: Graphs

Home > Data Structures > Graphs > General Questions

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

1 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

2 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

3 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

4 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

5 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

6 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

7 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

8 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

9 / 12

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

10 / 12

 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