QUESTION 1 A _________ is the one in which every two pairs of vertices are conne

Question

QUESTION 1

A _________ is the one in which every two pairs of vertices are connected.

complete graph

weighted graph

directed graph

none of the above.

10 points   

QUESTION 2

If locality is a concern, you can use _______ to traverse the graph.

Breadth First Search (BFS)

Depth First Search (DFS)

Either BFS or DFS

None of the above.

10 points   

QUESTION 3

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can NOT be the degree sequence of any graph?

I. 7, 6, 5, 4, 4, 3, 2, 1

II. 6, 6, 6, 6, 3, 3, 2, 2

III. 7, 6, 6, 4, 4, 3, 2, 2

IV. 8, 7, 7, 6, 4, 2, 1, 1

I and II

III and IV

IV only

II and IV

None of the above.

10 points   

QUESTION 4

Considering unit weight on all the edges, which walk gives the shortest path:

Breadth First Search (BFS)

Depth First Search (DFS)

Either BFS or DFS

None of the above.

10 points   

QUESTION 5

Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is:

E

2E

V

2V

None of the above.

complete graph

weighted graph

directed graph

none of the above.

Explanation / Answer

Questtion 1. ---> Answer (a) complete graph, complete graph is undirected graph in which every vertiex is connected to unique edge.complete graph is a directed graph in which every pair is connected to a one unique edge pair which should be one in each direction.

Question 2. ----> Answer (B) Depth first search(DFS), Depth first search is better when locality wise items are concerned.

Question 3, ----> Answer (D) II & IV,

It can be done with the help of havel hakimi theorem,

So we check each degree sequence given in question :

Question 4, Answer 4 (A) Breadth First Search(BFS)

Question 5, Answer 5 (B) 2E , As the graph is given in undirected, every edge contributes as 2 to sum of degrees.

So the sum of degrees is 2E.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.