The minimal-spanning tree problem involves connecting all points of a network together while minimizing the total distance of these connections. Some common examples include telephone or cable companies trying to connect houses in a neighborhood, and network administrators trying to minimize the cable required to hardwire computers in a network. While a linear programming model can be used for this problem, it has certain properties that make this quite complex. Fortunately, there is another method for finding the solution to such a problem that is very easy, and that will be presented here. The minimal-spanning tree technique problem will be presented using the following example.

Let us consider the Lauderdale Construction Company, which is currently developing a luxurious housing project in Panama City Beach, Florida. Melvin Lauderdale, owner and president of Lauderdale Construction, must determine the least expensive way to provide water and power to each house. The network of houses is shown in Figure 9.6.

As seen in Figure 9.6, there are eight houses on the gulf. The distance between each house in hundreds of feet is shown on the network. The distance between houses 1 and 2, for example, is 300 feet. (The number 3 is between nodes 1 and 2.) Now, the minimal-spanning tree technique is used to determine the minimal distance that can be used to connect all of the nodes. The approach is outlined as follows.

Now, we solve the network in Figure 9.6 for Melvin Lauderdale. We start by arbitrarily selecting node 1. Since the nearest node is the third node at a distance of 2 (200 feet), we connect node 1 to node 3. This is shown in Figure 9.7.

Considering nodes 1 and 3, we look for the next-nearest node. This is node 4, which is the closest to node 3. The distance is 2 (200 feet). Again, we connect these nodes, as shown in Figure 9.8(a).

We continue, looking for the nearest unconnected node to nodes 1, 3, and 4. This is node 2 or node 6, each at a distance of 3 from node 3. We will pick node 2 and connect it to node 3, as shown in Figure 9.8(b).

We continue the process. There is another tie for the next iteration with a minimum distance of 3 (node 2–node 5 and node 3–node 6). You should note that we do not consider node 1–node 2 with a distance of 3 because both nodes 1 and 2 are already connected. We arbitrarily select node 5 and connect it to node 2, as shown in Figure 9.9(a). The next-nearest node is node 6, and we connect it to node 3, as shown in Figure 9.9(b).

At this stage, we have only two unconnected nodes left. Node 8 is the nearest to node 6, with a distance of 1, and we connect it, as shown in Figure 9.9(c). Then the remaining node, node 7, is connected to node 8, as shown in Figure 9.9(d).

The final solution can be seen in the seventh and final iteration. Nodes 1, 2, 4, and 6 are all connected to node 3. Node 2 is connected to node 5. Node 6 is connected to node 8, and node 8 is connected to node 7. All of the nodes are now connected. The total distance is found by adding the distances for the arcs used in the spanning tree. In this example, the distance is $2+2+3+3+3+1+2=16$ (or 1,600 feet). This is summarized in Table 9.4.

The minimal-spanning tree problem can be solved with Excel QM or QM for Windows. Using Excel QM in Excel 2016, select the Alphabetical menu from the ribbon, scroll down to Network Analysis, and select Minimal Spanning Tree. In the spreadsheet initialization window that opens, enter the number of branches or arcs (13 in this example). When the worksheet opens, for each arc enter the beginning node, the ending node, and the distance between the two (i.e., the length of the arc), as shown in Program 9.8. Click the Solve button that appears in the spreadsheet, and the solution will be displayed, as in Program 9.8. The problem could also be solved in QM for Windows by selecting the Networks module and entering a new problem as a minimal-spanning tree. The input is very similar to the Excel QM input.