图论教程

Preface Ⅰ Basic Results 1.0 Introduction 1.1 Basic Concepts 1.2 Subgraphs 1.3 Degrees of Vertices 1.4 Paths and Connectedness 1.5 Automorphism of a Simple Graph 1.6 Line Graphs 1.7 Operations on Graphs 1.8 An Application to Chemistry 1.9 Miscellaneous Exercises Notes Ⅱ Directed Graphs 2.0 Introduction 2.1 Basic Concepts 2.2 Tournaments 2.3 k—Partite Tournaments Notes Ⅲ Connectivity 3.0 Introduction 3.1 Vertex Cuts and Edge Cuts 3.2 Connectivity and Edge—Connectivity 3.3 Blocks 3.4 Cyclical Edge—Connectivity of a Graph 3.5 Menger’s Theorem 3.6 Exercises Notes Ⅳ Trees 4.0 Introduction 4.1 Definition， Characterization， and Simple Properties 4.2 Centers and Centroids 4.3 Counting the Number of Spanning Trees 4.4 Cayley’s Formula 4.5 Helly Property 4.6 Exercises Notes Ⅴ Independent Sets and Matchings 5.0 Introduction 5.1 Vertex Independent Sets and Vertex Coverings 5.2 Edge—lndependent Sets 5.3 Matchings and Factors 5.4 Matchings in Bipartite Graphs 5.5最 Perfect Matchings and the Tutte Matrix Notes Ⅵ Eulerian and Hamiltonian Graphs 6.0 Introduction 6.1 Eulerian Graphs 6.2 Hamiltonian Graphs 6.3最 Pancyclic Graphs 6.4 Hamilton Cycles in Line Graphs 6.52—Factorable Graphs 6.6 Exercises Notes Ⅶ Graph Colorings 7.0 Introduction 7.1 Vertex Colorings 7.2 Critical Graphs 7.3 Triangle—Free Graphs 7.4 Edge Colorings of Graphs 7.5 Snarks 7.6 Kirkman’s Schoolgirls Problem 7.7 Chromatic Polynomials Notes Ⅷ Planarity 8.0 Introduction 8.1 Planar and Nonplanar Graphs 8.2 Euler Formula and Its Consequences 8.3 K5 and K3，3 are Nonplanar Graphs 8.4 Dual of a Plane Graph 8.5 The Four—Color Theorem and the Heawood Five—Color Theorem 8.6 Kuratowski’s Theorem 8.7 Hamiltonian Plane Graphs 8.8 Talt Coloring Notes Ⅸ Triangulated Graphs 9.0 Introduction 9.1 Perfect Graphs 9.2 Triangulated Graphs 9.3 Interval Graphs 9.4 Bipartite Graph B（G） of a Graph G 9.5 Circular Arc Graphs 9.6 Exercises 9.7 Phasing of Traffic Lights at a Road Junction Notes Ⅹ Applications 10.0 Introduction 10.1 The Connector Problem 10.2 Kruskal’s Algorithm 10.3 Prim’s Algorithm 10.4 Shortest—Path Problems 10.5 Timetable Problem 10.6 Application to Social Psychology 10.7 Exercises Notes List of Symbols References Index