question

QUESTION 1

1. In the terminology of network theory, what is a tree? A spanning tree? A minimum spanning tree?
2. What is an easiest way to recognize a spanning tree?
3. What is the objective of an minimum spanning tree problem?
4. How many methods will solve a minimum spanning tree problem?
5. What are a few types of applications of minimum spanning tree problems?
6. Use a Kruskal’s algorithm to find a minimum spanning tree for a network with the following nodes.

QUESTION 2

The 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 its major centers.
The nodes in figure 1 show the geographical layout of the corporation’s major centers which include corporate headquarters, s 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 give the cost (in millions of dollars) if that particular cable is chosen as one to be installed.
Determine which cable should be installed to minimize the total cost of providing high-speed communications between every pair of centers?
Explain the reason for the name of minimum spanning tree.

QUESTION 3
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 road that makes each grove accessible from every other grove. The distance (in miles) between every pair of groves is as follows:

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.
b. Use the suitable algorithm to solve the problem.