lan3016 11MEN406 4Microsoft Word EmphasisHeading 1 Heading 3

lan3016 11-MEN406 (4)·Microsoft Word EmphasisHeading 1 Heading 3 T Normal StrongSubtite 4) (25 points) The State University campus has five microcomputers. The distance between each pair of computers (in city blocks) is given in the figure below. The computers must be interconnected by underground cable. What is the minimum length of cable required?

Solution

The spanning tree solution is as follows:

Step

Connected Nodes

Unconnected Nodes

Closet Unconnected node

Arc selected

Arc length

Total Length

1

1

2, 3, 4, 5

1-2 (3)

1-3 (4)

1-5 (2)

1-4 (6)

1-5 (2)

2

2

2

1, 5

2, 3, 4

1-2 (3)

1-3 (4)

1-4 (6)

5-2 (2)

5-3 (2)

5-4 (4)

5-2 (2)

Or 5-3 (2)

Select node 2

2

4

3

1, 5, 2

3, 4

1-3 (4)

1-4 (6)

2-3 (3)

5-3 (2)

5-4 (4)

5-3 (2)

2

6

4

1, 5, 2, 3

4

1-4 (6)

3-4 (5)

5-4 (4)

5-4 (4)

4

10

               

Total length of wire required for the spanning tree = 10

The connections are as follows: 1-5, 5-2, 5-3, and 5-4

Step	Connected Nodes	Unconnected Nodes	Closet Unconnected node	Arc selected	Arc length	Total Length
1	1	2, 3, 4, 5	1-2 (3) 1-3 (4) 1-5 (2) 1-4 (6)	1-5 (2)	2	2
2	1, 5	2, 3, 4	1-2 (3) 1-3 (4) 1-4 (6) 5-2 (2) 5-3 (2) 5-4 (4)	5-2 (2) Or 5-3 (2) Select node 2	2	4
3	1, 5, 2	3, 4	1-3 (4) 1-4 (6) 2-3 (3) 5-3 (2) 5-4 (4)	5-3 (2)	2	6
4	1, 5, 2, 3	4	1-4 (6) 3-4 (5) 5-4 (4)	5-4 (4)	4	10