数学实验之图的模型及算法初步课件.ppt
数学实验之图的模型及算法初步第1页，此课件共44页哦 1 1学会如何建立图的模型；22了解图的存储结构；33掌握图的表示与矩阵表示 之间的转化；44初步认识算法及其复杂性,树立算法有效性的观点。实验目的2022-9-6第2页，此课件共44页哦实验十主要内容实验十主要内容第3页，此课件共44页哦图论的起源：七桥问题图论的起源：七桥问题2022-9-6第4页，此课件共44页哦 c a b d c a b d 图论的起源：七桥问题图论的起源：七桥问题2022-9-6第5页，此课件共44页哦欧拉图论之父 定义：线图（图论的研究对象）定理：一个线图存在通过每边正好一次回到出发点的路线的充要条件是：1）图要是连通连通的2）与图中每一顶点相连的边必须是偶数偶数条。于是得出结论：七桥问题无解。图论的起源：七桥问题图论的起源：七桥问题2022-9-6第6页，此课件共44页哦无向图，一般用大写字母G,H表示。一种表示工具一种表示工具图图顶点顶点边边 d c a b 2022-9-6第7页，此课件共44页哦 无向图：G=(V,E)，顶点集：V；边集：E。e与顶点u,v相关联。u与v相邻。两边相邻。重边 c a b d 一种表示工具一种表示工具图图2022-9-6第8页，此课件共44页哦两种特殊图：简单图 完全图，记为Knb d c a b d c a 一种表示工具一种表示工具图图2022-9-6第9页，此课件共44页哦有向图：V1V2V3V5V4你能给出一个可用有向图描述的实际例子吗？一种表示工具一种表示工具图图2022-9-6第10页，此课件共44页哦网络网络这些数字可以代表距离距离，费用费用，可靠可靠性性或其他的相关参数。12345869157103一种表示工具一种表示工具图图2022-9-6第11页，此课件共44页哦(G)和(G)分别表示图G的顶点数和边数在无向图中，v的度数，记为d(v)；在有向图中，v的出度，记为d+(v);v的入度，记为d-(v)。一种表示工具一种表示工具图图2022-9-6第12页，此课件共44页哦一个时间安排问题一个时间安排问题 学校要为一年级的研究生开设六门基础数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。2022-9-6第13页，此课件共44页哦 S N G M R P李春兰郑文国姚南陈奇峰王润惠邹文燕万华李祖军黄大度史武军刘昆欧阳金郭志伟陈奇峰刘云刘元元黄大度董舟邹鑫赵云王凯李白彤甄军李欣陈俊于洪化范文李出荣张惠赵云曹林军胡志强张敏陈修建欧阳金李晓李白彤万华曾光伟张星夏雯邵桂芳王学权单富民董舟杨欣吴军查小辉王坚程静波邹文燕卫迎新赵小民息志强陈修建邹鑫刘元兵杨成宝邱吉洲许茂陈俊周清武樊雪峰刘伟甄军姜永东一个时间安排问题一个时间安排问题2022-9-6第14页，此课件共44页哦SNGRPM完成上述表示课程冲突关系的线图直观、清晰地表达已知信息的方式一个时间安排问题一个时间安排问题2022-9-6第15页，此课件共44页哦人狼羊菜渡河问题人狼羊菜渡河问题摆渡人F狼W羊G菜C2022-9-6第16页，此课件共44页哦 南岸状态：16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，FWGCFWGFWCFGCFGOCGWWC10个允许状态：人狼羊菜渡河问题人狼羊菜渡河问题2022-9-6第17页，此课件共44页哦FWGCFWG FWCFGCFGOCGWWC寻求图中从顶点“FWGC”到顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。语言描述时未显示的关系跃然纸上人狼羊菜渡河问题人狼羊菜渡河问题2022-9-6第18页，此课件共44页哦FWGCFWG FWCFGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC人狼羊菜渡河问题人狼羊菜渡河问题2022-9-6第19页，此课件共44页哦图的矩阵表示方法图的矩阵表示方法邻接矩阵关联矩阵边矩阵邻接顺序表2022-9-6第20页，此课件共44页哦v1v2v5v6v7v4v3abjkcghidfe010100010111100100010110010101010100110101000101076543217654321邻接矩阵2022-9-6第21页，此课件共44页哦 无向图的邻接矩阵：A=(aij)nn，其中不相邻与当，相邻与当jijiijvv0vv1a无向图的邻接矩阵有何特点？由邻接矩阵是否能作出原图？邻接矩阵2022-9-6第22页，此课件共44页哦001010000000011011100000010000100100011000101100001000001000001101000000000117654321kjihgfedcba关联矩阵v1v2v5v6v7v4v3abjkcghidfe2022-9-6第23页，此课件共44页哦 无向图的关联矩阵：M=(mij)nm,其中 不相关联与若相关联，与若jijiijev0ev1m无向图的关联矩阵有哪些特征？由关联矩阵能否作出原图？关联矩阵2022-9-6第24页，此课件共44页哦4376766654232654432211Ekjihgfedcba边矩阵v1v2v5v6v7v4v3abjkcghidfe2022-9-6第25页，此课件共44页哦好算法还是坏算法好算法还是坏算法算法无效算法的时间复杂性分析什么是算法时间复杂度量级比较有效算法2022-9-6第26页，此课件共44页哦 一个算法就是解决某一特定问题的方法，是一系列确定步骤，它必须在有限的时间内终止。表述一个算法一般有两种方式（1）步骤描述；（2）框图。什么是算法2022-9-6第27页，此课件共44页哦例：求两个正整数m和n的最大公因子的Euclid算法什么是算法2022-9-6第28页，此课件共44页哦 用行列式的定义求一个20阶行列式的值，即使是每秒1000万次的计算机也要花大约15万年的时间。算法无效2022-9-6第29页，此课件共44页哦好算法还是坏算法好算法还是坏算法 如何才能简便地判断一个算法的有效性呢？在什么情况下一个问题找不到有效算法来求出正确解？2022-9-6第30页，此课件共44页哦 算法的时间复杂度从输入数据到计算出结果所需要的时间，它是输入长n（问题规模）的一个函数。算法的时间复杂性分析2022-9-6第31页，此课件共44页哦时间复杂度例如，求n个数最大者的一个算法如下：max=-999999for i=1:n if number(i)maxn maxn=number(i)endend记 T(n)=c1+c2n 为这个算法的时间复杂度。通常记T(n)=O(n).2022-9-6第32页，此课件共44页哦好算法还是坏算法好算法还是坏算法时间复杂度 若存在正数C和n0，使当nn0时，一个算法的执行时间T(n)Cf(n)，则称该算法花了f(n)阶的时间，记为T(n)=O(f(n)。2022-9-6第33页，此课件共44页哦时间复杂度分别是O(1),O(n),O(n2)。例：对下面三个简单的程序段，求时间复杂度。1)x=x+12)for i=1:n x=x+1 end3)for i=1:n for j=1:n x=x+1 end end好算法还是坏算法好算法还是坏算法2022-9-6第34页，此课件共44页哦典型算法的执行时间时间复杂度n2n32nn!计算时间1/64秒2秒274世纪5*2662世纪n=128时各典型算法的执行时间2022-9-6第35页，此课件共44页哦 有效算法或好算法：以多项式时间为限界的算法。指数时间算法或坏算法：任何多项式都不是其时间复杂度T(n)的上界的算法好算法还是坏算法好算法还是坏算法2022-9-6第36页，此课件共44页哦典型算法的处理规模算法时间复杂度一小时能处理的实例规模提高速度210倍一小时能处理的实例规模A1nN11024N1A2n2N232N2A32nN3N3+10A48nN4N4+3.32022-9-6第37页，此课件共44页哦时间复杂度函数的量级比较Lnfnfn)()(lim212022-9-6第38页，此课件共44页哦显然：1，log n，n，n2，n3，n3，2 n，n!量级是由低到高。时间复杂度函数的量级比较2022-9-6第39页，此课件共44页哦1无论计算机速度多么高，功能多么强，用指数时间算法不能解大型问题。2.算法的时间复杂度函数的量级越低，算法的效率越高（就大型问题而言）。2022-9-6第40页，此课件共44页哦实验内容实验内容1.1.设某校的田径选拔赛共设六个项目的比设某校的田径选拔赛共设六个项目的比赛，即跳高，跳远，标枪，铅球，赛，即跳高，跳远，标枪，铅球，100100米和米和200200米短跑，规定每个选手至多参加三个米短跑，规定每个选手至多参加三个项目的比赛。现有七名选手报名，选手项目的比赛。现有七名选手报名，选手所选项目如表所选项目如表1 1所示。现在要求设计一个比所示。现在要求设计一个比赛日程安排表，使得在尽可能短的时间内完赛日程安排表，使得在尽可能短的时间内完成比赛成比赛。布置实验布置实验第41页，此课件共44页哦实验内容实验内容姓 名 项目 1 项目 2 项目 3 赵 宁 跳 高 跳 远 铅 球 钱 虎 跳 远 100 米 孙 正 跳 高 200 米 李 江 200 米 标 枪 铅 球 杨 众 跳 远 铅 球 跳高 刘 平 铅 球 跳 高 200 米 王 跃 标 枪 跳 远 100 米 表1 参赛选手比赛项目表 2022-9-6第42页，此课件共44页哦商人们怎样安全过河 2.三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢？2022-9-6第43页，此课件共44页哦3.七桥问题、课程的时间安排问题和人、狼、羊、菜渡河问题都有哪些共同特征和隐含关系？在你的身边、社会生活、生产中去发现问题，举出能用线图描述的问题，建立图的模型。2022-9-6第44页，此课件共44页哦
