GATE CSE Graphs & Graph Algorithms – Data Structures Practice Test

GATE CSE Graphs & Graph Algorithms – Data Structures Practice Test | Set 1

Questions 81-85 of 100

0% completed (0/100 answered)

Question 81

MSQ · Multiple Correct 2 mark

Which of the following statements about Minimum Spanning Trees (MSTs) are CORRECT?

A If all edge weights are distinct, the MST is unique. B Adding a new edge to an MST creates exactly one cycle. C The minimum weight edge in any cut is always present in at least one MST. D The maximum weight edge in a graph can NEVER be part of an MST.

Question 82

MSQ · Multiple Correct 2 mark

Which of the following are NP-Complete problems on Graphs?

A Hamiltonian Path Problem B Travelling Salesperson Problem (TSP) C Graph 3-Coloring Problem D Single-Source Shortest Path with non-negative weights

Question 83

MSQ · Multiple Correct 2 mark

Which of the following operations take O(1) time when using an Adjacency Matrix representation?

A Checking if an edge exists between vertex u and vertex v B Adding a new edge between vertex u and vertex v C Removing an edge between vertex u and vertex v D Finding all adjacent neighbors of vertex u

Question 84

MSQ · Multiple Correct 2 mark

Which of the following statements about Planar Graphs are CORRECT?

A A graph is planar if it can be drawn in a plane without edge crossings. B For a connected planar graph with V >= 3, E <= 3V - 6. C $Euler's formula states V - E + F = 2.$ D $K_{5}$ and $K_{3,3}$ are non-planar graphs.

Question 85

MSQ · Multiple Correct 2 mark

Which of the following graph parameters are correctly matched with their properties?

A In-degree of a vertex: Number of directed edges entering it. B Out-degree of a vertex: Number of directed edges leaving it. C Self-loop: An edge connecting a vertex to itself. D Parallel edges: Two or more edges connecting the same pair of vertices in the same direction.