图论在20世纪得到了飞速的发展，其中一个主要的原因是其在物理学、化学、社会学及计算机科学等领域应用广泛。本书主要介绍了图论中一些基础课题的背景知识。包括K连通图的Dirac定理，线图的Harary-Nashwilliam定理，欧拉图的Toida-McKee公理，图的Tutte矩阵，平面图的Kuratowski定理的傅里叶证明方法等。
样章试读
目录
- Contents
Preface
Ⅰ Basic Results 1
1.0 Introduction 1
1.1 Basic Concepts 2
1.2 Subgraphs 8
1.3 Degrees of Vertices 10
1.4 Paths and Connectedness 13
1.5 Automorphism of a Simple Graph 18
1.6 Line Graphs 20
1.7 Operations on Graphs 25
1.8 An Application to Chemistry 29
1.9 Miscellaneous Exercises 31
Notes 32
Ⅱ Directed Graphs 33
2.0 Introduction 33
2.1 Basic Concepts 33
2.2 Tournaments 35
2.3 /:-Partite Tournaments 38
Notes .43
Ⅲ Connectivity 44
3.0 Introduction 44
3.1 Vertex Cuts and Edge Cuts 44
3.2 Connectivity and Edge-Connectivity 48
3.3 Blocks 54
3.4 Cyclical Edge-Connectivity of a Graph 56
3.5 Menger’s Theorem 57
3.6 Exercises 65
Notes 66
Ⅳ Trees 67
4.0 Introduction 67
4.1 Definition, Characterization, and Simple Properties 67
4.2 Centers and Centroids 72
4.3 Counting the Number of Spanning Trees 75
4.4 Cayley’s Formula 79
4.5 Helly Property 80
4.6 Exercises 81
Notes 82
Ⅴ Independent Sets and Matchings 83
5.0 Introduction 83
5.1 Vertex Independent Sets and Vertex Coverings 83
5.2 Edge-Independent Sets 85
5.3 Matchings and Factors 87
5.4 Matchings in Bipartite Graphs 90
5.5* Perfect Matchings and the Tutte Matrix 99
Notes 101
Ⅵ Eulerian and Hamiltonian Graphs 102
6.0 Introduction 102
6.1 Eulerian Graphs 102
6.2 Hamiltonian Graphs 107
6.3* Pancyclic Graphs 115
6.4 Hamilton Cycles in Line Graphs 118.
6.5 2-Factorable Graphs 124
6.6 Exercises 126
Notes 127
Ⅶ Graph Colorings 128
7.0 Introduction 128
7.1 Vertex Colorings 128
7.2 Critical Graphs 132
7.3 Triangle-Free Graphs 136
7.4 Edge Colorings of Graphs 138
7.5 Snarks 144
7.6 Kirkman's Schoolgirls Problem 145
7.7 Chromatic Polynomials 147
Notes 150
Ⅷ Planarity 152
8.0 Introduction 152 .
8.1 Planar and Nonplanar Graphs 152
8.2 Euler Formula and Its Consequences 157
8.3 K5 and ^3 3 are Nonplanar Graphs 162
8.4 Dual of a Plane Graph .164
8.5 The Four-Color Theorem and the Heawood Five-Color Theorem 167
8.6 Kuratowski’s Theorem 170
8.7 Hamiltonian Plane Graphs 178
8.8 Tait Coloring 180
Notes 184
Ⅸ Triangulated Graphs 185
9.0 Introduction 185
9.1 Perfect Graphs 185
9.2 Triangulated Graphs 187
9.3 Interval Graphs 190
9.4 Bipartite Graph B(G) of a Graph G 192
9.5 Circular Arc Graphs 193
9.6 Exercises 193
9.7 Phasing of Traffic Lights at a Road Junction 195
Notes 198
Ⅹ Applications 199
10.0 Introduction 199
10.1 The Connector Problem 199
10.2 Kruskal’s Algorithm 200
10.3 Prim’s Algorithm.202
10.4 Shortest-Path Problems 203
10.5 Timetable Problem 205
10.6 Application to Social Psychology 207
10.7 Exercises 210
Notes 210
List of Symbols 213
References 217
Index 223
京公网安备 11010102004214号