图论在20世纪得到了飞速的发展,其中一个主要的原因是其在物理学、化学、社会学及计算机科学等领域应用广泛。本书主要介绍了图论中一些基础课题的背景知识。包括K连通图的Dirac定理,线图的Harary-Nashwilliam定理,欧拉图的Toida-McKee公理,图的Tutte矩阵,平面图的Kuratowski定理的傅里叶证明方法等。
样章试读
目录
- Prefacev
Ⅰ 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 Ccncepts
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-Independent 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.5 2-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 Sharks
7.6 Kirkrnan'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 Ks 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 Tait 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 Symbol
References
Index