Drawing Pictures With One Line (HiMAP)

This unit uses Euler's Theorem and the fascinating one-line drawings of the Malekula people in the South Pacific to demonstrate the many applications of circuit design. HiMAP Module 21.

HiMAP library now available on CD-ROM product no. 7593

Table of Contents:

CHAPTER 1: EULER AND ONE-LINE GAMES
The Drawing Game
Who Plays the Game?
The Mathematical History of One-Line Pictures
HISTORICAL BOX: Where is Königsberg?
What is a Graph?
Examples of Applications
Euler's Solution
HISTORICAL BOX: Leonhard Euler
Why Euler's Solution is True
Finding an Eulerian Circuit-The Onion-Skin Algorithm
Finding an Eulerian Circuit-The Connectedness Algorithm
HISTORICAL BOX: Why Are They Called Graphs?
HISTORICAL BOX: Does Euler Deserve Credit for Euler's Theorem?

CHAPTER 2: REAL-WORLD PROBLEMS
What About Real-Life Problems?
Plotters and Computer Controlled Machining Tools
The Metal Cutting Problem
The Chinese Postman Problem
The Longest Stroll
HISTORICAL BOX: Detours
Routing Several Crews
Turning Around, Crossing Intersections, and Other Annoyances
Traveling Roads More Than Once
One-Way Streets and Directed Graphs
Mixed Graphs
Laying Out a Gallery
Putting it All Together-A Garbage Collection Problem
Summary
HISTORICAL BOX: The Human Aspect of Problem Solving

EXERCISES

REFERENCES