|
《图论及其应用》教学大纲
(
每周4学时，共80学时)
本课程大纲以《Theory and Application of Graphs》为依据。按学校教学日历表安排，本课程总学时为80课时，授课时间共60个课时。课堂教学以概念和理论为主，通过证明定理和例子介绍图论命题的基本论证方法和技巧。课后安排少量必作习题和部分自学的内容。以达到掌握图论的基本概念、理论、方法和应用，提高利用数学方法解决实际问题能力的目的。为确保达到这个目的，课余预习和复习思考时间应不少于课堂教学时间的1.5倍。在教学过程中，视其具体情况，有可能对此大纲进行调整，请注意课堂通知。
0. 开课，导引，图论的简史，数学范畴归属，国内外理论研究和应用进展，最主要的参考书和参考杂志。课程要求和注意事项。有三本图论教材可以作为参考书：
1.徐俊明，《图论及其应用》（第三版，科大出版社，2011年4月第7次印刷）。
2.
Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications. The MaCmillan
Press ltd, London and Basingstoke, 1976。
中译本：《图论及其应用》（吴望名等译），科学出版社，1984。该书将无向图和有向图分开论述，图的理论部分写得通俗易懂，应用材料很精彩，习题很多，适合作一般大学本科图论教材。缺点是理论部分写得太浅，有点陈旧（该书的第二版即将出版）。张克民、林国宁和张忠辅《图论及其应用习题解答》（清华大学出版社，1988）已将该书的习题作了全部解答。
3.
Chartrand,
G, and Lesniak, L., Graphs and Digraphs (Second Edition).
Wadsworth, Inc, Belmont and California, 1986。该书将无向图和有向图交叉叙述，
内容较多，专题叙述较为深入。但几乎不涉及图论应用，各专题之间的联系不够紧密，习题难度不大。
另有两篇综述文献值得一读（中译文）：
1.) C.Thomassen, 图论的回顾,数学译林,1988,
65-75;
2.) B.Bollobas, 图论的未来,
数学译林,15(1996), No.2, 109-110.
1.
内容是1.1节和1.2节。图的基本概念、介绍基本记号、图的同构和某些特殊的图类，如完全图、竞赛图和二部分图。强调图是一个特殊的代数结构（有限集和定义在该集上的二元关系），几何图形只是它的一种直观表示。因此，图同构的概念是自然的。介绍超立方体和有向图与二部分图的关系。习题：1.1.1,
1.2.4 和 1.2.5，1.2.6。
2.
内容是1.3节和1.4节。介绍图的顶点度概念和图的基本运算和记号，笛卡尔乘积和线图运算。掌握图论第一定理（边数和顶点度之间的基本关系）和它的证明。通过若干例子，掌握证明和分析方法。习题：1.3.5,
1.3.6 和 1.4.2, 1.4.4, 1.4.6。
3.内容是1.5节和1.6节。链、迹和路的概念、关系、区别，连通和强连通概念，它们的区别和联系。连通和强连通的判定，通过证明定理1.2和若干例子，介绍图论中常用的基本论证方法和技巧。然后介绍距离和直径概念，以及有关结论。习题：1.5.4,
1.5.6， 1.5.7，1.6.3,
1.6.5 和 1.6.6。
4.内容是1.7。回和圈的概念、区别和基本图论结果（定理1.5）。理解和掌握竞赛图点泛圈性结果。作为回或者圈的应用，介绍二部分图的判定准则（定理1.6）和若干例子。习题：1.7.4,
1.7.6 和 1.7.7。
5.内容是1.8节和1.9节。Euler图和Hamilton图的概念。重点掌握Euler图的判定准则（定理1.7）和Hamilton图的充分条件（定理1.9）及其推论。定理1.10的证明可以暂时不读，但推论必须了解。掌握图的Euler性和Hamilton性区别。掌握和学会运用定理1.9的证明技巧。作为例子，介绍De
Bruijn图和Kautz图。习题：1.8.2，1.8.3，1.9.3
和 1.9.7。
6.内容是1.10节。介绍图的另一种表示－图的邻接矩阵和关联矩阵。弄清同构图的邻接矩阵的置换相似性和关联矩阵的置换相抵性。利用这种表示，可以借助代数方法来研究图的结构性质，有此产生代数图论。证明定理1.11并通过若干例子，介绍代数方法在图论中的应用。习题：1.10.4
和 1.10.5; 选作1.10.6。自习1.11节。
7.内容是1.11节。图论在矩阵论中的应用。
8.内容是2.1节，它是本章的基础。介绍树（林）和支持树（林）的基本性质。弄清余树（林）、割边集和键的概念，圈、键与余树（林）的关系。习题：2.1.2,
2.1.3 和 2.1.4。
9.内容是2.2节，它是本章的重点。弄清圈空间概念，重点是边空间中两个互补的子空间：圈空间和键空间的维数和基的生成。通过这节结果和论证方法，进一步了解图的矩阵表示的重要性和代数方法在图论中的具体应用。习题：2.2.4,
2.2.6 和 2.2.7。
10.内容是2.3节。这节讨论连通图支撑树的计数，本质上是边空间理论的应用，矩阵理论、图论和代数方法的结合，导出若干支撑树计数公式。习题：2.3.2,
2.3.3 和 2.3.6(选作)。
11.内容是2.4和2.5节。介绍两个实际问题的应用：最小连接和最短路问题，弄清他们的联系和区别，并介绍解决这两个问题的有效算法。重点是学会怎样将一个实际问题转化为图论问题，然后利用图论方法去解决问题。学会分析算法的有效性。习题：2.4.1,
2.4.2 和 2.5.2。自习2.6节。
12.重点介绍平面图和平图的基本概念和性质，Euler公式，Kuratowski
定理（3.6）和平图的几何对偶概念。有关Kuratowski
定理的各种变形，可以参阅一篇综述文献：D.Archdeacon, Variations on a
theme of Kuratowski. Discrete Mathematics, 302(2005), 22–31 (Kuratowski.pdf)。习题：3.1.4,
3.1.6 和 3.2.3。本章的其它内容安排自习。
13.内容是4.1节和4.2节，是本章的基础。介绍网络流，截和局部连通度的概念，弄清截与割的区别。重点掌握和证明最大流最小截定理（4.1）、两种形式的Menger定理（4.3和4.3）和证明方法,了解这三个定理的等价性。习题：4.1.2,
4.1.5,4.2.3,
4.2.4 和
4.2.5。
14.内容是4.3节。图的整体连通度概念，重点掌握Whitney不等式（定理4.4）和Whitney关于k连通图的判定准则（定理4.5）。通过定理和具体例子的证明，介绍有关连通度命题证明的基本方法。习题：4.3.3,
4.3.10，4.3.11 和 4.3.12。
15.内容是4.4和4.5节。通过运输方案的设计和最优运输方案的设计，介绍求整容量网络最大流的标号算法和求整容量网络最小费用最大流算法。该算法的基础是定理4.6和定理4.8。因此，要弄清增广路和增广圈概念概念。习题：4.4.2
和 4.5.2。
16.
内容是4.6。通过解决中国投递员问题，介绍求加权图的最优邮路算法，它与网络流的密切关系和转化过程。习题：4.6.2
和 4.6.3。自习4.7节。
17.
内容是5.1节（上）。介绍匹配概念，研究二部分图和一般图中完备匹配的存在性。重点掌握Hall定理（5.1）和Tutte定理（5.2），了解这两个定理证明方法以及它们与最大流最小截定理、Menger定理的等价性。通过若干例子，介绍匹配理论的基本应用。习题：5.1.1,
5.1.2，5.1.3, 5.1.5，5.1.6。
18.内容是5.1节（下）和5.2.节。介绍点覆盖和König定理（5.3）以及相关定理的等价性。介绍图的独立集和独立数的概念，了解计算独立数的困难性。介绍独立数与连通度及图的Hamilton性之间的关系。习题：5.2.5,
5.2.6 和 5.2.7。
19.内容是5.3节。作为匹配理论的应用，通过人员安排问题，介绍求二部分图中完备匹配的匈牙利算法。算法的基础是Hall定理、定理5.8和定理5.9。习题：5.3.1和
5.3.5。
20.内容是5.4节。通过最优人员安排问题，介绍求二部分加权图中最大（小）全完备匹配的Kuhn-Munkers算法，掌握问题的转化。了解绍排序问题的难度和求排序问题的近似算法。习题：5.4.4。
21.内容是5.5节。介绍著名的货郎担问题，它是NPC问题的杰出代表。掌握货郎担问题的两种提法，怎样将一般图的货郎担问题转化为求满足三角不等式的完全加权图中最优Hamilton圈问题。介绍一个近似算法，它是该课程中介绍的著名算法的应用和总结，计算它的的性能比。习题：5.5.1和5.5.3。
22.
内容是6.1。介绍点染色的基本概念和结果，弄清点染色与独立集之间的关系。重点掌握定理6.1、6.2和6.3。作为应用，列举若干例子。习题：6.1.4 和6.1.5。
23.内容是6.2节。介绍边染色的基本概念和结果，弄清边染色与匹配之间的关系。重点掌握定理6.3。介绍图的分类问题和4色问题。习题：6.2.2，6.2.4 和6.2.5。
24.期终总结，布置期终复习和考试事宜。
25.
习题课。
26.期末考试（闭卷）。
|
