《图论及其应用》（第4版）出版发行。
见 http://staff.ustc.edu.cn/~xujm/indexChinesegraphs_4.htm
第四版前言
转眼间,《图论及其应用》出版已过 20 年, 3 次修订, 9 次印刷. 十多年来, 此书被推荐为全国研究生教学用书 (2002), 中国科学技术大学精品教材 (2008), “十一五”国家重点图书, 并获中国科学院首届教学成果（教材）二等奖 (2008), 中国科学技术大学优秀教材一等奖 (2009). 这些成绩和荣誉都离不开各级领导的支持与鼓励, 离不开读者及同行专家的厚爱与帮助. 借这次修订再版的机会, 笔者对关心支持此书编写和出版的各级领导, 各类评审委员会的专家, 同行学者和读者致以真诚的感谢. 感谢中国科学技术大学研究生院、教务处和 出版社在本书编写和出版过程中所给予的支持和帮助, 感谢国家自然科学基金多年来对作者研究项目的资助.
二十多年来, 笔者深刻感受到图论研究在国内的普及和蓬勃发展. 作为重要的数学工具和数学训练之一, 图论越来越被更多科学工作者认可、接受和应用, 越来越多的高等院校将图论列为相关专业本科生和研究生的必修课程. 尤为可喜的是, 国内图论研究队伍中年轻学者越来越多, 研究水平越来越高. 近几年越来越多学成回国的海外学者为国内图论研究和发展增添活力. 做为长期从事图论教学和研究工作者来说, 笔者有责任尽己所能再一次润饰, 提炼, 充实和完善《图论及其应用》, 为国内的图论发展尽绵薄之力. 这次修订基于第3 版, 在保持原版整体结构和叙述风格的基础上, 主要修订有如下几点.
1. 进一步规范图论术语和记号. 强调图是集V 及其 2 元关系E的数学结构(V,E), 它是个有序 2 元组. 将图的记号由“有序 3 元组(V,E,psi)” 改为“有序 2 元组(V,E_psi)”, 其中E_psi 是V 上由函数psi 确定的 2 元关系. 重图的概念并不难理解, 但陈述某些概念 (如, 图的同构) 有些累赘, 为初学者增加了理解上的困难. 重图只涉及边的结论, 如边连通度、匹配和边染色等. 如果回避它, 并不影响相关概念和结论的 陈述. 笔者曾试图避开重图, 但难以回避. 例如, 在陈述 Euler 图的背景时, K"onigsberg 七桥对应的图是重图; 简单平图的对偶图可能是重图; “中国邮路问题”的 Edmonds-Johnson 算法用到重图. 尽管如此, 这次修订将淡化重图, 主要概念和结论的陈述以简单图为主. 另外, 这次修订将进一步淡化有向图与无向图的区别, 故将术语“边割集”改为“割”(无向), “截边集”改为“有向割”（有向）, “强k 连通”改为“k 通”等; 将色类记号“pi=(V_1,cdots,V_k)” （有序集）改为无序集“pi={V_1,cdots,V_k}”等.
2. 调整部分章节的顺序, 并适当增减部分内容. 将第3 版的第1.8 节“距离和直径” 提前到本版的第,1.5 节, 因为它与第1.4节“路与连通”密切相关, 并将笛卡尔乘积概念和与之相关的直径结论调至这一节. 强调线图在“点”和“边”概念之间的桥梁作用, 添加了部分内容, 如“D 是Euler 有向图但且仅当它的线图L(D) 是 Hamilton 图”, 并解释涉及“点”和“边”问题差别之原因, 增加对线图研究背景的了解. 添加连通性、强连通性、有根树、圈向量和割向量存在性判定定理. 在平图与平面图一章中, 添加了平面图的 Hamilton 性内容; 将原第3.2 节“Kuratowski 定理”改为“平面图判定准则”, 添加并证明了几个判断定理; 添加外平面图和小图 (minor) 概念以及外平面图判断定理. 删去第 6 章的“应用”两字, 改第6.3节为“面染色与四色问题”和第6.4 节为“整数流与面染色”, 改写了“整数流”部分, 给出整数流与平图面染色关系定理的完整证明. 改写了第7.4 节, 添加网络设计原则, 笛卡尔乘积图的连通度、对换生成图和图的替代乘积等内容和最新研究成果.
3. 为尊重历史和知识产权, 所述结果尽可能标上原创作者和参考文献. 重大结论 (如 Euler 无向图判定定理, 矩阵--树定理和 Kuratowski 定理等) 尽可能解释历史原委. 为了方便读者查阅, 所有涉及到的作者和参考文献都标在正文引用的位置上. 笔者认为, 作为教科书, 不仅要传授专业知识, 也有尊重原创, 传承历史的责任和义务. 正是这些原创作者和继承者的不懈努力 和执着探索, 才使图论概念和结果得到不断的提炼、丰富和完善, 才有图论的今天, 后继者应该永远记住他们.
4. 为了方便读者阅读和理解文中内容, 本次修订增加了一些例子和大量辅助图, 辅助图并尽可能放在靠近内容的位置旁. 重新绘制了大部分图形使其更加美观. 为了减少篇幅, 有些的图形采用文图并排的形式; 所有习题、参考文献和附录中的记号和索引改为小体字. 重写了小结和进一步阅读的建议, 补充了某些问题的历史背景、有趣的典故、研究进展和参考文献.
5. 本次修订的所有文字和图形均由 LaTex 一气呵成, 所有定理（引理）、命题、例子和公式按章、节、序 三层编号, 图形按章和序二层编号, 自动生成.
6. 标以“*”的章节和正文中楷体内容, 或为正文的附加材料, 或具有一定的难度, 初学者暂时可以不读, 并不影响后继内容的阅读与学习. 标以“Delta”的章节或为应用, 或无重要理论结果, 从教学的角度, 可以安排自学.
感谢洪振木博士提供第3 版的勘误 (分别在第7 次和第8 次印刷时做了订正), 侯新民、潘向峰、黄佳、杨超、陆由、胡夫涛、李向军、 洪振木和何伟骅等博士分别审阅了全书的各个章节.
笔者敬请使用本教材的师生和读者多提宝贵意见.
徐俊明
2018年3月6日于
中国科学技术大学, 合肥
