MST:Problem and Motivation Suppose we have n computers, connected by wires as given in the graph. 4 1 ■ Each wire has a renting cost. 4 6 3 ■ We want to select some wires, such that all computers are connected (i.e.every two can communicate). 3 Algorithmic question:How to select a subset of wires with the minimum renting cost? Answer to this graph?MST: Problem and Motivation ◼ Suppose we have 𝑛 computers, connected by wires as given in the graph. ◼ Each wire has a renting cost. ◼ We want to select some wires, such that all computers are connected (i.e. every two can communicate). ◼ Algorithmic question: How to select a subset of wires with the minimum renting cost? ◼ Answer to this graph? 4 1 4 3 5 4 2 2 2 3 3 2 6 4