大学课件：图论及其应用.ppt

《大学课件：图论及其应用.ppt》由会员分享，可在线阅读，更多相关《大学课件：图论及其应用.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论及其应用Graph Theory and Its Applications,主要内容,图论前言 数学预备知识,前言,课程目标 学时和学分 教学大纲 教材和主要参考资料 课程考核,图论学科简介 （1）,哥尼斯堡七桥问题 欧拉（17071782）：根据几何位置的解题方法，这是图论领域的第一篇论文，1736年， 被尊称为图论和拓扑之父 图论是组合数学的一个分支，它交叉运用了拓扑学、群论、数论等学科，有时将其归为离散数学的一个分支,图论学科简介 （2）,19世纪末期，图论应用于电网络方程组和有机化学中的分子结构 20世纪中叶，由于计算机的发展，图论用来求解生产管理、军事、交通运输、计算机和网络通信

2、等领域中的离散性问题 物理学、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学、管理科学等领域应用,课程目标,通过本课程学习，要求学生掌握图论的基本理论及推理方法，为通信网络、电路辅助设计、信息工程、密码学等打下理论基础。 掌握图论的基本理论与基本方法，并用这些理论与方法解决一些实际问题，了解图论在现代信息科学和现代通信系统中的应用。本课程特别强调理论与工程实践相结合，以提高学生的学习知识、运用知识能力。,学时和学分,学时数 54 学分数 3,教学大纲 （共11章）,通过教学，使学生掌握该课程的基本理论与方法，培养对离散对象的抽象思维与解决实际问题的能力，并为学习相关课程及

3、将来从事科学研究创新和工程实践奠定理论基础，及培养学生理论与实践相结合的能力。,第一章 图的基本概念,图和简单图 同构 子图 顶点的度 路和连通性 圈 最短路问题,第二章 树,树 割边和键 割点 连线问题,第三章 连通度,连通度 块 可靠通信网建设问题,第四章 Euler环游和Hamilton圈,Euler环游 Hamilton圈 旅行售货员问题,第五章 匹配,匹配 偶图的匹配和覆盖 完美匹配 人员分派问题 最优匹配问题,第六章 着色问题,边色数 Vizing定理 点着色 色数 Brooks定理 围长和色数,第七章 平面图,平图和平面图 对偶图 Euler公式 Kuratowski定理 五色定

4、理和四色猜想 平面性算法,第八章 有向图,有向图 有向路 有向圈,第九章 网络,流 割 最大流最小割定理 Menger定理,第十章 NP 完全问题,优化问题 P类和NP类 Cook定理 六个基本NPC问题,第十一章 图论的应用,图论在现代网络设计和流量分析中的应用 图论在信息安全中的应用 图论在信号处理中的应用,教材和主要参考资料 （1）,图论及其应用，孙惠泉，科学出版社，2004年9月。 图论导引，Douglas B.West 著，李建中、骆吉洲译，机械工业出版社，2006年2月。 图论简明教程，Fred Buckley,Marty Lewinter 著，李慧霸、王凤芹译，清华大学出版社，2

5、005年1月。,教材和主要参考资料 （2）,图论及其应用，J.A. 邦迪 及 U.S.R 默蒂，科学出版社。 （原书：Graph Theory with Applications, J.A. Bondy & U.S.R. Murty) Introduction to Graph Theory, Second Edition , Douglas B. West. A Friendly Introduction to Graph Theory, Fred Buckley,Marty Lewinter.,学习方法,目的明确 态度端正 理论和实践相结合 充分利用资源 逐步实现从知识到能力到素质的深化和

6、升华,课程考核,平时成绩 （10%） 图论应用的小论文 （60%） 开卷考试 （30%）,几点建议,做人：厚德博学 敬业乐群 读书：博与精 薄与厚 创新：IPR (Intellectual Property Rights) 职业定位：CEO、CTO、CFO、 首席科学家、 董事长 技术管理？技术专家 理想与价值体现：修身、齐家、治国、 平天下 个人价值？社会价值 身心健康，全面发展：IQ、EQ、AQ,网上资源：标准,http:/www.itu.int/home/index.html http:/www.3gpp.org/ http:/www.3gpp2.org/ http:/www.etsi.

7、org/ http:/www.ieee.org/ http:/standards.ieee.org/wireless/ http:/ieee802.org/ http:/www.wi-fi.org/ http:/www.iso.org/,网上资源：文章、论文、图书,IEE,IEEE,IEICE http:/ieeexplore.ieee.org/ SCI,EI Village ,网上资源：专利, http:/www.wipo.int/ http:/www.european-patent-office.org/ http:/www.uspto.gov/ http:/www.jpo.go.jp/,

8、北京九章图书有限公司, 北京海淀西大街31号 海淀图书城 籍海楼二层 北京九章图书有限公司 邮编： 100080电话：（010） 62639894、62539135、62559881 （均可收传真）E-mail:,名人名言,智者，善假于物也 学贵有恒，人贵有志 贵我、通今：横尽虚空，山河大地无一可恃，可恃惟我；数尽来劫，前后左右无一可据，可据惟今！ 生当作人杰，死亦为鬼雄！,一副对联、一句勉励,上联： 做人做事做第一 下联： 创新创业创世界 横批： 众志成城 千里之行，始于足下， 兴趣是最好的老师，将兴趣升华为爱好，将爱好升华为技能，将技能升华为素质，将素质升华为成功。,数学预备知识,集合论

9、数理逻辑 归纳法原理 组合分析与计数 鸽巢原理（鸽舍原理、抽屉原理） 等价关系与同余,集合论,自然数集、整数集、有理数集、实数集 并集，交集，差集，补集，对称差集 集合的计数：card A=n 自然数集的计数： 实数集的计数：,数理逻辑 （1）,全称量词 存在量词 否定 合取 析取 条件命题 双条件命题,数理逻辑 （2）,条件命题 逆命题 逆否命题：,数理逻辑 （3）,双条件命题,引理、定理、推论,引理（lemma) : 希腊语意为前提 定理 (theorem):希腊语意为待证的论题 推论 (corollary): 拉丁语，意为赠品，是从定理或命题出发无需太多额外工作即可得出的论断,归纳法原理

10、一,对每个自然数，设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的余数类或者同余类，所有的同余类构成的集合,Next week,第一章 图的基本概念,