Data Structure II Practice Test 5

1. Who was the first person to solve the maximum matching problem?

2. Consider the given graph.

What is the weight of the minimum spanning tree using the Prim’s algorithm,starting from vertex a?

3. How many unique colors will be required for proper vertex coloring of an empty graph having n vertices?

4. Branch and bound is a __________

5. How many unique colors will be required for vertex coloring of the following graph?

6. Which of the following branch and bound strategy leads to breadth first search?

7. The chromatic number of star graph with 3 vertices is greater than that of a complete graph with 3 vertices.

8. When a free man proposes to an available woman, which of the following happens?

9. What happens when a free man approaches a married woman?

10. What is the time complexity of Dijikstra’s algorithm?