Management of the modern Corp. has decided to have a state-of-the-art fiber-optic network install to provide high-speed communications (data, voice, and video) between major centers.
The nodes in figure 1 show the geographical layout of the corporation’s major centers which include corporate headquarters, a supercomputer facility, and a research park, as well as production and distribution centers. The dashed lines are potential locations of fiber-optic cables. The number next to each dashed line gives the cost (in millions of dollars) if that particular cable chosen as one to be installed.
Figure 1: A display of Modern Corp.'s major centers (nodes), the possible locations for fiber-optic cables(the dashed line), and the cost in million of dollars for those cables (the numbers).
A) Determine which cables should be installed to minimize the total cost of providing high-speed communications between every pair of centers?
n = 7
n-1 = 6
B)Explain the reason for the name of minimum spanning-tree.
Every nodes now is touched by a link, so the algorithm is done and this is the optimal solution. All the links that have been inserted into the network form a minimum spanning tree with a total cost 2+4+1+3+1+5 = 16 millions.
No comments:
Post a Comment