Nets, Puzzles and Postmen An Exploration of Mathematical Connections

by Higgins, Peter M

• ISBN13: 9780199218424
• ISBN10: 0199218420
• Format: Hardcover
• Copyright: 2008-02-20
• Publisher: Oxford University Press

Summary

What do road and railway systems, mingling at parties, mazes, family trees, and the internet all have in common? All are networks--either people or places or things that relate and connect to one another. In this stimulating book, Peter Higgins shows that these phenomena--and many more--all share the same deep mathematical structure. The mathematics of networks form the basis of many fascinating puzzles and problems, from tic-tac-toe to circular sudoku. Higgins reveals that understanding networks can give us remarkable new insights into many of these puzzles as well as into a wide array of real-world phenomena. Higgins offers new perspectives on such familiar mathematical quandaries as the four-color map and the bridges of Konisberg. He poses the tantalizing question Can you walk through all the doors of the house just once? He also sheds light on the Postman Problem, a puzzle first posed by a Chinese mathematician: what is the most efficient way of delivering your letters, so you get back to your starting point without having traversed any street twice. And he explores the Harem Problem--a generalization of the Marriage Problem--in which we work out how to satisfy all members of a set of men who have expressed a wish for a harem of wives. Only relatively recently have mathematicians begun to explore networks and connections, and their importance has taken everyone by surprise.Nets, Puzzles, and Postmentakes readers on a dazzling tour of this new field, in a book that will delight math buffs everywhere.

Author Biography

Peter M. Higgins is Professor of Mathematics and Head of Mathematical Sciences at the University of Essex. His previous mathematics books for a popular audience include Mathematics for the Curious, Mathematics for the Imagination, and The Official Book of Circular Sudoku. He is the inventor of Circular Sudoku, which has now appeared throughout the world in magazines, books, the internet, and handheld computer games.

Table of Contents

Nets, Trees, and Lies	p. 1
Trees	p. 5
Chemical isomers	p. 9
Lying liars and the lies they tell	p. 10
Trees and Games of Logic	p. 17
Familiar logic games	p. 17
Exotic squares and Sudoku	p. 23
The Nature of Nets	p. 35
The small world phenomenon	p. 35
The bridges of Konigsberg	p. 43
Hand-shaking and its consequences	p. 48
Cycles that take you on a tour	p. 53
Party problems	p. 56
Colouring and Planarity	p. 63
The four-colour map problem	p. 63
How edges can ruin planarity	p. 74
Rabbits out of hats	p. 80
Guarding the gallery	p. 81
Innocent questions of points and lines	p. 84
Brouwer's fixed point theorem	p. 90
How to Traverse a Network	p. 101
The Euler-Fleury method	p. 101
The Chinese Postman Problem	p. 105
One-Way Systems	p. 111
Nets that remember where you have been	p. 114
Nets as machines	p. 119
Automata with something to say	p. 128
Lattices	p. 132
Spanning Networks	p. 137
Sorting the traffic	p. 140
Greedy salesmen	p. 145
Finding the quick route	p. 147
The P versus NP controversy	p. 150
Going with the Flow	p. 159
Network capacities and finding suitable boys	p. 159
Marriage and other problems	p. 163
Harems, maximum flows, and other things	p. 168
Novel Applications of Nets	p. 175
Instant Insanity	p. 175
Sharing the wine	p. 181
Jealousy problems	p. 184
Mazes and labyrinths	p. 185
Trees and codes	p. 188
Reassembling RNA chains	p. 191
For Connoisseurs	p. 197
References	p. 237
Further Reading	p. 239
Index	p. 243
Table of Contents provided by Ingram. All Rights Reserved.