Minimum Spanning Tree Problems

Bismillahirrahmanirrahim.

Question 1
              
                In the terminology of network theory, what is a tree?  A spanning tree ? A minimum spanning tree?

Ø  Tree – connected undirected graph with no simple circuits

Ø  A spanning tree – Let  Y be a simple graph. A spanning tree of Y is a subgraph of Y that is a tree containing every vertex of Y

Ø  A minimum spanning tree –  spanning tree that has the smallest possible sum of weights of its edges

What is an easy way to recognize a spanning tree?

Ø  All vertices are connected

Ø  No cycle or loops are formed

Ø  Undirected graph

What is the objective of a minimum spanning tree problem?

Ø  To minimise the total cost of the network or to increase the economics efficiency

Ø  To make the transmission of data  to multiple receiving computers more efficient

How many method will solve a minimum spanning tree problrm?

Ø  Kruskal’s Algorithm

Ø  Depth-First Search Algorithm

                        Ø  Prim’s Algorithm

                       What  are  a few types of applications of minimum spanning tree problem?

Ø  Use in the optimization of city natural gas pipeline network

Ø  Application phone network design

Ø  Play a role in data networking such as in  multicasting over Internet Protocol(IP) networks

Use a kruskals algorithm to find a minimum spanning tree for a network with the following nodes.

 n = number of vertices;      n-1 = no. of edges of spanning tree

 n = 7

 n -1 = 6

Min. total weight = 1+1+2+4+4+6

                          = 18

Question 2

Case study problems 

The Modern Corp. Problem.

Management of the modern Corp. has decided to have decided to have a state-of-the-art fiber-optic network install 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.

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

number of centers = vertices = n = 7
number of fiber-optic = edges = n - 1 = 7 - 1 = 6

Min. total cost = 1 + 1 + 2 + 3 + 4 + 5
                       = 16 million

Explain the reason for the name minimum spanning-tree.

• the spanning tree with the smallest sum of the distances over the edges in the spanning tree.

Question 3

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

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

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

because using minimum spanning tree problem it can has the shortest possible sum of distance and connect all the grove. This will easier to the system developer to develop a system of dirt roads that makes each grove accessible from every other grove.

b) Use the suitable algorithm to solve the problem.

number of grove = n = 8
number of roads = n - 1 = 7

= 0.5 + 0.6 + 0.7 + 0.7 + 0.9 + 0.9 + 1.0
= 5.3 miles

Reference
Discrete Mathematics and Its Applications, Sixth Edition, Kenneth H. Rosen