数学实验之图的模型及算法初步PPT课件

一种表示工具图,布置实验,实验十主要内容,一个时间安排问题,图论的起源,人、狼、羊、菜渡河问题,好算法还是坏算法,图的矩阵表示方法,返回,15.05.2020,图论的起源：七桥问题,15.05.2020,图论的起源：七桥问题,15.05.2020,欧拉图论之父定义：线图（图论的研究对象）定理：一个线图存在通过每边正好一次回到出发点的路线的充要条件是：1）图要是连通的2）与图中每一顶点相连的边必须是偶数条。于是得出结论：七桥问题无解。,图论的起源：七桥问题,返回,15.05.2020,无向图，一般用大写字母G,H表示。,一种表示工具图,15.05.2020,无向图：G=(V,E)，顶点集：V；边集：E。e与顶点u,v相关联。u与v相邻。两边相邻。重边,一种表示工具图,15.05.2020,两种特殊图：简单图完全图，记为Kn,一种表示工具图,15.05.2020,有向图：,你能给出一个可用有向图描述的实际例子吗？,一种表示工具图,15.05.2020,网络,这些数字可以代表距离，费用，可靠性或其他的相关参数。,一种表示工具图,15.05.2020,(G)和(G)分别表示图G的顶点数和边数在无向图中，v的度数，记为d(v)；在有向图中，v的出度，记为d+(v);v的入度，记为d-(v)。,一种表示工具图,返回,15.05.2020,一个时间安排问题,学校要为一年级的研究生开设六门基础数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。,15.05.2020,一个时间安排问题,15.05.2020,完成上述表示课程冲突关系的线图,直观、清晰地表达已知信息的方式,一个时间安排问题,返回,15.05.2020,人狼羊菜渡河问题,摆渡人F狼W羊G菜C,15.05.2020,南岸状态：16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，,10个允许状态：,人狼羊菜渡河问题,15.05.2020,寻求图中从顶点“FWGC”到顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。,语言描述时未显示的关系跃然纸上,人狼羊菜渡河问题,15.05.2020,人狼羊菜渡河问题,返回,15.05.2020,图的矩阵表示方法,邻接矩阵,关联矩阵,边矩阵,邻接顺序表,返回,15.05.2020,邻接矩阵,15.05.2020,无向图的邻接矩阵：A=(aij)nn，其中,无向图的邻接矩阵有何特点？由邻接矩阵是否能作出原图？,邻接矩阵,返回,15.05.2020,关联矩阵,15.05.2020,无向图的关联矩阵：M=(mij)nm,其中,无向图的关联矩阵有哪些特征？由关联矩阵能否作出原图？,关联矩阵,返回,15.05.2020,边矩阵,返回,15.05.2020,好算法还是坏算法,算法无效,算法的时间复杂性分析,什么是算法,时间复杂度,量级比较,有效算法,返回,15.05.2020,一个算法就是解决某一特定问题的方法，是一系列确定步骤，它必须在有限的时间内终止。表述一个算法一般有两种方式（1）步骤描述；（2）框图。,什么是算法,15.05.2020,例：求两个正整数m和n的最大公因子的Euclid算法,什么是算法,输入：正整数m,n。输出：m和n的最大公因子。1）求余数m除以n，令r为所得的余数(0rmaxnmaxn=number(i)endend,记T(n)=c1+c2n为这个算法的时间复杂度。通常记T(n)=O(n).,15.05.2020,好算法还是坏算法,时间复杂度,若存在正数C和n0，使当nn0时，一个算法的执行时间T(n)Cf(n)，则称该算法花了f(n)阶的时间，记为T(n)=O(f(n)。,15.05.2020,时间复杂度分别是O(1),O(n),O(n2)。,例：对下面三个简单的程序段，求时间复杂度。,1)x=x+1,2)fori=1:nx=x+1end,3)fori=1:nforj=1:nx=x+1endend,好算法还是坏算法,15.05.2020,典型算法的执行时间,n=128时各典型算法的执行时间,返回,15.05.2020,有效算法或好算法：以多项式时间为限界的算法。指数时间算法或坏算法：任何多项式都不是其时间复杂度T(n)的上界的算法,好算法还是坏算法,15.05.2020,典型算法的处理规模,返回,15.05.2020,（1）若0O(f2(n)。,时间复杂度函数的量级比较,15.05.2020,显然：1，logn，n，n2，n3，n3，2n，n!量级是由低到高。,时间复杂度函数的量级比较,15.05.2020,1无论计算机速度多么高，功能多么强，用指数时间算法不能解大型问题。2.算法的时间复杂度函数的量级越低，算法的效率越高（就大型问题而言）。,返回,实验内容,1.设某校的田径选拔赛共设六个项目的比赛，即跳