图论基础教程

Contents

Preface

Chapter 1 Basic Concepts of Graphs

1.1 Graph and Graphical Representation.

1.2 Graph Isomorphism.

1.3 Vertex Degrees

1.4 Subgraphs and Operations

1.5 Walks， Paths and Connection

Chapter 2 Advanced Concepts of Graphs

2.1 Distances and Diameters

2.2 Circuits and Cycles

2.3 Eulerian Graphs

2.4 Hamiltonian Graphs

2.5 Matrix Representations of Graphs

2.6 Exponents of Primitive Matrices

Chapter 3 Trees and Graphic Spaces

3.1 Trees and Spanning Trees.

3.2 Vector Spaces of Graphs

3.3 Enumeration of Spanning Trees

3.4 The Minimum Connector Problem.

3.5 The Shortest Path Problem.

3.6 The Electrical Network Equations

Chapter 4 Plane Graphs and Planar Graphs

4.1 Plane Graphs and Euler's Formula

4.2 Kuratowski's Theorem.

4.3 Dual Graphs.

4.4 Regular Polyhedra.

4.5 Layout of Printed Circuits

Chapter 5 Flows and Connectivity.

5.1 Network Flows

5.2 Menger's Theorem.

5.3 Connectivity.

5.4 Design of Transport Schemes

5.5 Design of Optimal Transport Schemes

5.6 The Chinese Postman Problem

5.7 Construction of Squared Rectangles.

Chapter 6 Matchings and Independent Sets

6.1 Matchings

6.2 Independent Sets

6.3 The Personnel Assignment Problem.

6.4 The Optimal Assignment Problem.

6.5 The Travelling Salesman Problem.

Chapter 7 Colorings and Integer Flows

7.1 Vertex-Colorings.

7.2 Edge-Colorings

7.3 Face-Coloring and Four-Color Problem.

7.4 Integer Flows and Cycle Covers

Chapter 8 Graphs and Groups

8.1 Group Representation of Graphs

8.2 Transitive Graphs

8.3 Graphic Representation of Groups

8.4 Design of Interconnection Networks

Bibliography

List of Notations

Index

《运筹与管理科学丛书24：A First Course in Graph Theory（图论基础教程）》着眼于有向图，将无向图作为特例，在一定的深度和广度上系统地阐述了图论的基本概念、理论和方法以及基本应用．全书内容共分７章，包括Euler回与Hamilton圈、树与图空间、平面图、网络流与连通度、匹配与独立集、染色理论、图与群以及图在矩阵论、组合数学、组合优化、运筹学、线性规划、电子学以及通讯和计算机科学等多方面的应用．每章分为理论和应用两部分，章末有小结和参考文献．各章内容之间联系紧密，许多著名的定理给出最新最简单的多种证明。每小节末有大量习题，书末附有记号和名词索引。