The Chinese Postman Problem (UMAP)

A unit that applies finite mathematics to optimization focusing on the Chinese Postman Problem. This module introduces ideas from network and graph theory to find optimal routes. Students analyze networks and construct optimal routes for networks in which all streets are two-way streets.

Table of Contents:

1. DESCRIPTION OF THE PROBLEM

2. GRAPHS AND NETWORKS

3. EULERIAN AND HAMILTONIAN GRAPHS

4. EXISTENCE AND CONSTRUCTION OF EULERIAN CIRCUITS

5. COMPLETE AND MINIMAL MATCHINGS

6. CONSTRUCTION OF OPTIMAL ROUTES

7. ANSWERS TO EXERCISES

8. REFERENCES