Tuesday, 12 April 2011

MINIMUM SPANNING TREE PROBLEM

QUESTION 1



QUESTION 2

QUESTION 3

 QUESTION 4

 QUESTION 5

 QUESTION 6
Posted by ::Math Discrete:: at 05:11 0 comments

Monday, 11 April 2011

CASE STUDY PROBLEMS : MODERN CORP. PROBLEM

     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.



Posted by ::Math Discrete:: at 12:36 0 comments

Sunday, 10 April 2011

CASE STUDY PROBLEMS : WIREHOUSE LUMBER COMPANY

The Wirehouse Lumber Company will soon begin logging eight groves of trees in the same general area. Therefore, it must develop a system of dirt roads that makes each grove accessible from every other grove. The distance(in miles) between every pair of groves is as follows:



Grove
Distance between Pairs of  Groves
1
2
3
4
5
6
7
8
1
-
1.3
2.1
0.9
0.7
1.8
2.0
1.5
2
1.3
-
0.9
1.8
1.2
2.6
2.3
1.1
3
2.1
0.9
-
2.6
1.7
2.5
1.9
1.0
4
0.9
1.8
2.6
-
0.7
1.6
1.5
0.9
5
0.7
1.2
1.7
0.7
-
0.9
1.1
0.8
6
1.8
2.6
2.5
1.6
0.9
-
0.6
1.0
7
2.0
2.3
1.9
1.5
1.1
0.6
-
0.5
8
1.5
1.1
1.0
0.9
0.8
1.0
0.5
-


Management now wants to determine between which pairs of groves the roads should be constructed to connect all groves with a minimum total length of road.

a. Describe how this problem fits the network description of a minimum spanning tree problem.   


answer:

  1. Choose of the first link: Select the cheapest potential link.
  2.  Choose of the next link: Select the cheapest potential link between a node that already is touched by a link and a node that does not yet have such a link.
  3.  Repeat step 2 over and over until every node is touched by a link (perhaps more than one). At that point, an optimal solution (a minimum spanning tree) has been obtained.

b. Use the suitable algorithm to solve this problem.


answer :



n = 8
n -1 = 7

total distance = 0.5 + 0.6 + 0.8 + 0.7+ 0.7 + 0.9 + 1.0

Posted by ::Math Discrete:: at 12:35 1 comments
Subscribe to: Posts (Atom)