《图论课件》由会员分享，可在线阅读，更多相关《图论课件（46页珍藏版）》请在金锄头文库上搜索。
1、图论及其应用 Graph Theory and Its Applications,主要内容,图论前言 数学预备知识,前言,课程目标 学时和学分 教学大纲 教材和主要参考资料 课程考核,图论学科简介 （1）,图论是研究点与线组成的“图形”问题的一门科学。图论是组合数学的一个分支，它交叉运用了拓扑学、群论、数论等学科，有时将其归为离散数学的一个分支 属于应用数学分支 哥尼斯堡七桥问题 欧拉（17071782）：根据几何位置的解题方法，这是图论领域的第一篇论文，1736年， 被尊称为图论和拓扑之父,七桥问题,近代图论的历史可追溯到18世纪的七桥问题:穿过Knigsberg城的七座桥，要求每座桥通过一
2、次且仅通过一次。,Euler1736年证明了不可能存在这样的路线。,四色问题,在日常生活中我们常常可以遇到组合数学的问题。比如一个著名的世界难题“四色猜想” ：一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。,四色问题,1852年，刚从伦敦大学毕业的Francis Guthrie提出了四色猜想。 1878年著名的英国数学家Cayley向数学界征求解答。 此后数学家 Heawood 花费了毕生的精力致力于四色研究，于1890年证明了五色定理（每个平面图都是5顶点可着色的）。 直到1976年6月，美国数学家 K. Appel与 W. Haken，在3台不
3、同的电子计算机上，用了1200小时，才终于完成了“四色猜想”的证明，从而使“四色猜想“成为了四色定理。,图论学科简介 （2）,19世纪末期，图论应用于电网络方程组和有机化学中的分子结构 20世纪中叶，由于计算机的发展，图论用来求解生产管理、军事、交通运输、计算机和网络通信等领域中的离散性问题 物理学、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学、管理科学等领域应用,课程目标,通过本课程学习，要求学生掌握图论的基本理论及推理方法，为通信网络、计算机、信息工程、密码学、运筹学、管理科学等等学科进一步学习和研究打下理论基础。 掌握图论的基本理论与基本方法，并用这些理论与方法解
4、决一些实际问题，了解图论在现代信息科学、现代通信系统、计算机科学、管理与工程等中的应用。本课程特别强调理论与工程实践相结合，以提高学生的学习知识、运用知识能力。,学时和学分,学时数 54 学分数 3,教学大纲 （共11章）,通过教学，使学生掌握该课程的基本理论与方法，培养对离散对象的抽象思维与解决实际问题的能力，并为学习相关课程及将来从事科学研究创新和工程实践奠定理论基础，及培养学生理论与实践相结合的能力。,第一章 图的基本概念,图和简单图 同构 子图 顶点的度 路和连通性 圈 最短路问题,第二章 树,树 割边和键 割点 连线问题,第三章 连通度,连通度 块 可靠通信网建设问题,第四章 Eul
5、er环游和Hamilton圈,Euler环游 Hamilton圈 旅行售货员问题,第五章 匹配,匹配 偶图的匹配和覆盖完美匹配 人员分派问题 最优匹配问题,第六章 着色问题,边色数 Vizing定理 点着色 色数 Brooks定理 围长和色数,第七章 平面图,平图和平面图 对偶图 Euler公式 Kuratowski定理 五色定理和四色猜想 平面性算法,第八章 有向图,有向图 有向路 有向圈,第九章 网络,流 割 最大流最小割定理 Menger定理,第十章 NP 完全问题,优化问题 P类和NP类 Cook定理 六个基本NPC问题,第十一章 图论的应用,图论在现代网络设计和流量分析中的应用图论在
6、信息安全中的应用 图论在信号处理中的应用,教材和主要参考资料 （1）,图论及其应用，孙惠泉，科学出版社，2004年9月。 图论导引，Douglas B.West 著，李建中、骆吉洲译，机械工业出版社，2006年2月。 图论及其应用习题解答，张克民、林国宁、张忠辅编，清华大学出版社，1988年4月。,教材和主要参考资料 （2）,图论及其应用，J.A. 邦迪 及 U.S.R 默蒂，科学出版社。 （原书：Graph Theory with Applications, J.A. Bondy & U.S.R. Murty) 有最新扩容版，2008年Springer出版的GTM丛书,GTM244 Grap
7、h Theory. Graph Theory, Reinhard Diestel，第四版,Springer，有中文版，李学良等译.,学习方法,目的明确 态度端正 理论和实践相结合 充分利用资源 逐步实现从知识到能力到素质的深化和升华,课程考核,平时成绩 （30%-40%） 闭卷考试 （60%-70%）,27,图论模型,为了抽象和简化现实世界，常建立数学模型。图是关系的数学表示，为了深刻理解事物之间的联系，图是常用的数学模型。,(1) 化学中的图论模型,19世纪，化学家凯莱用图论研究简单烃即碳氢化合物,用点抽象分子式中的碳原子和氢原子，用边抽象原子间 的化学键。,28,通过这样的建模，能很好研究
8、简单烃的同分异构现象.,例如：C4H10的两种同分异构结构图模型为：,29,(2) 商业中的图论模型,商业中，经常用图来对仓库和零售店进行建模,例如：令V=w1,w2,w3,r1,r2,r3,r4,r5代表3个仓库和5个零售点,E=w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5代表每个仓库和每个 零售店间的关联。则图模型图形为：,30,用点表示城市，两点连线当且仅当两城市有航线。为了 求出两城市间最短航线，需要在线的旁边注明距离值。,例如：令V=a, b, c, d, e代表5个城市,E=a b, ad, b c , be, de代表城市间的直达航线,则航线图
9、的图形为：,请求出从d到c的最短路,(3) 最短航线问题,31,(4) 任务分配问题,有一个旅行团要组织一批人去旅游，其中一些人是朋友 他们要乘坐公共汽车去，而车上的位子是成对的。因此 为了让大家旅途更愉快，旅行团负责人需要将成对的朋 友安排在一起。给出一种安排方案。,该问题可以建立一个图论模型来解决：旅行团的人抽象 为图的顶点，两个顶点连线，当且仅当两个顶点代表的 人是朋友。,问题归结于在模型图中求所谓的“匹配”，关于图的匹配 将在第五章介绍。,32,(5) 考试时间安排问题,一个教授需要对期末考试时间进行安排，使得学生们 不会有相互冲突的考试。如何解决？,该问题可以建立一个图论模型来解决：
10、待考的课程可 抽象为图的顶点，连接两个顶点的边表示至少有一个学生 同时选择了这两门课程。,问题归结于在模型图中求所谓的“顶点着色方案”问题， 该问题将在第六章讨论。,例如：有a, b, c ,d, e, f 六门课程。按照上面方法建立 的模型图如下：,33,一种可行的安排方案为：第一时间：a, d, e;第二时间： b, f ；最后：c.,另一种可行的安排方案为：第一时间：a, e;第二时间： c, d ；最后：b, f .,(6) 旅行售货员问题,一电脑代理商要从她所在城市出发，乘飞机去六个城市， 然后回到出发点，如果要求每个城市只经历一次，能否办 到？给出行走方案。,34,问题归结为在模型
11、图中寻求所谓的“哈密尔顿圈”问题。 将在第四章介绍。,例如：如果模型图如下：,该问题可以建立一个图论模型来解决：城市抽象为 图的顶点，边代表城市间的直达航线。,可行方案: (1) h, d, e, c, b, a, h (2) h, d, e, c, a, b, h,数学预备知识,集合论 数理逻辑 归纳法原理 组合分析与计数 鸽巢原理（鸽舍原理、抽屉原理） 等价关系与同余,集合论,自然数集、整数集、有理数集、实数集并集，交集，差集，补集，对称差集 集合的计数：card A=n 自然数集的计数： 实数集的计数：,数理逻辑 （1）,全称量词 存在量词 否定 合取 析取 条件命题 双条件命题,数理逻
12、辑 （2）,条件命题 逆命题逆否命题：,数理逻辑 （3）,双条件命题,引理、定理、推论,引理（lemma) : 希腊语意为前提 定理 (theorem):希腊语意为待证的论题 推论 (corollary): 拉丁语，意为赠品，是从定理或命题出发无需太多额外工作即可得出的论断,归纳法原理一,对每个自然数，设P(n)是一个数学命题。如果下面的性质a和b成立，则P(n)对每个自然数n均为真 a) P(1)为真； b) 对于 ，如果P(k)为真，则 P(k+1)为真；,归纳法原理二,对每个自然数，设P(n)是一个数学命题。如果下面的性质a和b成立，则P(n)对每个自然数n均为真 a) P(1)为真； b) 对于 ，如果对所有 P(t)为真，则 P(k+1)为真；,组合分析与计数,映射 双射幂集、子集的个数计数,鸽巢原理（鸽舍原理、抽屉原理）,平均值总是介于最大值和最小值之间 如果对象多于kn的一个集合被划分为n个类，则必有一个包含的对象多于k个,等价关系与同余 （1）,集合S上的一个等价关系是S上的一个关系R,它对不同元素 满足 a) 自反性 b) 对称性 c) 传递性,等价关系与同余 （2）,对于“模n同余”是等价关系，其等价类成为模n的余数类或者同余类，所有的同余类构成的集合,
