The Fascinating World of Graph Theory
“The Fascinating World of Graph Theory is readable and “student-friendly”—more so than the typical math textbook . . .”
The Fascinating World of Graph Theory arrived at a most opportune moment. This reviewer was in the middle of teaching a course in Algorithms and having trouble holding students’ attention. Algorithms was already familiar to them, the students having coded stacks, lists, queues, and trees from previous courses, in particular Data Structures I and again in Data Structures II.
Here’s where The Fascinating World of Graph Theory shows its pedagogic value. Traditional courseware develops subject matter from the bottom on up, going from basic definitions to the more complex. The Fascinating World of Graph Theory is different, not starting with the simplest structures or algorithms but with interesting problems to be solved, puzzles that use graphs and networks such as the Problem of Five Princes, Three Houses and Three Utilities, and The Job Hunter’s Problem. Good puzzles to give students are ones that look difficult but yield to simple logic and mathematics, something that students can puzzle out on their own without having to delve too much into definitions or study of foundational material.
The second chapter presents a number of famous problems, including The Konigsberg Bridge Problem, The Four Color Problem, and The Polyhedron Problem. These are accompanied by puzzles that use a chessboard and a selected subset of chess pieces, including The Knight’s Tour and The Five Queens Puzzle. Puzzles in the second chapter include the efficient placement of guards in art galleries, the coordination of traffic lights at intersections, and the arrangement of game tournaments. And all of these problems and puzzles are presented before definitions, theorems and in depth instruction.
After the first two chapters the authors provide foundational material, and though they define terms the authors sometimes slip and use terms pages before their definition to the consequence that a student will need to search ahead (or backwards) through the text on encountering unfamiliar terms. The authors also use a number of unfamiliar definitions. For example the term “weight” in weighted graph commonly refers to the weight (or cost) of traversing an edge in a graph. The authors define weight as the count of parallel edges in a multigraph. In another example, the “directed” in directed graph, commonly refers to graph edges having a direction, similar to one-way streets and two-way streets. The authors instead of direction use the term orienting, though googling “orienting graph” shows this alternative term to be more common than expected.
Graph and graph topics addressed in The Fascinating World of Graph Theory include regular graphs, irregular graphs, almost irregular graphs, graph complements and multigraphs (graphs with multiple parallel edges), bipartite graphs, and Erdos numbers (collaboration graphs). And there are many real-world applications: one puzzle analyzes street distances in city plans to determine where to place an emergency facility so that the path to the facility will always be the shortest.
In addition to graphs, The Fascinating World of Graph Theory covers trees including decision trees, minimum cost paths, Euler’s famous Konigsberg bridge problems, the “geometry of position,” and continuing to provide real world problems as examples—for example, saturated hydrocarbons map nicely to tree structures.
After the chapter on trees, The Fascinating World of Graph Theory goes back to graphs though now they are more complex and in-depth, these include Hamiltonian graphs, the Traveling Salesman problem, factoring graphs, matching graphs, decomposing graphs, orienting graphs, coloring graphs, drawing graphs (both planar and non-planar), embedding graphs (on surfaces), and the history and nature of proofs for the four-color problem that includes an explanation of what “proof” means.
The book concludes with a chapter on finite automata, which may be more familiar to engineers as “state machines.” Finite automata are (to no surprise), also graphs. Throughout, the authors digress into side-topics in graph theory and graph theory history, raising and following through on interesting questions, and providing biographies of those who have made advances graph theory, including mathematicians famous and not so famous. And in what should be by now expected of mathematician-authors, any number of poems, songs, and (bad) puns will be found interwoven with the text.
Each chapter is short and (mostly) self-contained, providing its own set of examples, puzzles and problems, permitting readers or instructors to skip chapters or choose chapters in a variety of sequences. Additional problems are provided at the end but organized by chapter, and suitable for assignment.
The Fascinating World of Graph Theory is readable and “student-friendly”—more so than the typical math textbook—and as such this reviewer intends to keep the book within easy reach.