The XY&Y Bell Telephone Corporation offers to set up and maintain a private network of cables...

Transcribed Image Text:

The XY&Y Bell Telephone Corporation offers to set up and maintain a private network of cables connecting all of your company's facilities. There are various ways in which the cables could be arranged so that there is a path from every facility to every other facility; as an example, here are two options for a case of 5 facilities: XY&Y's charge for their services is based on the minimum length of 880 cable that is required to connect your facilities in this way, with lengths between facilities computed by the usual cartesian formula for distances between points in a plane. a: The problem of minimizing the length of cable required, so that every facility is connected by a path to every other facility, is well known in the study of graphs and networks. What is the name that is given to this problem? b: Suppose that your facilities are arranged as follows, with the distances in kilometers shown on the scales at the left and bottom: What is the minimum 2- 1 - 0- 0 1 2 3 4 length of cable in this case? c: If you add a facility, must your payments to XY&Y necessarily go up? Give a simple example to show that this is not the case. d: If you add a facility, could your payments possibly go down? Give a simple example or short argument to justify your answer. e: After XY&Y instituted this scheme for charging for service, they found that customers were adding "phantom" facilities at which no activity actually took place. What do you suppose was the motivation for this behavior? The XY&Y Bell Telephone Corporation offers to set up and maintain a private network of cables connecting all of your company's facilities. There are various ways in which the cables could be arranged so that there is a path from every facility to every other facility; as an example, here are two options for a case of 5 facilities: XY&Y's charge for their services is based on the minimum length of 880 cable that is required to connect your facilities in this way, with lengths between facilities computed by the usual cartesian formula for distances between points in a plane. a: The problem of minimizing the length of cable required, so that every facility is connected by a path to every other facility, is well known in the study of graphs and networks. What is the name that is given to this problem? b: Suppose that your facilities are arranged as follows, with the distances in kilometers shown on the scales at the left and bottom: What is the minimum 2- 1 - 0- 0 1 2 3 4 length of cable in this case? c: If you add a facility, must your payments to XY&Y necessarily go up? Give a simple example to show that this is not the case. d: If you add a facility, could your payments possibly go down? Give a simple example or short argument to justify your answer. e: After XY&Y instituted this scheme for charging for service, they found that customers were adding "phantom" facilities at which no activity actually took place. What do you suppose was the motivation for this behavior?