Problem 1 Consider the weighted, undirected graph G in Figure 1. We are interested in finding a maximum spanning tree (MaxST) of G, i.e., a spanni tree of G of maximum total weight.
(i) Show that you can solve the MaxST problem by reducing it to the minimum spanni tree problem.
(ii) Find the Maximum Spanning Tree (MaxST) of G using Kruskal’s algorithm. Gi the set of edges in the MaxST. Show the main steps of the algorithm. What is t total weight of the MaxST?
(iii) Find the Maximum Spanning Tree (MaxST) of G using Prim’s algorithm. Gi the set of edges in the MaxST. Show the main steps of the algorithm. What is t weight of the MaxST?
(iv) Find the MaxST of G using Boruvka’s algorithm. Show the main steps of the algorithm. What is the weight of the MaxST?
Transcribed Image Text:W1
a
W2
w6
w7
6.
-1
4
W3
W5
e
W4
Figure 1: Weighted, undirected graph G.
Weights and Source Node
All problems use weights wi through w7. To determine these weights, look at your 7
digit ID. The weight wi corresponds to the first digit of your ID, the weight w2
corresponds to the second digit of your ID, and so on.
For problems 2 and 4, we use a source node or starting node s, determined as
follows: find the digit in your ID that has the highest value. If it is the first digit then s =
a, if it is the second digit, then s = b, and so on. If there is more than one digit with the
same highest value, choose the first occurrence of that digit. For example, if your ID is
4526767, then the highest value is 7, and you choose the first 7, i.e., digit 5, and set s =
е.
Process or set of rules that allow for the solving of specific, well-defined computational problems through a specific series of commands. This topic is fundamental in computer science, especially with regard to artificial intelligence, databases, graphics, networking, operating systems, and security.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
