图论教程

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

《图论教程(影印版)》作者是印度巴拉克里什南（BalakrishnanR.）。《图论教程(影印版)》是“国外数学名著系列”丛书中的一本。《图论教程(影印版)》关键词：图论、教材、英文。《图论教程(影印版)》由北京京华虎彩印刷有限公司印刷。《图论教程(影印版)》由各地新华书店经销。