图论及其应用.ppt

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

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

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

3、与方法，培养对离散对象的抽象思维与解决实际问题的能力，并为学习相关课程及将来从事科学研究创新和工程实践奠定理论基础，及培养学生理论与实践相结合的能力。现在学习的是第8页，共43页第一章 图的基本概念 图和简单图 同构 子图 顶点的度路和连通性 圈 最短路问题现在学习的是第9页，共43页第二章 树树 割边和键 割点 连线问题现在学习的是第10页，共43页第三章 连通度 连通度 块 可靠通信网建设问题 现在学习的是第11页，共43页第四章 Euler环游和Hamilton圈 Euler环游 Hamilton圈 旅行售货员问题 现在学习的是第12页，共43页第五章 匹配 匹配 偶图的匹配和覆盖 完美

4、匹配人员分派问题 最优匹配问题现在学习的是第13页，共43页 第六章 着色问题 边色数 Vizing定理 点着色色数 Brooks定理 围长和色数 现在学习的是第14页，共43页第七章 平面图平图和平面图 对偶图 Euler公式Kuratowski定理 五色定理和四色猜想平面性算法现在学习的是第15页，共43页第八章 有向图有向图 有向路 有向圈现在学习的是第16页，共43页第九章 网络 流 割 最大流最小割定理 Menger定理 现在学习的是第17页，共43页第十章 NP 完全问题 优化问题 P类和NP类 Cook定理 六个基本NPC问题 现在学习的是第18页，共43页第十一章 图论的应用图

5、论在现代网络设计和流量分析中的应用 图论在信息安全中的应用 图论在信号处理中的应用现在学习的是第19页，共43页教材和主要参考资料（1）图论及其应用，孙惠泉，科学出版社，2004年9月。图论导引，Douglas B.West 著，李建中、骆吉洲译，机械工业出版社，2006年2月。图论简明教程，Fred Buckley,Marty Lewinter 著，李慧霸、王凤芹译，清华大学出版社，2005年1月。现在学习的是第20页，共43页教材和主要参考资料（2）图论及其应用，J.A.邦迪 及 U.S.R 默蒂，科学出版社。（原书：Graph Theory with Applications,J.A.B

6、ondy&U.S.R.Murty)Introduction to Graph Theory,Second Edition,Douglas B.West.A Friendly Introduction to Graph Theory,Fred Buckley,Marty Lewinter.现在学习的是第21页，共43页学习方法目的明确态度端正理论和实践相结合充分利用资源逐步实现从知识到能力到素质的深化和升华现在学习的是第22页，共43页课程考核平时成绩 （10%）图论应用的小论文（60%）开卷考试 （30%）现在学习的是第23页，共43页几点建议做人：厚德博学 敬业乐群读书：博与精 薄与厚创新：

7、IPR(Intellectual Property Rights)职业定位：CEO、CTO、CFO、首席科学家、董事长 技术管理？技术专家理想与价值体现：修身、齐家、治国、平天下 个人价值？社会价值身心健康，全面发展：IQ、EQ、AQ现在学习的是第24页，共43页网上资源：标准http:/www.itu.int/home/index.html http:/ http:/ieeexplore.ieee.org/SCI,EI Village http:/ 海淀图书城 籍海楼二层 北京九章图书有限公司邮编：100080电话：（010）62639894、62539135、62559881（均可收传真）

8、E-mail:现在学习的是第28页，共43页名人名言智者，善假于物也学贵有恒，人贵有志贵我、通今：横尽虚空，山河大地无一可恃，可恃惟我；数尽来劫，前后左右无一可据，可据惟今！生当作人杰，死亦为鬼雄！现在学习的是第29页，共43页一副对联、一句勉励 上联：做人做事做第一 下联：创新创业创世界 横批：众志成城千里之行，始于足下，兴趣是最好的老师，将兴趣升华为爱好，将爱好升华为技能，将技能升华为素质，将素质升华为成功。现在学习的是第30页，共43页数学预备知识集合论数理逻辑归纳法原理组合分析与计数鸽巢原理（鸽舍原理、抽屉原理）等价关系与同余现在学习的是第31页，共43页集合论自然数集、整数集、有理数

9、集、实数集并集，交集，差集，补集，对称差集集合的计数：card A=n 自然数集的计数：实数集的计数：NZQRA0现在学习的是第32页，共43页数理逻辑（1）全称量词 存在量词否定合取析取条件命题双条件命题()()xS P x()()xS P x 现在学习的是第33页，共43页数理逻辑（2）条件命题 逆命题逆否命题：PQQPQP()PQ现在学习的是第34页，共43页数理逻辑（3）双条件命题()()PQQP现在学习的是第35页，共43页引理、定理、推论引理（lemma):希腊语意为前提定理(theorem):希腊语意为待证的论题推论(corollary):拉丁语，意为赠品，是从定理或命题出发无需

10、太多额外工作即可得出的论断现在学习的是第36页，共43页归纳法原理一对每个自然数，设P(n)是一个数学命题。如果下面的性质a和b成立，则P(n)对每个自然数n均为真a)P(1)为真；b)对于 ，如果P(k)为真，则 P(k+1)为真；kN现在学习的是第37页，共43页归纳法原理二对每个自然数，设P(n)是一个数学命题。如果下面的性质a和b成立，则P(n)对每个自然数n均为真a)P(1)为真；b)对于 ，如果对所有 P(t)为真，则 P(k+1)为真；tk现在学习的是第38页，共43页组合分析与计数映射双射幂集、子集的个数计数x x 现在学习的是第39页，共43页鸽巢原理（鸽舍原理、抽屉原理）平

11、均值总是介于最大值和最小值之间如果对象多于kn的一个集合被划分为n个类，则必有一个包含的对象多于k个现在学习的是第40页，共43页等价关系与同余 （1）集合S上的一个等价关系是S上的一个关系R,它对不同元素 满足a)自反性 b)对称性 c)传递性,x y zS(,)x xR(,)(,)x yRy xR(,)(,)(,)x yRy zRx zR且现在学习的是第41页，共43页等价关系与同余 （2）对于“模n同余”是等价关系，其等价类成为模n的余数类或者同余类，所有的同余类构成的集合 modxynn/n现在学习的是第42页，共43页Next week第一章 图的基本概念现在学习的是第43页，共43页