图论教程（英文影印版）[（印）巴拉克里什南 等编著] 2011年版

图论教程（英文影印版）
出版时间：2011年版
内容简介
　　Graph theory has experienced atremendous growth during the 20thcentury. One of the main reasonsfor this phenomenon is theapplicability of graph theory in otherdisciplines such as physics，chemistry， psychology， sociology， andtheoretical computer science.This book aims to provide a solidbackground in the basic topics ofgraph theory. It covers Dirac'stheorem on k-connected graphs，Harary-Nashwilliam's theorem on thehamiltonicity of line graphs，Toida-McKee's characterization ofEulerian graphs， the Tutte matrixof a graph， Foumier's proof ofKuratowski's theorem on planar graphs，the proof of thenonhamiltonicity of the Tutte graph on 46 verticesand a concreteapplication of triangulated graphs. The book does notpresupposedeep knowledge of any'branch of mathematics， butrequires only thebasics of mathematics. It can be used in an advancedundergraduatecourse ora beginning graduate course in graph theory.
目录
Preface
I Basic Results
1.0 Introduction
1.l 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
II Directed Graphs
2.0 Introduction
2.1 Basic Concepts
2.2 Tournaments
2.3 k-Partite Tournaments
Notes
III 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
IV 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 Heily Property
4.6 Exercises
Notes
V 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
VI Eulerian and HamUtonlan 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
VII 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
VIII 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 Tait Coloring
Notes
IX 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
X 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