A university has eight buildings that need to be connected so that each of the b

Question

A university has eight buildings that need to be connected so that each of the building's computer network is accessible to the network in the other buildings. The distances between buildings are given below (in units of 1000 yards). Which pairs of buildings should be directly connected to connect all the buildings with a minimum total network length? What is the length of a minimum network? What are the different possible minimal networks?

Which pairs of buildings should be directly connected to connect all the buildings with a minimum total network length? What is the length of a minimum network? What are the different possible minimal networks?

Explanation / Answer

Answer:

Since the network is considered as connected in one direction, there by the network is considered to be forming a directed graph.

1)

The pair of buildings that are needed to be connected directly are:

(8, 7) - (7, 6) - (6, 5) - (5, 4) - (4, 3) - (3, 2) - (2, 1)

2)

Therefore, the total length of the network connection is 0.5+0.6+0.9+0.7+2.6+0.9+1.6 = 7.8

If the network is considered as undirected graph then the pair of buildings that are connected are:

(3, 2) – (2, 1) – (1, 4) – (4, 5) – (5, 6) – (6, 7) – (7, 8) – (8, 3)

Thereby the total length is:

0.9+1.6+0.5+0.7+0.9+0.6+0.5+0.9

=6.6

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.