|
图论中的人与事：
1.
J. Petersen 与 Petersen 图
2.
L. Euler 与 Euler 图
3.
K. Kuratowski 与 Kuratowski
定理
4.
K. Menger 与
Menger 定理
5.
H. Whitney 与 Whitney 不等式
| |
（“十一”国家重点图书，教育部推荐研究生教学用书，中国科学技术大学精品教材）
 |
标题:
|
图论及其应用（第4版）
|
|
作者:
|
徐俊明
|
| 出版社:
|
中国科学技术大学出版社
|
| 书号:
|
ISBN
978-7-312-04453-3
页数:
362＋16
|
| 出版日期:
|
2019.03
|
第10次印刷：
|
2019.03
|
| 书价:
|
60:00
|
字数：
|
506千字
|
|
|
邮购: |
中国科学技术大学出版社
|
内容简介
本书着眼于有向图，将无向图作为特例，在一定的深度和广度上系统地阐述了图论的基本概念、理论和方法以及基本应用．全书内容共分７章，包括Euler回与Hamilton圈、树与图空间、平面图、网络流与连通度、匹配与独立集、染色理论、图与群以及图在矩阵论、组合数学、组合优化、运筹学、线性规划、电子学以及通讯和计算机科学等多方面的应用．每章分为理论和应用两部分，章末有小结和参考文献．各章内容之间联系紧密，许多著名的定理给出最新最简单的多种证明．每小节末都有大量习题，书末附有记号和名词索引．
读者对象
本书既可用作高校数学系、应用数学系、计算机科学系、电子学系、自动化系、管理科学系和相关的研究所的研究生和高年级本科生选修课教材，也可用作高校和研究所从事相关专业的教师和研究人员以及图论工作者的参考书．
第四版前言
转眼间,《图论及其应用》出版已过 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日于
中国科学技术大学, 合肥
|