离散数学 (图论部分)

《离散数学 (图论部分)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学(图论部分)主要内容平面图的概念Euler公式极大平面图图的可平面性对偶图的着色色数多项式独立集和支配集匹配理论网流理论图的概念点和边的关联关系道路与回路树的概念关联矩阵生成树（支撑树）二叉树Huffman树最优路径关键路径1.1图论的产生和发展1.Konisberge桥问题[问题]能否从某一块陆地出发，走遍每一座桥，且每一座桥只能走一次，最后回到出发点。2.四色猜想在任何平面或球面上的地图，只用四种颜色涂色，就可使得相邻区域涂上不同颜色。1976年，Appel,Haken和Koch利用计算机辅助证明了四色猜想，但其数学证明仍不理想。

2、1.1图论的产生和发展3.Hamilton回路1859年，Hamilton的周游世界游戏：由12个正五边形构成一个12面体，上面有20个顶点。[问题]能否从某一顶点出发，走遍每一个顶点一次且仅仅一次，最后回到出发点。1.1图论的产生和发展4.Ramsey问题任何六个人中，或有三个人互相认识，或有三个人互不认识，二者必居其一。更一般性的问题：若一群人中或有m个人互相认识，或有n个人互不认识，则这群人最少得有多少人？记为Ramsey(m,n)[例]Ramsey(3,3)=61.1图论的产生和发展5.路径问题两点之间有无道路可通？有多少条道路可通？

3、哪条路最短？1.1图论的产生和发展图论在计算机科学领域中有着重要地位操作系统进程演变状态图和目录树搜索。人工智能图搜索策略和知识的表示数据结构的二大类非线性结构：树和图数据库系统的实体-联系模型和文件组织自动机理论1.2图论的重要地位石纯一，数理逻辑与集合论，北京：清华大学出版社，2000戴一奇，图论与代数结构，北京：清华大学出版社，1995王树禾，图论，北京：科学出版社，2004李盘林等，离散数学，北京：高等教育出版社，1999BernardKolman,DiscreteMathematicalStructures(FifthEdition

4、)，北京：高等教育出版社（影印版），2005D.S.Malik,DiscreteMathematicalStructures–TheoryandApplications，北京：高等教育出版社（影印版），2005D.B.West,IntroductiontoGraphTheory(SecondEdition),北京：机械工业出版社（影印版），20041.3参考书目