图论及其应用
2013-8-8
清华大学出版社
张清华,陈六新,李永红
本书是根据作者多年从事图论教学的经验，综合国内外同类优秀教材的优势，并结合学科最新发展状况编写而成。本书较为系统地介绍了图论课程中的基本知识，注重理论与实践结合，突出算法思想，适合于工科教学需要。
全书分6章，第1章介绍图论的主要预备知识，第2章介绍图的基本概念，第3章介绍树与最短路径，第4章介绍网络流与Petri网，第5章介绍独立集与匹配，第6章介绍平面图与着色。各章之后配有适当难度的习题，便于学生课后练习。本书可以作为高等院校硕士研究生或高年级本科生的教材，也可以作为研究人员的参考用书。
目录
第1章图论预备知识1
1.1集合的基本概念与运算1
1.2二元关系的基本概念和性质2
1.3等价关系与偏序关系16
1.4函数22
1.5算法的时间复杂性25
习题131第2章图34
2.1图的基本概念34
2.2图的连通性43
2.3图的矩阵表示49
2.4欧拉图与哈密顿图54
习题265第3章树与最短路径70
3.1树及其等价定义70
3.2生成树73
3.3根树及其应用77
3.4最短路算法87
3.5中国邮递员问题95
3.6旅行售货员问题98
习题3100第4章网络优化与Petri网102
4.1网络流与截集102
4.2最大流问题及其算法105
4.3最小费用流算法110
4.4Petri网简介119
习题4123第5章独立集、支配集与匹配126
5.1独立集126
5.2支配集132
5.3匹配137
5.4最大匹配算法143
5.5最优匹配146
5.6Ramsey数151
习题5156第6章平面图与着色159
6.1平面图159
6.2平面图的性质——欧拉公式163
6.3平面图的判断166
6.4图的平面性检测168
6.5对偶图与平面图的着色171
6.6图的色多项式177
习题6181
参考文献184
