内容

目次

I: The Theory of Graphs.- 1: Basic Ideas.- History.- Initial Concepts.- Summary.- Exercises.- 2: Connectivity.- Elementary Results.- Structure Based on Connectivity.- Summary.- Exercises.- 3: Trees.- Characterizations.- Theorems on Trees.- Tree Distances.- Binary Trees.- Tree Enumeration.- Spanning Trees.- Fundamental Cycles.- Summary.- Exercises.- 4: Traversability.- Eulerian Graphs.- Hamiltonian Graphs.- Summary.- Exercises.- 5: Planarity.- The Utilities Problem.- Plane and Planar Graphs.- Planar Graph Representation.- Planarity Detection.- Duality.- Thickness and Crossing Numbers.- Summary.- Exercises.- 6: Matrices.- The Adjacency Matrix.- The Incidence Matrix.- The Cycle Matrix.- The Cut-Set Matrix.- The Path Matrix.- Summary.- Exercises.- 7: Digraphs.- Connectivity.- Traversability.- Directed Trees.- More Digraph Matrices.- The Principle of Directional Duality.- Tournaments.- Summary.- Exercises.- 8: Coverings and Colourings.- Covering, Independence, and Domination.- Colouring.- Matching.- Summary.- Exercises.- 9: Algorithms.- Algorithms.- Input.- Complexity.- Output.- Graph Analysis Algorithms.- Graph Optimization Algorithms.- Summary.- Exercises.- 10: Matroids.- Duality.- The Greedy Algorithm.- Summary.- Exercises.- II: Applications.- 11: Miscellaneous Applications.- Social Sciences.- Economics.- Geography.- Architecture.- Puzzles and Games.- Summary.- Exercises.- 12: Operations Research.- Operations Research and Graph Theory.- Graph Theoretic Algorithms in OR.- Graph Theoretic Heuristics in OR.- Digraphs in OR.- Optimization Algorithms.- Transportation Networks: Advanced Models.- Summary.- Exercises.- 13: Electrical Engineering.- Electrical Network Analysis.- Printed Circuit Design.- Summary.- Exercises.- 14: Industrial Engineering.- Production Planning and Control.- Facilities Layout.- Summary.- Exercises.- 15: Science.- Physics.- Chemistry.- Biology.- Summary.- Exercises.- 16: Civil Engineering.- Earthwork projects.- Traffic Network Design.- Summary.- Exercises.- Further Reading.