图论及其应用（课堂PPT）

图论及其应用GraphTheoryandItsApplications,1,主要内容,图论前言数学预备知识,2,前言,课程目标学时和学分教学大纲教材和主要参考资料课程考核,3,图论学科简介（1）,哥尼斯堡七桥问题欧拉（17071782）：根据几何位置的解题方法，这是图论领域的第一篇论文，1736年，被尊称为图论和拓扑之父图论是组合数学的一个分支，它交叉运用了拓扑学、群论、数论等学科，有时将其归为离散数学的一个分支,4,图论学科简介（2）,19世纪末期，图论应用于电网络方程组和有机化学中的分子结构20世纪中叶，由于计算机的发展，图论用来求解生产管理、军事、交通运输、计算机和网络通信等领域中的离散性问题物理学、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学、管理科学等领域应用,5,课程目标,通过本课程学习，要求学生掌握图论的基本理论及推理方法，为通信网络、电路辅助设计、信息工程、密码学等打下理论基础。掌握图论的基本理论与基本方法，并用这些理论与方法解决一些实际问题，了解图论在现代信息科学和现代通信系统中的应用。本课程特别强调理论与工程实践相结合，以提高学生的学习知识、运用知识能力。,6,学时和学分,学时数54学分数3,7,教学大纲（共11章）,通过教学，使学生掌握该课程的基本理论与方法，培养对离散对象的抽象思维与解决实际问题的能力，并为学习相关课程及将来从事科学研究创新和工程实践奠定理论基础，及培养学生理论与实践相结合的能力。,8,第一章图的基本概念,图和简单图同构子图顶点的度路和连通性圈最短路问题,9,第二章树,树割边和键割点连线问题,10,第三章连通度,连通度块可靠通信网建设问题,11,第四章Euler环游和Hamilton圈,Euler环游Hamilton圈旅行售货员问题,12,第五章匹配,匹配偶图的匹配和覆盖完美匹配人员分派问题最优匹配问题,13,第六章着色问题,边色数Vizing定理点着色色数Brooks定理围长和色数,14,第七章平面图,平图和平面图对偶图Euler公式Kuratowski定理五色定理和四色猜想平面性算法,15,第八章有向图,有向图有向路有向圈,16,第九章网络,流割最大流最小割定理Menger定理,17,第十章NP完全问题,优化问题P类和NP类Cook定理六个基本NPC问题,18,第十一章图论的应用,图论在现代网络设计和流量分析中的应用图论在信息安全中的应用图论在信号处理中的应用,19,教材和主要参考资料（1）,图论及其应用，孙惠泉，科学出版社，2004年9月。图论导引，DouglasB.West著，李建中、骆吉洲译，机械工业出版社，2006年2月。图论简明教程，FredBuckley,MartyLewinter著，李慧霸、王凤芹译，清华大学出版社，2005年1月。,20,教材和主要参考资料（2）,图论及其应用，J.A.邦迪及U.S.R默蒂，科学出版社。（原书：GraphTheorywithApplications,J.A.Bondy&U.S.R.Murty)IntroductiontoGraphTheory,SecondEdition,DouglasB.West.AFriendlyIntroductiontoGraphTheory,FredBuckley,MartyLewinter.,21,学习方法,目的明确态度端正理论和实践相结合充分利用资源逐步实现从知识到能力到素质的深化和升华,22,课程考核,平时成绩（10%）图论应用的小论文（60%）开卷考试（30%）,23,几点建议,做人：厚德博学敬业乐群读书：博与精薄与厚创新：IPR(IntellectualPropertyRights)职业定位：CEO、CTO、CFO、首席科学家、董事长技术管理？技术专家理想与价值体现：修身、齐家、治国、平天下个人价值？社会价值身心健康，全面发展：IQ、EQ、AQ,24,网上资源：标准,/home/index.html,25,网上资源：文章、论文、图书,IEE,IEEE,IEICE/SCI,EIVillage,26,网上资源：专利,27,北京九章图书有限公司,电话：（010）62639894、62539135、62559881（均可收传真）E-mail:chaoh,28,名人名言,智者，善假于物也学贵有恒，人贵有志贵我、通今：横尽虚空，山河大地无一可恃，可恃惟我；数尽来劫，前后左右无一可据，可据惟今！生当作人杰，死亦为鬼雄！,29,一副对联、一句勉励,上联：做人做事做第一下联：创新创业创世界横批：众志成城千里之行，始于足下，兴趣是最好的老师，将兴趣升华为爱好，将爱好升华为技能，将技能升华为素质，将素质升华为成功。,30,数学预备知识,集合论数理逻辑归纳法原理组合分析与计数鸽巢原理（鸽舍原理、抽屉原理）等价关系与同余,31,集合论,自然数集、整数集、有理数集、实数集并集，交集，差集，补集，对称差集集合的计数：cardA=n自然数集的计数：实数集的计数：,32,数理逻辑（1）,全称量词存在量词否定合取析取条件命题双条件命题,33,数理逻辑（2）,条件命题逆命题逆否命题：,34,数理逻辑（3）,双条件命题,35,引理、定理、推论,引理（lemma):希腊语意为前提定理(theorem):希腊语意为待证的论题推论(corollary):拉丁语，意为赠品，是从定理或命题出发无需太多额外工作即可得出的论断,36,归纳法原理一,对每个自然数，设P(n)是一个数学命题。如果下面的性质a和b成立，则P(n)对每个自然数n均为真a)P(1)为真；b)对于，如果P(k)为真，则P(k+1)为真；,37,归纳法原理二,对每个自然数，设P(n)是一个数学命题。如果下面的性质a和b成立，则P(n)对每个自然数n均为真a)P(1)为真；b)对于，如果对所有P(t)为真，则P(k+1)为真；,38,组合分析与计数,映射双射幂集、子集的个数计数,39,鸽巢原理（鸽舍原理、抽屉原理）,平均值总是介于最大值和最小值之间如果对象多于kn的一个集合被划分为n个类，则必有一个包含的对象多于k个,40,等价关