|
《图论及其应用》教学大纲
(
2003
年2月17日
-- 7月4日)
本课程大纲以《图论及其应用》（徐俊明，科大出版社，1998年版）为依据。按学校教学日历表安排，本学期授课时间72课时，因故停课一次（5月19日），习题课、小测验和总结复习8课时，实际授课时间共62个课时。课堂教学以概念和理论为主，通过证明定理和例子介绍图论命题的基本论证方法和技巧。课后安排少量必作习题和部分自学的内容。以达到掌握图论的基本概念、理论、方法和应用，提高利用数学方法解决实际问题能力的目的。为确保达到这个目的，课余预习和复习思考时间应不少于课堂教学时间的1.5倍。在教学过程中，视其具体情况，有可能对此大纲进行调整，请注意课堂通知或者网上通知。
1).
2.17（星期一）:
开课，导引，图论的简史，数学地位，国内外理论研究和应用进展，最主要的参考书和参考杂志。课程要求和注意事项。有两本图论教材可以作为参考书：
1.
Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications. The MaCmillan
Press ltd, London and Basingstoke, 1976。
中译本：《图论及其应用》（吴望名等译），科学出版社，1984。该书将无向图和有向图分开论述，图的理论部分写得通俗易懂，应用材料很精彩，习题很多，适合作一般大学本科图论教材。缺点是理论部分写得太浅，有点陈旧（该书的第二版即将出版）。张克民、林国宁和张忠辅《图论及其应用习题解答》（清华大学出版社，1988）已将该书的习题作了全部解答。
2.
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).
2.19（星期三）:
内容是1.1节和1.2节。图的基本概念、介绍基本记号、图的同构和某些特殊的图类，如完全图、竞赛图和二部分图。强调图是一个特殊的代数结构（有限集和定义在该集上的二元关系），几何图形只是它的一种直观表示。因此，图同构的概念是自然的。介绍超立方体和有向图与二部分图的关系。习题：1.1.1,
1.2.4 和 1.2.7。
3).
2.24（星期一）: 内容是1.3节和1.4节。介绍图的顶点度概念和图的基本运算和记号，线图运算。掌握图论第一定理（边数和顶点度之间的基本关系）。若干例子。习题：1.3.4,
1.3.5 和 1.4.5。
习题1.3.8是著名的Sperner引理,
利用它可以给出Brouwer不动点定理的图论证明。参阅J. A. Bondy
and U. S. R. Murty, Graph Theory with Applications, Macmillan Press LTD, 19976,
Section 1.9。
关于线图和笛卡儿乘积图的进一步性质可参阅Junming
Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer
Academic Publisheres, 2001, Sections 2.1 and 2.3。有一篇关于线图研究的综述文献：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。
4).
2.26（星期三）:
内容是1.5节。链、迹和路的概念、关系、区别，连通和强连通概念，它们的区别和联系。通过证明定理1.2和若干例子，介绍图论中常用的基本论证方法和技巧。习题：1.5.4,
1.5.6 和 1.5.10。
习题1.4.11叙述了著名的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。
5).
3.03（星期一）:
内容是1.6。回和圈的概念、区别和基本图论结果（定理1.3）。作为回或者圈的应用，介绍二部分图的判定准则（定理1.4）和若干例子。习题：1.6.2,
1.6.4 和 1.6.11。
关于路和圈中的研究问题和进展可参阅一篇综述文献：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.
6).
3.05（星期三）:
内容是1.7节。Euler迹、Euler回和Euler图的概念。介绍著名的Königsber七桥问题和Euler图的判定准则（定理1.5）。作为例子，介绍De
Bruijn图。习题：1.7.2 和 1.7.3。
有一篇关于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。
7).
3.10（星期一）:
内容是1.8。弄清Hamilton圈和Hamilton图的概念，它们与Euler回和Euler图区别，困难性。重点介绍充分条件（定理1.7），还可举两个例子。定理1.8的证明有一定难度，有余力的同学可以通过自学弄懂它。习题：1.8.3,
1.8.6 和 1.8.7。
有一篇关于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。
8).
3.12（星期三）:
内容是1.9节。介绍图的另一种表示－图的邻接矩阵和关联矩阵。弄清同构图的邻接矩阵的置换相似性和关联矩阵的置换相抵性。利用这种表示，可以借助代数方法来研究图的结构性质，有此产生代数图论。证明定理1.9并通过若干例子，介绍代数方法在图论中的应用。习题：1.9.4
和 1.9.5; 选作1.9.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.
9).
3.17（星期一）:
内容是1.10。作为图论应用，介绍本原矩阵的本原指数。定理1.11是关于本原指数的一个基本结果，它将被归结为图论结果。定理1.9和定理1.10起了关键作用。给出两个例子以说明本原矩阵的本原指数的基本方法。习题：1.10.2 和
1.10.3。
关于图论在矩阵论的应用,可见参考书:
1.)
李乔, 矩阵论八讲, 上海科学技术出版社,1988, 第6章.
2.)
柳柏濂, 组合矩阵论,科学出版社,1998.
10).
3.19（星期三）:
习题课, 小测验（作在作业本上，交第一次作业）。
11).
3.24（星期一）:
内容是2.1节和2.2节，它是本章的基础。介绍树（林）和支持树（林）的基本性质。弄清余树（林）、割边集和键的概念，圈、键与余树（林）的关系。习题：2.1.2,
2.1.5 和 2.2.3。
12).
3.26（星期三）:
内容是2.3节，它是本章的重点。弄清圈空间概念，重点是边空间中两个互补的子空间：圈空间和键空间的维数和基的生成。通过这节结果和论证方法，进一步了解图的矩阵表示的重要性和代数方法在图论中的具体应用。习题：2.3.4,
2.3.6 和 2.3.7。
13).
3.31（星期一）:
内容是2.4节。这节讨论连通图支撑树的计数，本质上是边空间理论的应用，矩阵理论、图论和代数方法的结合，导出若干支撑树计数公式。习题：2.4.2,
2.4.3 和 2.4.6。
14).
4.02（星期三）:
内容是2.5和2.6。介绍两个实际问题的应用：最小连接和最短路问题，弄清他们的联系和区别，并介绍解决这两个问题的有效算法。重点是学会怎样将一个实际问题转化为图论问题，然后利用图论方法去解决问题。学会分析算法的有效性。习题：2.5.1,
2.5.1 和 2.6.2。自习2.7节。
15).
4.07（星期一）:
内容是3.1节，是本章的重点。介绍平面图和平图的基本概念和性质，Euler公式。习题：3.1.4,
3.1.6 和 3.1.9。
16).
4.09（星期三）:
内容是3.2节和3.3节，重点掌握 Kuratowski 定理（3.6）和几何对偶图的概念，其它内容可作一般了解。习题：3.2.3,
3.3.2 和 3.3.6。自习3.4节和3.5节。
17).
4.14（星期一）:
内容是4.1节，是本章的基础。介绍网络流和截的概念，弄清截与割的区别。重点掌握和证明最大流最小截定理（4.1）。习题：4.1.2 和
4.1.4。
18).
4.16（星期三）: 内容是4.2，是本章的重点。弄清图的局部连通度概念，重点掌握两种形式的Menger定理（4.3和4.3），证明方法和它们与最大流最小截定理的等价性。习题：4.2.2 和
4.2.3。
19).
4.21（星期一）:
内容是4.3节。图的整体连通度概念，重点掌握Whitney不等式（定理4。4）和Whitney关于k连通图的判定准则（定理4.5）。通过定理和具体例子的证明，介绍有关连通度命题证明的基本方法。习题：4.3.3,
4.3.11 和 4.3.12。
20).
4.23（星期三）:
内容是4.4。通过运输方案的设计，介绍求整容量网络最大流的标号算法。该算法的基础是定理4.6。因此，要弄清增广路的概念。习题：4.4.2
和 4.4.6（可选作）。
21).
4.28（星期一）:
内容是4.5节。通过最优运输方案的设计，介绍求整容量网络最小费用最大流算法。该算法的基础是定理4.8。因此，要弄清增广圈概念。习题：4.5.2
和 4.5.3（可选作）。
22).
4.30（星期三）:
内容是4.6。通过解决中国投递员问题，介绍求加权图的最优邮路算法，它与网络流的密切关系和转化过程。习题：4.6.2
和 4.6.3。自习4.7节。
23).
5.04（星期一）:
习题课, 小测验（作在作业本上，交第二次作业）。
24).
5.07（星期三）:
内容是5.1节（上）。介绍匹配概念，研究二部分图和一般图中完备匹配的存在性。重点掌握Hall定理（5.1）和Tutte定理（5.2），了解这两个定理证明方法以及它们与最大流最小截定理、Menger定理的等价性。习题：5.1.1,
5.1.2 和 5.1.5。
25).
5.12（星期一）:
内容是5.1节（下）。介绍点覆盖概念和König定理（5.3）以及它与某些定理的等价性。通过若干例子，介绍匹配理论的基本应用。习题：5.1.3,
5.1.6 和 5.1.9。
26).
5.14（星期三）:
内容是5.2。介绍图的独立集和独立数的概念，了解计算独立数的困难性。介绍独立数与连通度及图的Hamilton性之间的关系。习题：5.2.5,
5.2.6 和 5.2.7。
27).
5.19（星期一）: 内容是5.3节。作为匹配理论的应用，通过人员安排问题，介绍求二部分图中完备匹配的匈牙利算法。算法的基础是Hall定理、定理5.9和定理5.10。习题：5.3.2,
5.3.5 和 5.3.6。
28).5.21（星期三）:
内容是5.4。通过最优人员安排问题，介绍求加权完全二部分图中最大（或者最小）权完备匹配的有效算法。算法的基础是定理5.11。作为算法的应用，介绍工作排序问题的近似算法。习题：5.4.4 和
5.4.6。
29).
5.26（星期一）:
内容是5.5节。介绍著名的货郎担问题，它是NPC问题的杰出代表。掌握货郎担问题的两种提法，怎样将一般图的货郎担问题转化为求满足三角不等式的完全加权图中最优Hamilton圈问题。介绍一个近似算法，它是该课程中介绍的著名算法的应用和总结，计算它的的性能比。习题：5.5.1和5.5.3。自习5.6节。
30).
5.28（星期三）: 自习
31). 6.02（星期一）:
内容是6.1。介绍点染色的基本概念和结果，弄清点染色与独立集之间的关系。重点掌握定理6.1、6.2和6.3。作为应用，列举若干例子。习题：6.1.5 和6.1.6。
32).
6.04（星期三）: 内容是6.2节。介绍边染色的基本概念和结果，弄清边染色与匹配之间的关系。重点掌握定理6.4。介绍图的分类问题。习题：6.2.2，6.2.4 和6.2.5。
33).
6.09（星期一）:
习题课，期终总结，布置期终复习和考试事宜。
期末考试时间：2003年06月14日（星期六）上午8：30－10：30，地点：4703教室
|
