Pages

Tuesday, April 12, 2011

CASE STUDY PROBLEM 1


Case Study Problems:

The Modern Corp. Problem
Management of the Modern Corp. has decided to have a state-of-the-art fiber-optic network installed to provide high-speed communications (data, voice, and video) between its 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 the potential locations of fiber-optic cables. The number next to each dashed line gives the cost (in millions of dollars) if that particular cable is chosen as one to be installed.

Question 1:
Determine which cables should be installed to minimize the total cost of providing high-speed communications between every pair of centers?

Question 2:
Explain the reason for the name of minimum spanning-tree.




Figure 1: A display of Modern Corp.'s major centers (nodes), the possible locations for fiber-optic cables (the dashed lines), and the cost in millions of dollars for those cables (the numbers).


ANSWERS:

Question 1:

The suggested plan for cables installation to minimize the total cost of providing high-speed communications between every pair of centers is:

  
n = 7 (vertices)
(n-1) = 8 (edges)

Way to calculate the total weight of minimum spanning tree or in this case the total cost in millions of dollars for those cable: 
Total weight = 1 + 1 + 2 + 3 + 4 + 5 = 15

Question 2: 


There are three reasons for the name of minimum spanning-tree. The first one is that the minimum spanning tree in Question 1 is a tree because it does not have any edges or path that begins and end at the same vertices (center/nodes) or in other word forming a cycle.  Secondly, it is also a spanning tree because it is a tree that connects all the vertices (center/nodes) by using the edges which by the number of edges (n-1) of the minimum spanning tree is always less one than the number of vertices (n) in the provided graph (Figure 1). Lastly, it is the minimum spanning tree because it minimizes the total weight of the spanning tree or in this case the total cost for the cables.


No comments:

Post a Comment