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

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

2. Bondy, J. A. and Murty, U. S. R., Graph Thory with Application. The MaCmillan Press ltd, London and Basingstoke, 1976 （第二版于2008年出版，GTM244）。 中译本：《图论及其应用》（吴望名等译），科学出版社，1984。该书将无向图和有向图分开论述，图的理论部分写得通俗易懂，应用材料很精彩，习题很多，适合作一般大学本科图论教材。缺点是理论部分写得太浅，有点陈旧 ）。张克民、林国宁和张忠辅《图论及其应用习题解答》（清华大学出版社，1988）已将该书的习题作了全部解答。

3.Chartrand, G, and Lesniak, L., Graphs and Digraphs (Second Edition). Wadsworth, Inc, Belmont and California, 1986。该书将无向图和有向图交叉叙述， 内容较多，专题叙述较为深入。但几乎不涉及图论应用，各专题之间的联系不够紧密，习题难度不大。

4.Diestel, R., GraphTheory , Springer-Verlag New York, 2005. 这是一本研究生水平的教材，理论难度很大，但很受欢迎。

另有两篇综述文献值得一读（中译文）：

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。

关于线图和笛卡儿乘积图的进一步性质可参阅Junming Xu,Toplogical Structure and Analysis of Interconnection Networks, Kluwer Academic Publisheres, 2001, Sections 2.1 and 2.3。和《组合网络理论》，科学出版社，北京，2007.

有一篇关于线图研究的综述文献：R. L. Hemminger, and  L. W. Beineke, Line graphs and line digraphs.   Selected Topics in Graph Theory , I, (edited by L. W. Beineke, and R. J. Wilson),  Academic Press INC, 1978, 271- 305。

习题1.4.7叙述了著名的Ramsey定理。该习题的 部分解答可参阅J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press LTD, 19976, Section 7.2。有两本有关Ramsey理论的专题著作可以参阅。

1.) R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory. John Wiley & Sons, 1980.

2.) 李乔， 拉姆塞理论， 湖南教育出版社， 1991。  

3.内容是1.5节 和1.6节。链、迹和路的概念、关系、区别，连通和强连通概念，它们的区别和联系。连通和强连通的判定。距离、直径和平均距离的概念，一般图直径的上界和下界，理解和掌握笛卡尔乘积图和因子图的直径、图和线图直径之间的关系 （定理1.3和定理1.4）。通过定理的证明和若干例子，介绍图论中常用的基本论证方法和技巧。习题：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。

关于路和圈中的研究问题和进展可参阅一篇综述文献：J. A. Bondy, Basic graph theory: paths and circuits. Handbook of Combinatorics (edited by R. L. Graham, M. Grotschel and L. Lovasz), Vol.1(1995),3-110.

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。

有一篇关于Euler问题的综述文章可以参阅：

H. Fleischer, Eulerian graphs. Selected Topics in Graph Theory , II, (edited by L. W. Beineke, and R. J. Wilson),  Academic Press INC, 1983, 17-53。

有 二篇关于Hamilton问题的综述文章可以参阅：

J. C. Bermond, Hamiltonian graphs. Selected Topics in Graph Theory , I, (edited by L. W. Beineke, and R. J. Wilson),  Academic Press INC, 1978, 127- 167。 

R.J. Gould, Updating the Hamiltonian Problem - A Survey.  Journal of Graph Theory   15 (1991), 121-157.  

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

建议参阅的两本代数图论教材和一本关于图的譜的专题著作(系资料室有原版): 

1.) N. Biggs, Algebraic Graph Theory (Second Edition), Cambridge University Press, 1993; 

2.) C. Golsil and G. Royle, Algebraic Graph Theory, Springer, 2001. 

3.) D. M. Cvetkoie, M. Doob, and H. Sachs, Spectura of Graphs. VEB Deutscher Verlag der Wissenschaften, 1982.

7.内容是1.11节。图论在矩阵论中的应用。介绍本原方阵和本原指数概念和一些基本结果。了解本原方阵与图的关系，利用图的性质来证明本原指数中的结论 。重点关注问题的转换和证明技巧。

关于图论在矩阵论的应用,可见 中文参考书:

1.) 李乔, 矩阵论八讲, 上海科学技术出版社,1988, 第6章.

2.) 柳柏濂, 组合矩阵论,科学出版社,1998.

8.习题课。

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

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

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

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

13.重点介绍平面图和平图的基本概念和性质，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.1.7。

14. 介绍图的组合对偶概念，平面图的组合对偶与几何对偶之间的关系。习题：3.2.3。本章的其它内容安排自习。

15.内容是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。

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

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

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

19. 内容是5.1节（上）。介绍匹配概念，研究二部分图和一般图中完备匹配的存在性。重点掌握Hall定理（5.1）和Tutte定理（5.2），了解这两个定理证明方法以及它们与最大流最小截定理、Menger定理的等价性。通过若干例子，介绍匹配理论的基本应用。习题：5.1.1, 5.1.2，5.1.3, 5.1.5，5.1.6。

20.内容是5.1节（下）和5.2.节。介绍点覆盖和König定理（5.3）以及相关定理的等价性。介绍图的独立集和独立数的概念，了解计算独立数的困难性。介绍独立数与连通度及图的Hamilton性之间的关系。习题：5.2.5, 5.2.6 和 5.2.7。

21.内容是5.3节。作为匹配理论的应用，通过人员安排问题，介绍求二部分图中完备匹配的匈牙利算法。算法的基础是Hall定理、定理5.8和定理5.9。习题：5.3.1和 5.3.5。

22.内容是5.4节。通过最优人员安排问题，介绍求二部分加权图中最大（小）全完备匹配的Kuhn-Munkers算法，掌握问题的转化。了解绍排序问题的难度和求排序问题的近似算法。习题：5.4.4。

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

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

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

26.期终总结，布置期终复习和考试事宜。

27. 习题课。

28.期末考试（闭卷）。时间：2010年12月27日（星期一）晚上7：00--9：00。地点：5102教室（数学系本科生）和5103教室（研究生和其他系本科生）。