《图论基础》除了介绍图论的基本概念和简单结构理论外，主要研究总结了近些年来比较热门的关于图的邻接谱、图的匹配多项式、图的着色、图的色多项式、图的拉普拉斯多项式和图的准拉普拉斯多项式的一些主要成果。为了方便读者进行研究和参考，我们也采编了一些和图论问题相关的线性代数、矩阵论的理论知识。在书的后面给出了基本符号及中英文对照表，以方便读者查阅参考。
    《高等学校计算机系列教材：图论基础》内容详细，证明简洁，并且在每章后面提供了一些新的研究内容与素材并配以一定量的习题，可作为数学与应用数学专业高年级的专业选修课和图论方向的一年级的硕士研究生课程的教材，也可作为广大图论研究工作者的参考用书。

《图论基础》的特点：内容基础、简单易于初学者掌握。主要侧重图基本结构与图的谱理论的相互关系.另外对多项式理论也进行了讨论。内容新颖，尤其是图的匹配多项式方面介绍了近年来的最新研究成果。采用英语语言编写，可以作为双语教材。

　　序言
图论不仅在算法设计、运筹学、网络设计，甚至在生物、化学等学科中都有广泛的应用，
而且经过几十年的发展现已成为和离散数学、组合数学、代数学、拓扑等数学分支紧密联
系的一个重要数学分支，因此，越来越受学术界的关注，并在实际问题中得到广泛的应用。
2006 年我校开设“图论”课程的双语教学，旨在扩大理工科高年级本科生的知识面，提高学
生对离散现象的分析能力，经过长时间教学实践并结合自己的研究成果，我们决定编写一本
具有特色的双语教材。
本书是在作者几年来开设“图论”双语教学所使用的自编讲义的基础上整理而成的。我
们借鉴国内外同类教材的精华，详细介绍了图的基本概念、图的谱、树、连通性、欧拉与哈
密尔顿图以及图的匹配多项式、图的着色、色多项式和图的准拉普拉斯谱等近几年的一些主
要成果，同时也采编了一些解决图论问题的有关线性代数，矩阵论的理论知识。并且，在每
章后面提供了一定量的习题，这些习题对于掌握图的结构性质有很大的帮助，部分有难度的
习题标以|，此外，作为对图论知识的应用在每章给出一个GROUP PROJECT 供读者练
习。总体上来讲，本教材内容丰富并且由浅入深，是一本图论入门书，也是对图的匹配多项
式理论感兴趣的读者的一本较全面的参考书。但由于作者水平有限，经验不足，难免有不少
错误，恳请读者批评指正。
在本书即将出版的时候，感谢我的硕士导师刘儒英、冶成福教授，以及各位师兄、师姐
的帮助；特别感谢博士导师束金龙导师对本书的编排及修改意见；最后感谢浙江省科协的资
助和清华大学出版社的大力支持！
编者
2010 年3 月
iii

Preface in Chinese
Chapter 1 Basic concepts
1.1 Graph and simple graph
1.2 Graph operations
1.3 Isomorphism
1.4 Incident and adjacent matrix
1.5 The spectrum of graph
1.6 The spectrum of several graphs
1.7 Results from matrix theory
1.8 About the largest zero of characteristic polynomials
1.9 Spectrum radius

Chapter 2 path and cycle
2.1 The path
2.2 The cycle
2.3 The diameter of a graph and its complement graph

Chapter 3 Tree
3.1 Tree
3.2 Spanning tree
3.3 A bound for the tree number of regular graphs
3.4 Cycle space and bound space of a graph

Chapter 4 Connectivity
4.1 Cut edges
4.2 Cut vertex
4.3 Block
4.4 Connectivity

Chapter 5 Euler and Hamilton graphs
5.1 Euler path and circuits
5.2 Hamilton graph

Chapter 6 Matching and matching polynomial
6.1 Matching
6.2 Bipartite graph and perfect matching
6.3 Matching polynomial
6.4 The relation between spectrum and matching polynomial
6.5 Relation between several graphs
6.6 Several matching equivalent and matching unique graphs
6.7 The Hosoya index of several graphs
6.8 Two trees with minimal Hosoya index
6.9 Recent results in matching

Chapter 7 Laplacian and Quasi-Laplacian spectrum
7.1 Sigma function
7.2 The spanning tree and sigma function
7.3 Quasi-Laplacian Spectrum
7.4 Basic lemmas
7.5 Main results
7.6 Three different spectrum of regular graphs

Chapter 8 More theorems form matrix theory
8.1 The irreducible matrix
8.2 Cauchy's interlacing theorem
8.3 The eigenvalues of A(G) and graph structure

Chapter 9 Chromatic polynomial
9.1 Induction
9.2 Two different formula for chromatic polynomial
9.3 Chromatic polynomials for several type of graphs
9.4 Estimate the color number
References
Bibliography