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

一种表示(biǎoshì)工具——图布置(bùzhì)实验实验(shíyàn)十主要内容一个时间安排问题图论的起源人、狼、羊、菜渡河问题好算法还是坏算法图的矩阵表示方法返回第一页，共40页。2023/4/29图论的起源(qǐyuán)：七桥问题第二页，共40页。2023/4/29

c

a

b

d

c

a

b

d

图论的起源(qǐyuán)：七桥问题第三页，共40页。2023/4/29欧拉——图论之父■定义：线图〔图论的研究对象〕■定理：一个线图存在通过每边正好一次回到出发点的路线的充要条件是：1〕图要是连通的2〕与图中每一顶点相连的边必须是偶数条。于是(yúshì)得出结论：七桥问题无解。图论的起源(qǐyuán)：七桥问题返回第四页，共40页。2023/4/29无向图，一般(yībān)用大写字母G,H表示。一种表示(biǎoshì)工具——图顶点边dcab第五页，共40页。2023/4/29无向图：G=(V,E)，顶点集：V；边集：E。e与顶点u,v相关联。u与v相邻(xiānɡlín)。两边相邻(xiānɡlín)。重边

c

a

b

d

一种(yīzhǒnɡ)表示工具——图第六页，共40页。2023/4/29两种特殊图：简单(jiǎndān)图完全图，记为Knb

d

c

a

b

d

c

a

一种表示(biǎoshì)工具——图第七页，共40页。2023/4/29有向图：V1V2V3V5V4想你能给出一个可用有向图描述的实际(shíjì)例子吗？一种表示(biǎoshì)工具——图第八页，共40页。2023/4/29网络(wǎngluò)这些数字可以代表距离(jùlí)，费用，可靠性或其他的相关参数。12345869157103一种(yīzhǒnɡ)表示工具——图第九页，共40页。2023/4/29(G)和(G)分别(fēnbié)表示图G的顶点数和边数在无向图中，v的度数，记为d(v)；在有向图中，v的出度，记为d+(v);v的入度，记为d-(v)。一种表示(biǎoshì)工具——图返回第十页，共40页。2023/4/29一个时间安排(ānpái)问题学校要为一年级的研究生开设六门根底数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养方案，注册(zhùcè)的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。第十一页，共40页。2023/4/29一个时间(shíjiān)安排问题第十二页，共40页。2023/4/29SNGRPM‡完成(wánchéng)上述表示课程冲突关系的线图直观(zhíguān)、清晰地表达信息的方式一个(yīɡè)时间安排问题返回第十三页，共40页。2023/4/29人狼羊菜渡河问题(wèntí)摆渡人F狼W羊G菜C第十四页，共40页。2023/4/29南岸状态：16种，其中WG,GC,WGC，从而(cóngér)FC,FW,F为不允许状态，FWGCFWGFWCFGCFGOCGWWC10个允许(yǔnxǔ)状态：人狼羊菜渡河问题(wèntí)第十五页，共40页。2023/4/29FWGCFWGFWCFGCFGOCGWWC寻求图中从顶点“FWGC〞到顶点“O〞的最短路径(lùjìng)，这样的路径(lùjìng)有几条？求出最优的渡河方案。想语言(yǔyán)描述时未显示的关系跃然纸上人狼羊菜渡河问题(wèntí)第十六页，共40页。2023/4/29FWGCFWGFWCFGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC人狼羊菜渡河问题(wèntí)返回第十七页，共40页。2023/4/29图的矩阵(jǔzhèn)表示方法邻接矩阵关联矩阵边矩阵(jǔzhèn)邻接(línjiē)顺序表返回第十八页，共40页。2023/4/29v1v2v5v6v7v4v3abjkcghidfe邻接矩阵第十九页，共40页。2023/4/29无向(wúxiànɡ)图的邻接矩阵：A=(aij)nn，其中无向图的邻接矩阵有何特点(tèdiǎn)？由邻接矩阵是否能作出原图？想邻接矩阵返回第二十页，共40页。2023/4/29关联矩阵v1v2v5v6v7v4v3abjkcghidfe第二十一页，共40页。2023/4/29无向(wúxiànɡ)图的关联矩阵：M=(mij)nm,其中想无向图的关联矩阵有哪些特征(tèzhēng)？由关联矩阵能否作出原图？关联矩阵返回第二十二页，共40页。2023/4/29边矩阵(jǔzhèn)v1v2v5v6v7v4v3abjkcghidfe返回第二十三页，共40页。2023/4/29好算法(suànfǎ)还是坏算法(suànfǎ)算法(suànfǎ)无效算法的时间(shíjiān)复杂性分析什么是算法时间复杂度量级比较有效算法返回第二十四页，共40页。2023/4/29一个算法就是解决某一特定(tèdìng)问题的方法，是一系列确定步骤，它必须在有限的时间内终止。表述一个算法一般有两种方式〔1〕步骤描述；〔2〕框图。什么(shénme)是算法第二十五页，共40页。2023/4/29例：求两个(liǎnɡɡè)正整数m和n的最大公因子的Euclid算法什么(shénme)是算法输入：正整数m,n。输出：m和n的最大公因子(yīnzǐ)。1〕求余数m除以n，令r为所得的余数(0r<n)。2)判断r是否为0。假设r=0，那么算法终止；否那么，转3)。3)互换。置mn,nr,返回第一步返回第二十六页，共40页。2023/4/29用行列式的定义求一个20阶行列式的值，即使(jíshǐ)是每秒1000万次的计算机也要花大约15万年的时间。算法(suànfǎ)无效第二十七页，共40页。2023/4/29好算法(suànfǎ)还是坏算法(suànfǎ)如何才能简便地判断一个算法的有效(yǒuxiào)性呢？在什么情况下一个问题找不到有效(yǒuxiào)算法来求出正确解？想返回第二十八页，共40页。2023/4/29算法的时间复杂度——从输入(shūrù)数据到计算出结果所需要的时间，它是输入(shūrù)长n〔问题规模〕的一个函数。

算法(suànfǎ)的时间复杂性分析第二十九页，共40页。2023/4/29时间(shíjiān)复杂度例如(lìrú)，求n个数最大者的一个算法如下：max=-999999fori=1:nifnumber(i)>maxnmaxn=number(i)endend记T(n)=c1+c2n为这个算法(suànfǎ)的时间复杂度。通常记T(n)=O(n).第三十页，共40页。2023/4/29好算法(suànfǎ)还是坏算法(suànfǎ)时间(shíjiān)复杂度假设存在正数C和n0，使当nn0时，一个算法的执行(zhíxíng)时间T(n)Cf(n)，那么称该算法花了f(n)阶的时间，记为T(n)=O(f(n))。第三十一页，共40页。2023/4/29时间(shíjiān)复杂度分别是O(1),O(n),O(n2)。例：对下面(xiàmian)三个简单的程序段，求时间复杂度。1)x=x+12)fori=1:nx=x+1end3)fori=1:nforj=1:nx=x+1endend好算法(suànfǎ)还是坏算法(suànfǎ)第三十二页，共40页。2023/4/29典型算法的执行(zhíxíng)时间时间复杂度n2n32nn!计算时间1/64秒2秒274世纪5*2662世纪n=128时各典型算法(suànfǎ)的执行时间返回第三十三页，共40页。2023/4/29

有效算法(suànfǎ)或好算法(suànfǎ)：以多项式时间为限界的算法(suànfǎ)。指数时间算法(suànfǎ)或坏算法(suànfǎ)：任何多项式都不是其时间复杂度T(n)的上界的算法(suànfǎ)好算法(suànfǎ)还是坏算法(suànfǎ)第三十四页，共40页。2023/4/29典型算法的处理(chǔlǐ)规模算法时间复杂度一小时能处理的实例规模提高速度210倍一小时能处理的实例规模A1nN11024N1A2n2N232N2A32nN3N3+10A48nN4N4+3.3返回第三十五页，共40页。2023/4/29〔1〕假设(jiǎshè)0<L<,称f1(n)与f2(n)同量级,记为O(f1(n))=O(f2(n));〔2〕假设(jiǎshè)L=0,那么称f1(n)的量级比f2(n)低,记为O(f1(n))<O(f2(n))；〔3〕假设(jiǎshè)L=,那么称f1(n)的量级比f2(n)高,记为O(f1(n))>O(f2(n))。时间(shíjiān)复杂度函数的量级比较第三十六页，共40页。2023/4/29显然(xiǎnrán)：1，logn，n，n2，n3，n3，…2n，n!量级是由低到高。时间(shíjiān)复杂度函数的量级比较第三十七页，共40页。2023/4/291．无论计算机速度(sùdù)多么高，功能多么强，用指数时间算法不能解大型问题。2.算法的时间复杂度函数的量级越低，算法的效率越高〔