图论

内容概要

W．T．Tutte已故著名数学家，现代图论奠基人之一。他于1948年获得剑桥大学博士学位；1942年至1949年担任三一学院评论员；1948年至1962年执教于多伦多大学。他是加拿大皇家科学院院士，曾被授予HenryMarshallTory奖。1982年，加拿大议会授予他IzaakWaltonKillam纪念奖。除本书外，他还著有拟阵论方面的书籍。他生前还多年担任《Journal of Combinatorial Theory》杂志主编。

书籍目录

Editor's Statement

Foreword

Introduction

Chapter I Graphs and Subgraphs

I.1 Definitions

1.2 Isomorphism

1.3 Subgraphs

1.4 Vertices of attachment

1.5 Components and connection

1.6 Deletion of an edge

1.7 Lists of nonisomorphic connected graphs

1.8 Bridges

1.9 Notes

Exercises

References

Chapter II Contractions and the Theorem of Menger

II.1 Contractions

II.2 Contraction of an edge

II.3 Vertices of attachment

II.4 Separation numbers

II.5 Menger's Theorem

II.6 Hall's Theorem

II.7 Notes

Exercises

References

Chapter III 2-Connection

III.1 Separable and 2-connected graphs

III.2 Constructions for 2-connected graphs

III.3 Blocks

III.4 Arms

III.5 Deletion and contraction of an edge

II1.6 Notes

Exercises

References

Chapter IV 3-Connection

IV.1 Multiple connection

IV.2 Some constructions for 3-connected graphs

IV.3 3-blocks

IV.4 Cleavages

IV.5 Deletions and contractions of edges

IV.6 The Wheel Theorem

IV.7 Notes

Exercises

References

Chapter V Reconstruction

V.I The Reconstruction Problem

V.2 Theory and practice

V.3 Kelly's Lemma

V.4 Edge-reconstruction

V.5 Notes

Exercises

References

Chapter VI Digraphs and Paths

VI.1 Digraphs

VI.2 Paths

VI.3 The BEST Theorem

VI.4 The Matrix-Tree Theorem

VI.5 The Laws of Kirchhoff

VI.6 Identification of vertices

VI.7 Transportation Theory

VI.8 Notes

Exercises

References

Chapter VII Alternating Paths

VII.1 Cursality

VII.2 The bicursal subgraph

VII.3 Bicursal units

VII.4 Alternating barriers

VII.5 f-factors and f-barriers

VII.6 The f-factor theorem

VII.7 Subgraphs of minimum deficiency

VII.8 The bipartite case

VII.9 A theorem of Erdos and Gallai

VII.10 Notes

Exercises

References

Chapter VIII Algebraic Duality

VIII.I Chain-groups

VIII.2 Primitive chains

VIII.3 Regular chain-groups

VIII.4 Cycles

VIII.5 Coboundaries

VIII.6 Reductions and contractions

VIII.7 Algebraic duality

VIII.8 Connectivity

VIII.9 On transportation theory

VIII.10 Incidence matrices

VIII.11 Matroids

VIII.12 Notes

Exercises

References

Chapter IX Polynomials Associated with Graphs

IX.1 V-functions

IX.2 The chromatic polynomial

IX.3 Colorings of graphs

IX.4 The flow polynomial

IX.5 Tait colorings

IX.6 The dichromate of a graph

IX.7 Some remarks on reconstruction

IX.8 Notes

Exercises

References

Chapter X Combinatorial Maps

X.1 Definitions and preliminary theorems

X.2 Orientability

X.3 Duality

X.4 Isomorphism

X.5 Drawings of maps

X.6 Angles

X.7 Operations on maps

X.8 Combinatorial surfaces

X.9 Cycles and coboundaries

X. 10 Notes

Exercises

References

Chapter XI Planarity

XI.1 Planar graphs

XI.2 Spanning subgraphs

XI.3 Jordan's Theorem

XI.4 Connectivity in planar maps

XI.5 The cross-cut Theorem

XI.6 Bridges

XI.7 An algorithm for planarity

XI.8 Peripheral circuits in 3-connected graphs

XI.9 Kuratowski's Theorem

XI.10 Notes

Exercises

References

Index

作者简介

本书并不是一本论文集，而是一系列讲稿的有机组合。本书涉及了Menger定理、重构、矩阵—树定理、Brooks定理、Grinberg定理、平面图等核心论题。在讲述时不仅关注原理本身，而且关注其推导过程。如果想对图论有个基本的了解，本书是最佳选择。另外，书中每一章都附有习题、注记和详尽的参考文献。

“相信本书会对在坚实的理论与技术基础上搭建起图论的大厦起到十分重要的作用。”

——Crispin St.J.A. Nash-Williams教授，里丁大学

图书封面

---

 图论下载

---