Network Flow Optimization and Minimum Spanning Trees

Introduction

Network flow techniques are aimed at optimizing situations related to transport networks, communication networks, the system of flights at airports, shipping routes for cruise lines, pumping stations that carry fluids through pipes, road networks between towns, pipe systems, and all situations that may be represented by a network. In such a network, nodes represent stations or towns and arcs (or edges) represent roads, airlines, cables, or pipes; the flow is represented by trucks, messages, or fluids moving through the network. These methods are used to find the shortest route in a road network or to send the maximum flow in a pipe network.

Network Models

The network optimization problems can be broadly represented by one of these four models:

• Minimization network model (minimum spanning tree problem)
• Shortest path model
• Maximum (peak) flow model
• Minimum cost flow model

Minimum Spanning Tree Model

The minimization network model, or minimum spanning tree problem, involves determining the set of edges that connects all nodes in a network while minimizing the sum of the lengths (or costs) of the chosen edges. The solution must not include cycles.

Characteristics of Minimum Spanning Trees

To create a minimum spanning tree, the problem has the following characteristics:

1. Suppose nodes exist in a network but the edges do not yet exist. Instead, potential edges and their positive lengths are provided for each possible inserted edge. (Alternative measures for the length of an edge include distance, cost, and time.)
2. We want to design the network with enough edges to satisfy the requirement that there be a path between each pair of nodes.
3. The goal is to satisfy this requirement while minimizing the total length of the edges embedded in the network.

A network with n nodes requires only (n-1) edges to provide a path between each pair of nodes. The (n-1) edges should be chosen so that the resulting network forms a spanning tree. Thus the problem is to find the spanning tree with the minimum total length of its edges.

Algorithm for Constructing a Minimum Spanning Tree

One simple algorithm to construct a minimum spanning tree proceeds as follows:

1. Choose, arbitrarily, any node and connect it to the nearest distinct node (i.e., add an edge).
2. Identify the closest node that is not yet connected to the connected component and connect these two nodes (i.e., add an edge between them). Repeat this step until all nodes are connected.
3. Ties: When there are ties for the nearest distinct node (step 1) or for the nearest node not yet connected (step 2), break the ties arbitrarily; the algorithm will still reach an optimal solution. However, these ties indicate that there may (but not necessarily) be multiple optimal solutions. All such solutions can be identified by trying other ways to break ties to the end.