Introduction

Seervada Park has recently been opened to sightseeing and backpacking. Cars are not permitted in the park, but there is a narrow, winding, set of trails that are used by the rangers' jeeps and by a tram system that takes tourists from the entry point to a spectacular set of falls. The trail system looks like Figure 1, where a trail is represented by a line, and the meeting of two or more trails is represented by a circle. At every such meeting point there is a ranger station. The number beside a line is the length of that path in miles.

Figure 1: Seervada Park

The park management has three problems to solve. The first is to find the best path from the entrance (O) to the waterfalls (T). Here, ``best'' is defined to be the shortest path from O to T. This is an example of the shortest path problem.

The second problem is that a telephone system must be installed under the road to link all the stations (including the entrance and the waterfall's station). Because installation is expensive and disruptive to the unique ecology of the park, only enough lines will be installed so that there is some connection between every pair of stations. The objective is to minimize the miles of lines that must be installed. This is an example of the minimum spanning tree problem.

Finally, the third problem is that during certain periods (like the Labor Day weekend) more people wish to use the tram than can be accommodated. To avoid unduly disturbing the wildlife and ecology of the park, strict limitations on the number of trams that can use each trail segment have been placed. Therefore, during the peak season, various routes might be used by the trams in order to maximize the number of tourists served. The problem is to determine the maximum number of trips per day that can be done without violating the capacity restrictions. This is an example of the maximum flow problem.

Next: Terminology Up: A Tutorial on Network Previous: A Tutorial on Network