TOC Front Cover 2 Algorithms Graphs and Computers 5 Copyright Page 6 Preface 7 Contents 13 Chapter One. COMMUTING AND COMPUTING 19 1. Introduction 19 2. A Commuting Problem 21 3. Enumeration of Paths 22 4. Tree Diagrams 24 5. Timing and the Shortest Route 28 6. An Improved Map 30 7. The Array of Times 34 8. Arbitrary Starting Point 37 9. Minimum Time Functions 39 Front Cover 2 Algorithms Graphs and Computers 5 Copyright Page 6 Preface 7 Contents 13 Chapter One. COMMUTING AND COMPUTING 19 1. Introduction 19 2. A Commuting Problem 21 3. Enumeration of Paths 22 4. Tree Diagrams 24 5. Timing and the Shortest Route 28 6. An Improved Map 30 7. The Array of Times 34 8. Arbitrary Starting Point 37 9. Minimum Time Functions 39 10. The Minimum Function 40 11. Equations for the fi 43 12. Reduced Tree 45 13. General Map 46 14. Solving the Equations 48 15. Why Not Enumeration Using Computers? 50 16. Graphs 51 17. The Problem of the Königsberg Bridges 53 18. Systems and States 57 19. Critical Path Analysis 61 20. Summing Up 64 Bibliography and Comments 65 Chapter Two. THE METHOD OF SUCCESSIVE APPROXIMATIONS 67 1. Introduction 67 2. A Simple Example of Successive Approximations 68 3. A Simple Example of the Failure of the Method 71 4. Algorithms 72 5. Computer Programming 75 6. Algorithms for Solving x = f(x) 78 7. The Newton–Raphson Method: Square Roots 81 8. An Example 84 9. Enter the Digital Computer 85 11. Flow Charts for the Determination of S a 86 10. Stop Rules 86 12. What Initial Approximation? 87 13. An Approximation Method of Steinhaus 88 14. Successive Approximations for a Simple Routing Problem 89 15. The Map of Fig. 3 of Chapter One 91 16. Determination of Optimal Policy 94 17. A Different Initial Policy 95 18. Successive Approximations for a General Map 97 19. Computer Program 100 20. The Connection Matrix and A Second Programming Method 100 21. Fictitious Links 103 22. Paths With a Given Number of Junctions 104 23. A Labelling Algorithm 108 24. Working Back From the End 109 Miscellaneous Exercises 112 Bibliography and Comment 117 Chapter Three. FROM CHICAGO TO THE GRAND CANYON BY CAR AND COMPUTER : Difficulties Associated With Large Maps 119 1. Introduction 119 2. How to Plan a Vacation 120 3. A Particular Initial Approximation 124 4. The Peculiarities of Structure 124 5. Computer Program 127 6. Storage Considerations 128 7. Use of Tapes 128 8. Storage of Sparse Data 129 9. Calculation of the tij 130 10. Transformation of Systems 130 11. Stratification 132 12. Acceleration of Convergence 133 13. Design of Electric Power Stations 136 Miscellaneous Exercises 138 Bibliography and Comments 139 Chapter Four. PROOF OF THE VALIDITY OF THE METHOD 141 1. Will the Method Always Work? 141 3. How Do We Find the Desired Solution? 143 2. Is There at Least One Solution? 143 4. Monotonicity 144 5. The Upper Solution 145 6. The Lower Solution 146 8. Uniqueness of Solution 147 7. Experimental Proof of Uniqueness 147 9. Determination of Optimal Policy 149 10. Arbitrary Initial Approximation 150 11. Least Time to Move k Steps 151 12. Number of Iterations 153 Miscellaneous Exercises 155 Bibliography and Comment 159 Chapter Five. JUGGLING JUGS 160 1. A Classical Puzzle 160 2. Precise Formulation 160 4. Tree Diagrams 161 3. Trial and Error 161 5. Some Further Observations 165 6. Enumeration by Computer 166 7. A Geometrical Representation 167 8. Cost Matrix 170 9. Connection Matrix 172 10. Minimum Cost Functions 173 11. Powers of the Adjacency Matrix 173 12. Functional Equations 174 13. Successive Approximations 175 14. The Labelling Algorithm 176 15. Avoiding the Cost Matrix 178 17. Getting Close 179 16. Another Initial Policy 179 18. Making the Closest Approach 181 19. Calculation of fN(y, z ) 182 20. Accessible and Inaccessible States 185 Miscellaneous Exercises 186 Bibliography and Comment 191 Chapter Six. THE SAWYER GRAPH AND THE BILLIARD BALL COMPUTER 192 1. The Sawyer Graph 192 2. Analysis of the Sawyer Graph 195 3. Connectedness of the Sawyer Graph 198 4. The Spine of the Sawyer Graph 199 5. The Case When c is a Divisor of b 200 6. The General Case 201 7. The Case when b and c Have No Common Factor 203 8. The Billiard Ball Solution 205 9. The Billiard Ball Diagram and Sawyer Graph 206 10. Graphical Determination of Shortest Paths 207 11. Discussion 210 12. Computer Assistance in Drawing State Graphs 210 Miscellaneous Exercises 211 Bibliography and Comment 213 Chapter Seven. CANNIBALS AND MISSIONARIES 214 1. Another Classical Puzzle 214 2. Trees and Enumeration 215 3. The State Diagram 216 4. Existence and Uniqueness 218 5. Analytic Methods 222 6. Example 224 Miscellaneous Exercises 227 Bibliography and Comment 229 Chapter Eight. THE 'TRAVELLING SALESMAN' AND OTHER SCHEDULING PROBLEMS 231 1. Introduction 231 2. A Mathematician's Holiday 232 3. A Map and a Matrix 232 5. A Simplified Version 234 4. Enumeration 234 6. Recurrence Relations 235 7. Do All the Errands! 236 8. Feasibility 237 9. How Many Errands Could We Do? 237 10. Trading Time for Storage 238 11. How to Build a Tennis Court 239 12. Sequential Selection 240 13. Feasibility 241 14. Simplified and More Realistic Assignment Problem 242 15. Constraints 243 16. Discussion 243 18. A Branching Process 244 17. 2N 244 19. Recurrence Relations 245 Miscellaneous Exercises 246 20. Discussion 246 Bibliography and Comment 254 Author lndex 257 Subject Index 261 Mathematics in Science and Engineering 265 Show more