Customer Reviews

Nets, Puzzles and Postmen: An Exploration of Mathematical Connections

5 star:		(1)
4 star:		(0)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

I'm glad to have found this little gem of a book on graph theory at my local bookstore. It is a rather odd book, as it's clearly not a rigourous math or computational theory book, and yet it has enough technical sophistication to put it beyond the reach of understanding for a general audience. It seems more apt for people who are non-mathematicians but who have had some background in graph and complexity theory and would like to read some mathematical diversions written in a casual, colloquial style.

Although the author likes to term the subject of his book as "nets", it is clearly focused on graph theory, with topics covering a wide range of areas, including planarity, colouring, reachability, network flow, shortest path, and automata. There is also an excellent discussion of the pigeonhole principle and the handshaking lemma, both used in many places throughout the book. The author unfortunately does not cover combinatorial subgraph selection (e.g. clique and vertex cover), approximation algorithms, or all-pairs-shortest-path in much detail.

The author's writing style is very engaging and friendly, and it's certainly a nice break from the encyclopedic style found in typical textbooks. The author presents the history of graph theory, including Euler's Konigsberg bridges problem, and discusses a number of complexity problems, including sudoku, amino acid chains, marriage arrangement, and Huffman encoding. Although the book is not mathematically rigourous, the author does provide a nice bibliography, and chapter 10 serves as an appendix that goes into mathematical detail with proofs of several of the concepts presented in earlier chapters.

There are only a few negatives. The problem of lying tribesmen in chapter 1 is unnecessarily tedious as a motivating example on complexity. Furthermore, although the author has sprinkled diagrams throughout the book, there is certainly a need for more given that the book is centered on graphs. The section on network flow definitely would benefit from more illustrations.

In summary, this is an excellent casual book on graph theory and complexity written in an engaging style.