资源描述
实验十主要内容实验十主要内容返回返回返回返回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu图论的起源：七桥问题图论的起源：七桥问题6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu c a b d c a b d 图论的起源：七桥问题图论的起源：七桥问题6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu欧拉图论之父 定义：线图（图论的研究对象）定理：一个线图存在通过每边正好一次回到出发点的路线的充要条件是：1）图要是连通连通的2）与图中每一顶点相连的边必须是偶数偶数条。于是得出结论：七桥问题无解。图论的起源：七桥问题图论的起源：七桥问题返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu无向图，一般用大写字母G,H表示。一种表示工具一种表示工具图图顶点顶点边边 d c a b 6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu 无向图：G=(V,E)，顶点集：V；边集：E。e与顶点u,v相关联。u与v相邻。两边相邻。重边 c a b d 一种表示工具一种表示工具图图6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu两种特殊图：简单图 完全图，记为Knb d c a b d c a 一种表示工具一种表示工具图图6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu有向图：V1V2V3V5V4你能给出一个可用有向图描述的实际例子吗？一种表示工具一种表示工具图图6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu网络网络这些数字可以代表距离距离，费用费用，可可靠性靠性或其他的相关参数。12345869157103一种表示工具一种表示工具图图6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu(G)和(G)分别表示图G的顶点数和边数在无向图中，v的度数，记为d(v)；在有向图中，v的出度，记为d+(v);v的入度，记为d-(v)。一种表示工具一种表示工具图图返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu一个时间安排问题一个时间安排问题 学校要为一年级的研究生开设六门基础数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu一个时间安排问题一个时间安排问题6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页GongquSNGRPM完成上述表示课程冲突关系的线图直观、清晰地表达已知信息的方式一个时间安排问题一个时间安排问题返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu人狼羊菜渡河问题人狼羊菜渡河问题摆渡人F狼W羊G菜C6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu 南岸状态：16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，FWGCFWGFWCFGCFGOCGWWC10个允许状态：人狼羊菜渡河问题人狼羊菜渡河问题6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页GongquFWGCFWG FWC FGCFGOCGWWC寻求图中从顶点“FWGC”到顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。语言描述时未显示的关系跃然纸上人狼羊菜渡河问题人狼羊菜渡河问题6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页GongquFWGCFWG FWC FGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC人狼羊菜渡河问题人狼羊菜渡河问题返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu图的矩阵表示方法图的矩阵表示方法邻接矩阵关联矩阵边矩阵邻接顺序表返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongquv1v2v5v6v7v4v3abjkcghidfe邻接矩阵6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu 无向图的邻接矩阵：A=(aij)nn，其中无向图的邻接矩阵有何特点？由邻接矩阵是否能作出原图？邻接矩阵返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu关联矩阵v1v2v5v6v7v4v3abjkcghidfe6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu 无向图的关联矩阵：M=(mij)nm,其中 无向图的关联矩阵有哪些特征？由关联矩阵能否作出原图？关联矩阵返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu边矩阵v1v2v5v6v7v4v3abjkcghidfe返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu好算法还是坏算法好算法还是坏算法算法无效算法的时间复杂性分析什么是算法时间复杂度量级比较有效算法返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu 一个算法就是解决某一特定问题的方法，是一系列确定步骤，它必须在有限的时间内终止。表述一个算法一般有两种方式（1）步骤描述；（2）框图。什么是算法6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu例：求两个正整数m和n的最大公因子的Euclid算法什么是算法输入：正整数m,n。输出：m和n的最大 公因子。1）求余数 m除以n，令r为所得的余数(0rmaxn maxn=number(i)endend记 T(n)=c1+c2n 为这个算法的时间复杂度。通常记T(n)=O(n).6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu好算法还是坏算法好算法还是坏算法时间复杂度 若存在正数C和n0，使当nn0时，一 个 算 法 的 执 行 时 间T(n)Cf(n)，则称该算法花了f(n)阶的时间，记为T(n)=O(f(n)。6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu时间复杂度分别是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好算法还是坏算法好算法还是坏算法6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu典型算法的执行时间时间复杂度n2n32nn!计算时间1/64秒2秒274世纪5*2662世纪n=128时各典型算法的执行时间返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu 有效算法或好算法：以多项式时间为限界的算法。指数时间算法或坏算法：任何多项式都不是其时间复杂度T(n)的上界的算法好算法还是坏算法好算法还是坏算法6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu典型算法的处理规模算法时间复杂度一小时能处理的实例规模提高速度210倍一小时能处理的实例规模A1nN11024N1A2n2N232N2A32nN3N3+10A48nN4N4+3.3返返返返 回回回回6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu（1）若0L,称f1(n)与f2(n)同量级,记为O(f1(n)=O(f2(n);（2）若L=0,则称f1(n)的量级比f2(n)低,记为O(f1(n)O(f2(n)。时间复杂度函数的量级比较6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu显然：1，log n，n，n2，n3，n3，2 n，n!量级是由低到高。时间复杂度函数的量级比较6/23/2024下一页下一页下一页下一页上一页上一页上一页上一页主主主主 页页页页Gongqu1无论计算机速度多么高，功能多么强，用指数时间算法不能解大型问题。2.算法的时间复杂度函数的量级越低，算法的效率越高（就大型问题而言）。返返返返 回回回回6/23/2024提问与解答环节Questions And Answers谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal
展开阅读全文