Date: 9th December 2020 Question 3 [20 marks] (a) Find a minimal spanning tree for the following graph using Kruskal's algorithm, then calculate its weight. (1) 14 E 8 D 18 F 20 15 10 17 Course: BSE2033 Algorithm and Complexity 19 C 7 H 10 (b) Analyze the efficiency of minimal spanning tree. B 10 5 15 9 21 6 16 19 K Find a minimal spanning tree for the graph above using Kruskal's algorithm. (12 marks) Calculate its total weights. (2 marks) (6 marks) 1 Minimum spanning tree Do problem 4.9 on page 192 of the textbook. For your convenience, here is the problem. Let G = (V, E) be a connected (undirected) graph with n vertices, m edges and positive edge costs (assume edge costs are distinct). Let T = (V, E') be a spanning tree of G. The bottleneck edge of T is the edge of T with the greatest cost. A spanning tree T of G is called a minimum bottleneck spanning tree where there exists no spanning tree of G with a cheaper bottleneck edge. Questions: (a) Is every minimum bottleneck tree of G a minimum spanning tree of G? Prove or give a counter-example. (b) Is every minimum spanning tree of G a minimum bottleneck tree of G? Prove or give a counter-example.