《图论及其应用》教学大纲

                                                     ( 2006 年09月04日---- 2007年02月03日)

本课程大纲以《Theory and Application of Graphs》为依据。按学校教学日历表安排，本课程总学时为54课时，授课时间共50个课时。课堂教学以概念和理论为主，通过证明定理和例子介绍图论命题的基本论证方法和技巧。课后安排少量必作习题和部分自学的内容。以达到掌握图论的基本概念、理论、方法和应用，提高利用数学方法解决实际问题能力的目的。为确保达到这个目的，课余预习和复习思考时间应不少于课堂教学时间的1.5倍。在教学过程中，视其具体情况，有可能对此大纲进行调整，请注意课堂通知。

1.  09.05（星期二）: 开课，导引，图论的简史，数学地位，国内外理论研究和应用进展，最主要的参考书和参考杂志。课程要求和注意事项。有三本图论教材可以作为参考书：

1.徐俊明，《图论及其应用》（第二版），2004年8月出版。（注意：初版于1998年1月第1次印刷有许多勘误，在2000年9月第2次印刷版本中作了一些订正，但版面未变。）

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.

2.  09.08（星期五）: 内容是1.1节和1.2节。图的基本概念、介绍基本记号、图的同构和某些特殊的图类，如完全图、竞赛图和二部分图。强调图是一个特殊的代数结构（有限集和定义在该集上的二元关系），几何图形只是它的一种直观表示。因此，图同构的概念是自然的。介绍超立方体和有向图与二部分图的关系。习题：1.1.1, 1.2.4 和 1.2.5，1.2.6。

3.  09.12（星期二）: 内容是1.3节和1.4节。介绍图的顶点度概念和图的基本运算和记号，线图运算。掌握图论第一定理（边数和顶点度之间的基本关系）。若干例子。习题：1.3.5, 1.3.6 和 1.4.2, 1.4., 1.4.6。

4. 09.15（星期五）: 内容是1.5节和1.6节。链、迹和路的概念、关系、区别，连通和强连通概念，它们的区别和联系。通过证明定理1.2和若干例子，介绍图论中常用的基本论证方法和技巧。然后介绍直径概念。习题：1.5.4, 1.5.6， 1.5.7，1.6.3, 1.6.5 和 1.6.6。

5. 09.19（星期二）: 内容是1.7。回和圈的概念、区别和基本图论结果（定理1.5）。理解和掌握竞赛图点泛圈性结果。作为回或者圈的应用，介绍二部分图的判定准则（定理1.6）和若干例子。习题：1.7.4, 1.7.6 和 1.7.7。

6. 09.22（星期五）: 内容是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。

7. 09.26（星期二）: 内容是1.10节。介绍图的另一种表示－图的邻接矩阵和关联矩阵。弄清同构图的邻接矩阵的置换相似性和关联矩阵的置换相抵性。利用这种表示，可以借助代数方法来研究图的结构性质，有此产生代数图论。证明定理1.11并通过若干例子，介绍代数方法在图论中的应用。习题：1.10.4 和 1.10.5; 选作1.10.6。自习1.11节。

8. 10.06（星期五）:  内容是1.11节。图论在矩阵论中的应用。

9. 10.10（星期二）: 内容是2.1节，它是本章的基础。介绍树（林）和支持树（林）的基本性质。弄清余树（林）、割边集和键的概念，圈、键与余树（林）的关系。习题：2.1.2, 2.1.3 和 2.1.4。

10. 10.13（星期五）: 内容是2.2节，它是本章的重点。弄清圈空间概念，重点是边空间中两个互补的子空间：圈空间和键空间的维数和基的生成。通过这节结果和论证方法，进一步了解图的矩阵表示的重要性和代数方法在图论中的具体应用。习题：2.2.4, 2.2.6 和 2.2.7。

11. 10.17（星期二）: 内容是2.3节。这节讨论连通图支撑树的计数，本质上是边空间理论的应用，矩阵理论、图论和代数方法的结合，导出若干支撑树计数公式。习题：2.3.2, 2.3.3 和 2.3.6(选作)。

12. 10.20（星期五）: 内容是2.4和2.5节。介绍两个实际问题的应用：最小连接和最短路问题，弄清他们的联系和区别，并介绍解决这两个问题的有效算法。重点是学会怎样将一个实际问题转化为图论问题，然后利用图论方法去解决问题。学会分析算法的有效性。习题：2.4.1, 2.4.2 和 2.5.2。自习2.6节。

13. 10.24（星期二）: 重点介绍平面图和平图的基本概念和性质，Euler公式，Kuratowski 定理（3.6）和平图的几何对偶概念。习题：3.1.4, 3.1.6 和 3.2.3。本章的其它内容安排自习。

14.10.31（星期二）: 内容是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。

15.11.03（星期五）:  内容是4.3节。图的整体连通度概念，重点掌握Whitney不等式（定理4.4）和Whitney关于k连通图的判定准则（定理4.5）。通过定理和具体例子的证明，介绍有关连通度命题证明的基本方法。习题：4.3.3, 4.3.10，4.3.11 和 4.3.12。

16.11.07（星期二）: 内容是4.4和4.5节。通过运输方案的设计和最优运输方案的设计，介绍求整容量网络最大流的标号算法和求整容量网络最小费用最大流算法。该算法的基础是定理4.6和定理4.8。因此，要弄清增广路和增广圈概念概念。习题：4.4.2 和 4.5.2。

17.11.10（星期五）:  内容是4.6。通过解决中国投递员问题，介绍求加权图的最优邮路算法，它与网络流的密切关系和转化过程。习题：4.6.2 和 4.6.3。自习4.7节。

18.11.14（星期二）:  内容是5.1节（上）。介绍匹配概念，研究二部分图和一般图中完备匹配的存在性。重点掌握Hall定理（5.1）和Tutte定理（5.2），了解这两个定理证明方法以及它们与最大流最小截定理、Menger定理的等价性。习题：5.1.1, 5.1.2 和 5.1.5。

19.11.17（星期五）: 内容是5.1节（下）。介绍点覆盖概念和König定理（5.3）以及它与某些定理的等价性。通过若干例子，介绍匹配理论的基本应用。习题：5.1.3, 5.1.6 和 5.1.10。

20.11.21（星期二）: 内容是5.2。介绍图的独立集和独立数的概念，了解计算独立数的困难性。介绍独立数与连通度及图的Hamilton性之间的关系。习题：5.2.5, 5.2.6 和 5.2.7。

21.11.24（星期五）:  内容是5.3节和5.4节。作为匹配理论的应用，通过人员安排问题和最优人员安排问题，介绍求二部分图中完备匹配的匈牙利算法。算法的基础是Hall定理、定理5.8和定理5.9。习题：5.3.1, 5.3.5 和 5.4.4。

22.11.28（星期二）: 内容是5.5节。介绍著名的货郎担问题，它是NPC问题的杰出代表。掌握货郎担问题的两种提法，怎样将一般图的货郎担问题转化为求满足三角不等式的完全加权图中最优Hamilton圈问题。介绍一个近似算法，它是该课程中介绍的著名算法的应用和总结，计算它的的性能比。习题：5.5.1和5.5.3。

23.12.01（星期五）:  习题课。

24.12.05（星期二）:   内容是6.1。介绍点染色的基本概念和结果，弄清点染色与独立集之间的关系。重点掌握定理6.1、6.2和6.3。作为应用，列举若干例子。习题：6.1.4 和6.1.5。

25.12.07（星期五）：内容是6.2节。介绍边染色的基本概念和结果，弄清边染色与匹配之间的关系。重点掌握定理6.4。介绍图的分类问题和4色问题。习题：6.2.2，6.2.4 和6.2.5。

26.12.11（星期二）: 期终总结，布置期终复习和考试事宜。

27.12.14（星期五）:  习题课。

27.12.24（星期日）: 期末考试（闭卷）。晚上7：00－9：00。地点：4601教室（数学系本科生），4602教室（研究生和少年班本科生）。