Nets, Puzzles, and Postmen: An exploration of mathematical connections
Peter M Higgins
Format: PDF / Kindle (mobi) / ePub
What do road and railway systems, electrical circuits, 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. Only relatively recently have mathematicians begun to explore such networks and connections, and their importance has taken everyone by surprise.
The mathematics of networks form the basis of many fascinating puzzles and problems, from tic-tac-toe and circular sudoku to the 'Chinese Postman Problem' (can he deliver all his letters without traversing the same street twice?). Peter Higgins shows how such puzzles as well as many real-world phenomena are underpinned by the same deep mathematical structure. Understanding mathematical networks can give us remarkable new insights into them all.
about the underlying network, and so to make progress, we should identify and draw that network. With respect to the network of seven bridges, there are only four places a walker can be, as indicated in the next diagram. Our ﬁrst simpliﬁcation in the way we look at the problem is to represent these four places (the two 44 THE NATURE OF NETS B1 I1 I2 B2 Figure 3.1 The seven bridges of Königsberg banks of the river and its pair of islands) as nodes. Naturally we draw one line between pairs
Given a simple plane network, it is clear that we can decorate it with as many loops and multiple edges as we wish without spoiling the planarity. For that reason, only the underlying simple network of a given network, where we strip away any loops and coalesce any multiple edges into a single edge, need concern us. Also, a network is planar if and only if each of its components is planar, so for the remainder of the discussion we take our network N to be simple and connected, meaning that it has
node lies within a triangle with colours 1 and 2 but no 3, it will be of degree 2; and ﬁnally any triply coloured triangle will have degree 1. We now ﬁnish the proof by invoking the Hand-Shaking Lemma—the number of nodes of odd degree is even, and since the outside node is odd, there must be an odd number of other nodes of degree 1, that is to say there is an odd number of triply coloured triangles. Therefore Sperner’s Lemma is established. All this can be seen in action in the example of Figure
graph of order 4. The de Bruijn graph of order n has as its nodes the 2n−1 binary strings of length n − 1. In Figure 6.3 we have n = 4 and so there are 23 = 8 nodes labelled by the eight binary strings of length three. Each of these nodes has two out-edges, one labelled 0 and the other 1. What characterizes this graph and gives it a touch of magic is the rule that tells you where each arrow goes to: to locate the end 116 ONE-WAY SYSTEMS 1 001 1 0 1 010 1 0 1 1 0 000 011 101 0 0
but has not yet been permanently labelled and if d + w(e) < t, where t is the current label of v and e is the edge from vi to v, change the temporary label to the (smaller) value d + w(e). (b) Having completed (a), take a node v that has the smallest temporary label among those still having temporary assignments, and make this temporary label permanent (if there are several of equal value, select whichever you prefer). Finally set v = vi+1 and repeat step 2. This process will eventually halt as