Welcome to Junming Xu's Website                           

 
 Homepage    My Books      Research  Graduate Programs  Students  Courses  Others   Related links
  Courses
 
 
Homepage
 
 
 
 
 
讲稿
Graph22.pdf
Graph23.pdf
 
 
 
图论习题
 
Graphs-ex01.pdf
Graphs-ex02.pdf
Graphs-ex03.pdf
Graphs-ex04.pdf

Graphs-ex05.pdf

Graphs-ex06.pdf
 
 
 
 
习题提示
 
 
 

                图论》教学大纲 (课程编号:MA04242

                                                     ( 2012 903 -- 2013125)

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

0开课,浅谈组合学与图论,图论概念,简史,数学归属,国内外理论研究和应用进展,最主要的参考书和参考杂志。课程要求和注意事项

   有几本图论教材可以作为参考书:

  • 徐俊明,《图论及其应用》(第三版,2010年3月)。(注意:初版于1998年1月第1次印刷有许多勘误,在2000年9月第2次印刷版本中作了一些订正,但版面未变。2011年4月第7次印刷对前6章进行了勘误,第7章中勘误没有纠正。)

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

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

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

  • 关于有向图,有一本讨论非常详尽的参考书(网上可以下载):J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London, 2000.

    有关图论历史:

  • Biggs N L, Lloyd E K, Wilson R J. Graph Theory 1736-1936. Oxford: Clarendon Press, 1976

  • Robin J. Wilson, History of graph theory. Handbook of graph theory (Edited by Jonathan L. Gross and Jay Yellen). Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2004, pp.29--49.

    两篇综述文献值得一读(中译文):

  • C.Thomassen, 图论的回顾,数学译林,1988, 65-75; 

  • B.Bollobas, 图论的未来, 数学译林,15(1996), No.2, 109-110.

   有关图论文献的查阅:

  • 查阅图论文献:数学评论Mathematics Review05C

  • 数学评论从第1到56卷(1940-1978年)有关图论论文的评论被收集在 Reviews in Graph Theory (W.G.Brown, 1980)中,共7卷。

 两本有关的手册:

  • Handbook of combinatorics. Vol. 1, 2. Edited by R. L. Graham, M. Grötschel and L. Lovász. Elsevier Science B.V., Amsterdam; MIT Press, Cambridge, MA, 1995. (这是一本由时任美国数学会(AMS) 主席 Graham国际数学联盟主席 Lovász 秘书长 Grötschel 三人合编的,约请53位专家分五个方面44个专题的综述组成的20世纪组合学百科全书)

  • Handbook of graph theory. Edited by Jonathan L. Gross and Jay Yellen. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2004. 

1. 内容是1.1节和1.2节。图的基本概念、介绍基本记号、图的同构和某些特殊的图类,如完全图、竞赛图和二部图。强调图是一个特殊的代数结构(有限集和定义在该集上的二元关系),几何图形只是它的一种直观表示。因此,图同构的概念是自然的。介绍有向图与二部图的关系。作为2部图,介绍超立方体;作为另一个例子,计算 k 部图的最大边数。重点是图的定义和它的几何图形表示,图的同构和一些特殊的图类。习题:1.1.1, 1.2.4 1.2.51.2.6 (中文第三版:1.1.11.2.3 1.2.61.27.)。

2. 内容是1.3节和1.4节。介绍图的顶点度概念和图的基本运算和记号,笛卡尔乘积和线图运算。重点掌握图论第一定理(边数和顶点度之间的基本关系)和它的证明。通过若干例子,掌握证明和分析方法。习题:1.3.5, 1.3.6  (中文第二、第三版:1.3.4, 1.3.5 )

  • 关于线图和笛卡儿乘积图的进一步性质可参阅: Junming Xu,Toplogical Structure and Analysis of  Interconnection Networks ( Kluwer Academic Publisheres, 2001) 中的 Section 2.1 and Section 2.3 或者《组合网络理论》  (科学出版社,北京,2007) 中的第2章和第4章。

  • 有一篇关于线图研究的综述文献: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理论的专题著作可以参阅:

  • R.L. Graham, B.L. Rothschild, and J.H. Spencer, Ramsey Theory. John Wiley & Sons, 1980;第二版, 1991.

  • 李乔, 拉姆塞理论, 湖南教育出版社, 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 (中文第二版:1.5.4, 1.5.6, 1.57,1.5.10; 中文第三版:1.4.5,1.4.7,1.4.8,另外两个习题已经在正文中证明了)。

  • 图的连通性概念是图论中最基本的概念之一,第四章做进一步研究。

  • 一般图论教科书对图的直径叙述的比较少,但有大量的结论、问题和应用,有兴趣的读者可参阅以下综述。

  • Bermond, J. C., and Bollobas, B., The diameter of graphs -- a survey. Congresses Numerantium, 32 (1981), 3-27.

  • Bermond, J. C., Bond, J., Paoli, M., and Peyrat, C., Graphs and interconnection networks: diameter and vulnerability. London Mathematical Society Lecture Note Series, 82 (1983), 1-30.

  • Chung, F. R. K., Diameters of communication networks. Proceeding of Symposia in Applied Mathematics. Amer. Math. Soc., Providence, RI, 1986, 34 (1986), 1-22.

  • Chung, F. R. K., Diameters of graphs: old problems and new results. Congressus Numerantium, 68 (1987), 295-317. 

  • 有关Moore 图及其相关问题的最新综述文章:M. Miller, J. Siran, Moore graphs and beyond: A survey of the degree/diameter problem. the electronic journal of combinatorics (2005), #DS14.

  •  有关Moore 图及其相关问题的研究进展见网页:http://www-mat.upc.es/grup_de_grafs/table_g.html/ 

4. 内容是1.7。回和圈的概念、区别和基本图论结果。理解和掌握竞赛图点泛圈性结果 (定理1.5)。作为回或者圈的应用,介绍二部分图的判定准则(定理1.6)和若干例子。习题:1.7.4, 1.7.6 1.7.7 (中文第二版:1.6.41.6.1(e)1.6.5第三版:1.5.41.5.1,1.5.6

  • 关于路和圈中的研究问题和进展可参阅一篇综述文献: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.

  • 例题1.7.2涉及图论中一类著名的极值图问题--(k,g)-cages 问题,即阶数达到下界的k正则g围长的图(见习题1.7.10)

  • 关于(k,g)-cages 问题的早期研究结果可参见综述文章:Par-Ken Wong, Cages - a survey. Journal of Graph Theory, 11(1) (1982), 1-22.

  • 关于(k,g)-cages 问题的到目前为止的研究结果可参见综述文章:G. Exoo and R. Jajcay, Dynamic cage survey. Electron. J. Combin., 18 (2011), DS16

  • 本节还提到点泛圈(vertex-pancycle)概念,在网络分析中有重要应用。可参见一篇综述文章:Jun-Ming Xu and Mei-Jie Ma, A survey on cycle and path embedding in some networks. Frntiers of Mathematics in China, 4 (2) (2009), 217-252

  • 1978年, Caccetta 和Häggkvist提出如下至今仍未解决的猜想: 最小出度不小于r的n阶有向图含有长度不大于[n/r]的有向圈。关于这个猜想及其相关问题的研究进展, 可以参阅综述文献:B.Sullivan, A summary of results and problems related to the Caccetta-Häggkvist Conjecture. 2006-Arxiv.org.

5.内容是1.8节和1.9节。Euler图和Hamilton图的概念。重点掌握Euler图的判定准则(定理1.7)和Hamilton图的充分条件(定理1.9)及其推论。定理1.10的证明可以暂时不读,但推论必须了解。掌握图的Euler性和Hamilton性区别,线图建立了它们之间的联系。掌握和学会运用定理1.9的证明技巧。作为例子,介绍De Bruijn图和Kautz图。习题:1.8.21.8.31.9.3 1.9.7(中文第二版:1.7.2; 1.7.3; 1.8.3; 1.8.7;第三版:1.6.3; 1.6.4; 1.7.3; 1.7.9)。

  • 有一篇关于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

  • 有一本关于Euler问题的专著:Herbert Fleischner, Eulerian Graphs and Related Topics. Annals of Discrete Mathematics, Vol.50, Elsvier, 1990. 中译本:欧拉图与相关专题(孙志人等译),科学出版社,2012.

  • 有三篇关于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.  

  • R.J.Gould, Advance on the hamiltonian problem - a survey. Graphs and Combinatorics, 19 (2003), 7-52.

6.内容是1.10节。介绍图的另一种表示-图的邻接矩阵和关联矩阵(统称为代数表示)。弄清同构图的邻接矩阵的置换相似性和关联矩阵的置换相抵性。利用这种表示,可以借助代数方法来研究图的结构性质,有此产生代数图论。重点掌握定理1.11,这个定理揭示了图的几何表示与代数表示之间的紧密联系。通过若干例子,介绍代数方法在图论中的应用。习题:1.10.4 1.10.5; 选作1.10.6(中文第二版:1.9.4; 1.9.5; 1.9.6;第三版:1.9.4; 1.9.7; 1.9.8)。

  • 建议参阅的两本代数图论教材、二本关于图的譜的专题著作(系资料室有原版)和一篇早期结果的综述文章: 

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

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

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

  • Fan R.K. Chung, Spectral Graph Theory, AMS, 1997.

  • Russell Merris, Laplacian matrices of graphs: a survey. Linear Algebra and its Applications, Volumes 197-198, January-February 1994, Pages 143-176.

  • 有关Moore 图及其相关问题的最新综述文章:M. Miller, J. Siran, Moore graphs and beyond: A survey of the degree/diameter problem. the electronic journal of combinatorics (2005), #DS14.

  •  有关Moore 图及其相关问题的研究进展见网页:http://www-mat.upc.es/grup_de_grafs/table_g.html/ 

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

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

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

  • 柳柏濂, 组合矩阵论(第二版),科学出版社,2005.

  • Liu, Bolian and Lai, Hong-Jian, Matrices in Combinatorics and Graph Theory. Kluwer Academic Publishers,Dordrecht/Boston/London, 2000.

8.习题课。

9.内容是2.1节,它是本章的基础。介绍树(林)和支持树(林)的基本性质。弄清余树(林)、割边集和键的概念,圈、键与余树(林)的关系。习题:2.1.2, 2.1.3 2.1.4(中文第二版、第三版:2.1.2; 2.1.3.)。

  • 与支撑树有关的研究可参见一篇综述文章:K. Ozeki and T. Yamashita, Spanning tree: a survey.  Graphs and Combinatorics, 27 (1) (2011), 1-26. 

  • 树与余树, 边割集与圈集, 以及割空间与圈空间之间的这种对偶联系导出了新的数学理论-拟阵论(matroid theory).欲做进一步了解的读者可参阅 D. J. A. Walsh(1967), J. G.Oxley(1992)的《Matroid Theory》,刘桂真和陈庆华的《拟阵》(1994)和 赖虹建的《拟阵论》(2003).

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

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

  • 图的计数理论可参见:F.Harary E.M. Palmer, Graphical Enumeration. New York: Academic Press, 1973.

  • 不同构支撑树的计数可参见Polya计数定理(一般组合学教材中都有这个定理)。

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

13.重点介绍平面图和平图的基本概念和性质,Euler公式,Kuratowski 定理(3.6)和平图的几何对偶概念。习题:3.1.4, 3.1.6 3.1.7(中文第二、三版标号相同)。

  • 有关 Kuratowski 定理,参阅:Carsten Thomassen, Kuratowski's theorem. Journal of Graph Theory, 5 (3)(1981), 225-241.

  • 有关Kuratowski 定理的各种变形,可以参阅一篇综述文献:D.Archdeacon, Variations on a theme of Kuratowski. Discrete Mathematics, 302(2005), 22–31 (Kuratowski.pdf)

  • 有许多学者也得到Kuratowski 定理中的结论,有关这个定理的历史讨论,可参见:J.W.Kennedy, L.V, Quintas, and M.M.Syslo,The theorem on planar graphs. Historia Mathematicica, 12 (2) (1985), 356-368.

  • 习题中提到厚度(thichness)概念,这是一个重要的图论参数。它的研究结果和进展参见综述文章:P. Mutzell, T. Odental, and M. Scharbrodt, The thickness of graphs: a survey. Graphs and Combinatorics, 14 (1)(1998), 59-73 .

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

  • 非平面图和图的曲面嵌入是拓扑图论研究的重要内容之一。有兴趣的读者可参阅刘彦佩的专著:

  • 刘彦佩:图的可嵌入性理论,科学出版社,1995,第二版 (2010)。

  • 刘彦佩:Topological Theory on Graphs, 中国科大出版社, 2008

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(中文第二版:4.1.2; 4.1.5; 4.2.2; 4.2.3;第三版:4.1.2; 4.1.5; 4.2.3; 4.2.4; 4.2.5)。

  • 有关网络流的原始著作见:L. R. Jr. Ford and D. R. Fulkerson, Flows in Networks. Princeton University Press, Princeton, 1962.

  • 有关Menger定理的发现参见: K. Menger, On the origin of the n-arc theorem. J. Graph Theory, 5 (1981), 341-350.

  • 有关网络流与 Menger 定理有关的问题,有两篇文献可以参考:

  • András Frank, Connectivity and network flows. Handbook of combinatorics, Vol. 1, 1995, pp. 111--177.

  • O.R.Oellermann, Menger's Theorem. In Topics in Structural Graph Theory (edited by L.W. Beineke and R.Wilson) Cambridge University Press, 2010.

16.内容是4.3节。图的整体连通度概念,重点掌握Whitney不等式(定理4.4)和Whitney关于k连通图的判定准则(定理4.5)。通过定理和具体例子的证明,介绍有关连通度命题证明的基本方法。习题:4.3.3, 4.3.104.3.11 4.3.12 (中文第二版:同英文版; 中文第三版:4.3.3; 4.3.11, 4.3.12; 4.3.16)

  • 有关连通度的研究结果和进展有几篇篇综述文章可以参考:

  • Mader, W., Connectivity and edge-connectivity in finite graphs. In  Surveys in Combinatorics, London Mathematical Society Lecture Note Series, 38 (1979), 66-95.

  • O.R.Oellermann, Connectivity and edge-connectivity in graphs: A survey.  Congressus Numernatium 115/116 (1996), 231-252.
  • Hellwig, A., and Volkmann. L., Maximally edge-connected and vertex-connected graphs and digraphs-A survey. Discrete Mathematics, 308 (15) (2008), 3265-3296.

  • 有关Menger 定理在计算机互连网络中的应用,见:徐俊明,组合网络理论。北京:科学出版社,2007.

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

  • 有关网络流,有一本经典著作: Ford L R Jr, Fulkerson D R. Flows in Networks. Princeton: Princeton University Press, 1962

  • 有关网络流理论和算法,可参阅:R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows - Theory,
    Algorithms, and Applications, Englewood Cliffs NJ: Prentice Hall,1993.

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

  • 有关中国投递员问题有两篇综述文章可以参考:

  • 管梅谷. 中国投递员问题综述. 数学研究与评论, 4 (1) (1984), 113-119.

  • R. Gary Parker, Chinese postman problems, Handbook of graph theory, 2004, pp.237-252.

  • 有关方化矩形问题的历史和研究进展可参见:Federico, P. J., Squaring rectangles and squares. Graph Theory and Related Topics}, Proceedings of the Conference held in honour of Professor W. T. Tuttle on the occasion of his sixieth birthday (edited by J. A. Bondy and U. S. R. Murty), Academic Press, New York, 1979, 173-196.

19. 习题课。

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

  • 有关匹配理论,进一步的学习可参阅专著:Lovasz L, Plummer M D. Matching Theory.Annals of Discrete Math. 1986, 29.

  • 建立在Tutte定理基础上的图的分解理论有许多综述文章,最新的一篇:M. D. Plummer, Graph factors and factorization: 19852003: A survey. Discrete Mathematics 307 (2007), 791- 821.

21.内容是5.1节(下)和5.2.节。介绍点覆盖和König 定理(5.3)以及相关定理的等价性。介绍图的独立集和独立数的概念,了解计算独立数的困难性。介绍独立数与连通度及图的Hamilton性之间的关系。习题:5.2.5, 5.2.6 5.2.7(中文第二、三版:5.1.9; 5.2.6; 5.2.7)。

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

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

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

  • 货郎担问题是NPC 问题中的杰出代表, 对NPC理论欲作进一步了解的读者 可参阅:

  • M.R.Garey and D.S.Jonson, Computers and Intractability, A guide to the theory of NP-compleness. Freeman, 1979 (中译本: 加里 M. R, 约翰逊 D. S 著, 张立昂等译,计算机和难解性--NP完全性理论导引. 北京: 科学出版社, 1987

  • 关于货郎担问题的研究与进展已有大量的文献, 有兴趣的读者可参阅专著:

  • E.L.Lawler, J.K.Lenstra, Kan A.H.G, Rinnooy and D.B.Shmoys, The Traveling Salesman Problem. New York: Wiley Interscience, 1986

  • D.L. Applegate, R.E. Bixby V. Chvatal and W.J. Cook, The Traveling Salesman Problem: A Computational Study.
    Princeton University Press, 2007
    .

  • Vašek Chvátal's: traveling salesman problem page

25. 内容是6.1。介绍点染色的基本概念和结果,弄清点染色与独立集之间的关系。重点掌握定理6.1、6.2和6.3。作为应用,列举若干例子。习题:6.1.4 6.1.5(中文第二版、第三版:6.1.5; 6.1.6)。

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

  • 关于图的染色,可以参考的最近专著:T.R.Jensen and B.Toft, Graph Coloring Problems. New York: Wiley,1995.

  • 关于四色猜想的计算机证明最新版本见:K.Appel and W. Haken, Every planar map is four colorable. With the collaboration of J. Koch. Contemporary Mathematics, 98 (1989), 1-741.

  • 四色猜想的计算机证明简化版本见:N.Robertson, D.Sanders, P.Seymour and R.Thomas, The four-color theorem. J. Combinatorial Theory, B, 70 (1997), 2-44. 可参见网页: http://people.math.gatech.edu/~thomas/FC/fourcolor.html 

  • 相关的染色问题见:B.Toft, 75 graph-colouring problems. Graph Colourings (edited by R. Nelson & R. J. Wilson),  Pitman Research Notes in Mathematics Series, Vol. 218, 1990, 9-35.

  • 四色问题与整数流密切相关,参见:C.-Q. Zhang (张存铨), Integer flows and cycle covers of graphs. New York: Marcel Dekker, 1997.

27.期终总结,布置期终复习和考试事宜。

28. 习题课。

29.期末考试(闭卷)。时间:2013-01-08上午7:35 -- 9:35;地点:5202教室。

习题提示: graph-ex.pdf 
返回到 Courses