Prepared by:

Joseph Malkevitch

Department of Mathematics

York College (CUNY)

Jamaica, New York 11451

Email: malkevitch@york.cuny.edu

web page: http://york.cuny.edu/~malk

Let us consider several problems, all of which will use as "input data" the diagram above.

Situation 0:

A contractor located at B has been hired to check the streets in the urban area shown above for pot holes. All the street segments shown will take the same time to traverse. The contractor wishes to traverse (walk) each segment of street at least once and return to B, following a route which will minimize the total amount of time for the inspection. What is this minimum amount of time?

(As part of your solution, explain why it is not possible to traverse each section of street once and only once on a tour that starts and ends at B.)

Situation 1:

You live at A and must run errands by foot that take you to the sites B, C, D, E, and F in any order you might want, and then return to A. What route makes the most sense? How far do you have to walk to achieve your "best" result? Are there different routes that are "best," and if so how many are there?

Situation 2:

A company must lay cable to connect up the sites A, ..., F so that messages can be sent between any pair of sites by relay if necessary. Thus, if cable is laid from A to B and B to C, cable does not have to be laid between A and C because one can relay a signal from A to C via B. If the cost of laying cable is proportional to the "distance" between two sites, what site pairs should be joined to minimize the cost of providing the cable service between the sites?

Situation 3:

Students live at sites A, ..., F. A teacher wishes to group the students in pairs for the purposes of working on projects. If X and Y are paired it is assumed that X will walk to Y's house or the other way around to work together. What pairing will minimize the "average" distance that must be walked to have the students work together?

Situation 4:

There are apartment blocks (or single family homes at A,...,F. Where would would an optimal location to place mobile medical facility which would:

a. Minimize the maximum distance that it would take to reach the mobile facility.

b. Minimize the total distance from all of the locations (A-F) to reach the mobile medical facility.

*
*--------------------------------------------------------------------------------------------------------------

Suppose you have described a group of problems which which appear to you to be similar to Situation 1. Now for each of these problems explain how you think the problem is like Situation 1 and how you think it differs from Situation 1. Carry out this same process for the problems you found similar to Situation 0, 2, 3 and to Situation 4.

Make up a new problem of your own invention based on the diagram and information implicit in the diagram given at the start. Perhaps you may want to ask that more information be added to the diagram to make up your problem. For example, you might want to know if there are traffic lights at any of the corners, or in what directions the automobile traffic can move on the streets shown.

a. Using a graph to help construct a mathematical model of information that comes up in everyday life.

b. Using a matrix to help construct a mathematical model of information that comes up in everyday life. (The matrix can be used to "store" the information which gives the taxicab or the Euclidean distance between the lettered points in the diagram.)

c. The difference between taxicab distance and Euclidean distance.

d. Situation 0 leads to the important mathematical model known as the Chinese Postman Problem. This problem generalizes ideas used by Leonard Euler in 1736 to solve the Königsberg Bridge problem, and which gave birth to a geometrical set of ideas known as graph theory. This problem involved the question of whether or not a collection of bridges joining various river banks and an island could be traversed once and only. Although this problem may not seem of much interest to urban students, when set as an operations research problem that involves municipal services it often catches the interest of students.

e. Situation 1 leads to the important mathematical model known as the traveling salesman problem (TSP). While this small problem can easily be solved by trial and error, large versions of this problem have been shown to belong to a class of computationally difficult problems. However, various easy "heuristics" (e.g. fast procedures that do not guarantee optimal answers) are often "rediscovered" by students. (Common names for these heuristics are "nearest neighbor" and "sorted edges.")

f. Situation 2 leads to the important mathematical model known as the minimum cost spanning tree (MST) problem. This problem can be solved by trial and error but there are variants of the heuristics listed above that lead to "fast" algorithms for this problem. These algorithms are know as Kruskal's and Prim's methods. There is also a lovely "parallel" algorithm known as Boruvka's method which also will solve this problem.

g. Situation 3 leads to the important mathematical model known as the minimum weight matching problem. This problem can be solved by trial and error here but although it is known that there is a "fast" algorithm to solve this problem, it is rather involved. Special cases of this problem can be solved more easily and involve ideas about shortest path algorithms in graphs.

h. Situation 4 has connections to ideas in statistics. The ideas of range, midrange value, mean, median and mode can be discussed. It belongs to a class of problems known as facility location problems. One needs to decide what distance function is most appropriate and also which optimization objective should be used. What adjustment might make sense if there are different numbers of people located at A,...,F?

The problem above was originally developed for a workshop given at Teachers College at Columbia, entitled Mathematics, Politics, and Society (July, 2004) Further work was supported in part by the Teacher Academy of York College. Specific funding was provided by: FIPSE (46274-07 01) and the Fund for PS (72042-07 01) to the Teacher Academy of CUNY