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

1、数学数学(shxu)实验之图的模型及算法初步实验之图的模型及算法初步第一页，共39页。图论的起源图论的起源(qyun)(qyun)：七桥问题七桥问题第1页/共39页第二页，共39页。 c a b d c a b d 图论图论(t ln)(t ln)的起源：七的起源：七桥问题桥问题第2页/共39页第三页，共39页。欧拉图论之父 定义：线图（图论的研究对象） 定理：一个线图存在通过每边正好一次回到出发点的路线的充要条件是：1）图要是连通的2）与图中每一顶点相连的边必须(bx)是偶数条。于是得出结论：七桥问题无解。图论的起源图论的起源(qyun)(qyun)：七桥问题七桥问题第3页/共39页第四页，

2、共39页。无向(w xin)图，一般用大写字母G,H表示。一种一种(y zhn(y zhn) )表表示工具示工具图图顶点顶点边边 d c a b 第4页/共39页第五页，共39页。 无向(w xin)图：G=(V,E)， 顶点集：V；边集：E。 e与顶点u, v相关联。 u与v相邻。 两边相邻。 重边 c a b d 一种表示一种表示(biosh)(biosh)工具工具图图第5页/共39页第六页，共39页。两种特殊图： 简单(jindn)图 完全图，记为Knb d c a b d c a 一种表示一种表示(biosh)(biosh)工具工具图图第6页/共39页第七页，共39页。有向图：V1V2

3、V3V5V4你能给出一个可用有向图描述的实际(shj)例子吗？一种表示一种表示(biosh)(biosh)工具工具图图第7页/共39页第八页，共39页。网络网络(wn(wnglu)glu)这些数字可以代表距离，费用，可靠性或其他的相关(xinggun)参数。12345869157103一种表示一种表示(biosh)(biosh)工具工具图图第8页/共39页第九页，共39页。(G)和(G)分别表示(biosh)图G的顶点数和边数在无向图中，v的度数，记为d (v)；在有向图中，v的出度，记为d+(v); v的入度，记为d-(v)。一种表示一种表示(biosh)(biosh)工具工具图图第9页/共

4、39页第十页，共39页。一个时间一个时间(shjin)(shjin)安排问题安排问题 学校要为一年级的研究生开设六门基础数学课：统计(S)，数值分析(N)，图论(t ln)(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。第10页/共39页第十一页，共39页。 S N G M R P李春兰郑文国姚南陈奇峰王润惠邹文燕万华李祖军黄大度史武军刘昆欧阳金郭志伟陈奇峰刘云刘元元黄大度董舟邹鑫赵云王凯李白彤甄军李欣陈俊于洪化范文李出荣张惠赵云曹林军胡志强张敏陈修建欧阳金李

5、晓李白彤万华曾光伟张星夏雯邵桂芳王学权单富民董舟杨欣吴军查小辉王坚程静波邹文燕卫迎新赵小民息志强陈修建邹鑫刘元兵杨成宝邱吉洲许茂陈俊周清武樊雪峰刘伟甄军姜永东一个一个(y )(y )时间安时间安排问题排问题第11页/共39页第十二页，共39页。SNGRPM完成上述(shngsh)表示课程冲突关系的线图直观(zhgun)、清晰地表达已知信息的方式一个时间一个时间(shjin)(shjin)安排问题安排问题第12页/共39页第十三页，共39页。人狼羊菜渡河问题人狼羊菜渡河问题(wnt)(wnt)摆渡人F狼W羊G菜C第13页/共39页第十四页，共39页。 南岸状态(zhungti)： 16种，其中W

6、G,GC,WGC，从而FC,FW,F为不允许状态(zhungti)，FWGCFWGFWCFGCFGOCGWWC10个允许(ynx)状态：人狼羊菜渡河问题人狼羊菜渡河问题(wnt)(wnt)第14页/共39页第十五页，共39页。FWGCFWGFWCFGCFGOCGWWC寻求图中从顶点(dngdin)“FWGC”到顶点(dngdin)“O”的最短路径，这样的路径有几条？求出最优的渡河方案。语言描述(mio sh)时未显示的关系跃然纸上人狼羊菜渡河问题人狼羊菜渡河问题(wnt)(wnt)第15页/共39页第十六页，共39页。FWGCFWGFWCFGCFGOCGWWCFWGCFWGFWCFGCFGOC

7、GWWC人狼羊菜渡河问题人狼羊菜渡河问题(wnt)(wnt)第16页/共39页第十七页，共39页。图的矩阵图的矩阵(j zhn)(j zhn)表示表示方法方法邻接矩阵关联矩阵边矩阵(j zhn)邻接(ln ji)顺序表第17页/共39页第十八页，共39页。v1v2v5v6v7v4v3abjkcghidfe010100010111100100010110010101010100110101000101076543217654321邻接矩阵第18页/共39页第十九页，共39页。 无向(w xin)图的邻接矩阵：A=(aij)nn，其中不相邻与当，相邻与当jijiijvv0vv1a无 向 图 的 邻

8、 接 矩 阵 有 何 特 点(tdin)？由邻接矩阵是否能作出原图？邻接矩阵第19页/共39页第二十页，共39页。001010000000011011100000010000100100011000101100001000001000001101000000000117654321kjihgfedcba关联矩阵v1v2v5v6v7v4v3abjkcghidfe第20页/共39页第二十一页，共39页。 无向(w xin)图的关联矩阵：M=(mij)nm, 其中 不相关联与若相关联，与若jijiijev0ev1m无向(w xin)图的关联矩阵有哪些特征？由关联矩阵能否作出原图？关联矩阵第21页/共

9、39页第二十二页，共39页。4376766654232654432211Ekjihgfedcba边矩阵(j zhn)v1v2v5v6v7v4v3abjkcghidfe第22页/共39页第二十三页，共39页。好算法好算法(sun f)(sun f)还还是坏算法是坏算法(sun f)(sun f)算法(sun f)无效算法(sun f)的时间复杂性分析什么是算法时间复杂度量级比较有效算法第23页/共39页第二十四页，共39页。 一个算法就是解决某一特定问题的方法，是一系列确定步骤，它必须在有限的时间内终止。 表述一个算法一般有两种方式（1） 步骤描述(mio sh)； （2） 框图。什么(shn

10、me)是算法第24页/共39页第二十五页，共39页。例：求两个(lin )正整数m和n的最大公因子的Euclid算法什么(shn me)是算法第25页/共39页第二十六页，共39页。 用行列式的定义求一个20阶行列式的值，即使(jsh)是每秒1000万次的计算机也要花大约15万年的时间。算法(sun f)无效第26页/共39页第二十七页，共39页。好算法好算法(sun f)(sun f)还还是坏算法是坏算法(sun f)(sun f) 如何才能简便地判断一个算法的有效性呢？在什么情况下一个问题(wnt)找不到有效算法来求出正确解？第27页/共39页第二十八页，共39页。 算法的时间复杂度从输入

11、数据到 计 算 出 结 果 所 需 要(xyo)的时间，它是输入长n（问题规模）的一个函数。 算法(sun f)的时间复杂性分析第28页/共39页第二十九页，共39页。时间(shjin)复杂度例如，求n个数最大者的一个算法(sun f)如下：max=-999999for i=1:n if number(i)maxn maxn=number(i) endend记 T(n)=c1+c2n 为这个算法(sun f)的时间复杂度。通常记T(n)= O(n).第29页/共39页第三十页，共39页。好算法好算法(sun f)(sun f)还还是坏算法是坏算法(sun f)(sun f)时间(shjin)复

12、杂度 若存在正数C和n0，使当nn0时，一 个 ( y ) 算 法 的 执 行 时 间T(n)Cf(n)，则称该算法花了f(n)阶的时间，记为T(n)=O(f(n)。第30页/共39页第三十一页，共39页。时间(shjin)复杂度分别是O(1), O(n), O( n2 ) 。例：对下面三个简单(jindn)的程序段，求时间复杂度。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好算法好算法(sun f)(sun f)还是坏算法还是坏算法(sun (sun f)f)第31页/共39页第三十二页，共39页。典型(

13、dinxng)算法的执行时间时间复杂度n2n32nn!计算时间1/64秒2秒274世纪5*2662世纪n=128时各典型算法的执行(zhxng)时间第32页/共39页第三十三页，共39页。 有效算法或好算法： 以多项式时间为限界的算法。 指数时间算法或坏算法： 任何(rnh)多项式都不是其时间复杂度T(n)的上界的算法好算法好算法(sun f)(sun f)还是坏算法还是坏算法(sun (sun f)f)第33页/共39页第三十四页，共39页。典型(dinxng)算法的处理规模算法时间复杂度一小时能处理的实例规模提高速度210倍一小时能处理的实例规模A1nN11024N1A2n2N232N2A

14、32nN3N3+10A48nN4N4+3.3第34页/共39页第三十五页，共39页。时间(shjin)复杂度函数的量级比较Lnfnfn)()(lim21第35页/共39页第三十六页，共39页。显然(xinrn)：1，log n，n，n2 ， n3 ，n3 ， 2 n ， n!量级是由低到高。时间复杂度函数(hnsh)的量级比较第36页/共39页第三十七页，共39页。1无论计算机速度多么高，功能多么强，用指数时间算法(sun f)不能解大型问题。 2. 算法(sun f)的时间复杂度函数的量级越低，算法(sun f)的效率越高（就大型问题而言）。第37页/共39页第三十八页，共39页。实验实验(shyn)(shyn)内容内容1. 1. 设某校的田径选拔赛共设六个项设某校的田径选拔赛共设六个项目的比赛，即跳高，跳远目的比赛，即跳高，跳远