《图的模型与算法初步.ppt》由会员分享，可在线阅读，更多相关《图的模型与算法初步.ppt（48页珍藏版）》请在三一办公上搜索。
1、Mathematica model,图的表示与算法初步,参考书：1.傅鹂 龚劬 刘琼荪 何中市 数学实验科学出版社2.张绍民 李淑华 数据结构教程C语言版中国电力出版社3.龚劬 图论与网络最优化算法 龚劬 重庆大学出版社主讲：龚 劬制作：龚 劬,主要内容,图的模型,算法初步,图的矩阵表示方法,结束,图的模型,一个时间安排问题,图论的起源七桥问题,人、狼、羊、菜渡河问题,图论的起源：七桥问题,图论的起源：七桥问题,graph,以四块陆地a,b,c,d为4个点(称为顶点),当且仅当两块陆地之间有一座桥时,就在对应的两点之间连一条线(称为边),得到图G.,一般用大写字母G,H表示无向图。,一种表示工
2、具图,三要素：顶点集V；边集E；关联函数,G=(V,E,),如(e1)=a,b，,e2,e3,e1,e4,e5,无向图,e与顶点u,v相关联 u与v相邻 两边相邻 重边,一种表示工具图,你能给出一些可用无向图描述的实际例子吗？,无向图,任何两个以上的人组成的人群中，至少有两个人，他们的朋友数一样多。在一次象棋比赛中，若每名选手与其余选手都比赛过，人数是n，求总盘数。设S=（x1，,x2，xn）是平面上的点集，其中任意两点间的距离至少是1，证明：距离正好是1的点对数最多为3n。在n个运动队间安排了一项竞赛，已赛n+1局，试证：存在一个队，它至少参加过3局比赛。,一种表示工具图,一些特殊的图,一种
3、表示工具图,)既没有环也没有重边的图，称为简单图,)任意两顶点都相邻的简单图,称为完全图.记为Kv,一种表示工具图,)若，且X 中任意两顶点不,相邻，Y 中任意两顶点不相邻，则称为二部图或,偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为,完全二部图或完全偶图,记为(m=|X|,n=|Y|),你能给出一些可用二部图描述的实际例子吗？,有向图：,你能给出一个可用有向图描述的实际例子吗？,一种表示工具图,加权图,这些数字可以代表距离，费用，可靠性或其他的相关参数。,一种表示工具图,返 回,一种表示工具图,返 回,定义 若图 的每一条边e 都赋以,一个实数w(e)，称w(e)为边e的权，G 连同边上
4、的权,称为赋权图.,定义 设 和 是两个图.,1)若,称 是 的一个子图,记,2)若，则称 是 的生成子图.,路径与连通,返 回,定义 1)无向图G的一条通路是指,一个有限非空序列，它的项交替,地为顶点和边，使得对，的端点是 和,称W是从 到 的一条通路，整数k称为W的长.,顶点 和 分别称为W的起点和终点.,2)若通路W的边互不相同但顶点可重复，则称W,为迹或道路.,3)若通路W的顶点和边均互不相同，则称W为路径,记为,路径与连通,定义,1)起点与终点重合的通路称为闭通路.,2)起点与终点重合的的路径称为圈，长,为k的圈称为k阶圈，记为Ck.,3)若在图G中存在(u,v)路径，则称顶点u和v
5、在图G,中连通.,4)若在图G中顶点u和v是连通的，则顶点u和v之,之间的距离d(u,v)是指图G中最短(u,v)路径的长；若,没有路径连接u和v，则定义为无穷大.,5)图G中任意两点皆连通的图称为连通图,一个时间安排问题,学校要为一年级的研究生开设六门基础数学课：数理统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。,一个时间安排问题,建立图的模型:以课程为顶点,当且仅当两门课程被同一个学生选(冲突)时,就在其对应的两顶点之间连
6、一边。,一个时间安排问题,返 回,1,2,2,2,3,3,人狼羊菜渡河问题,摆渡人Ferryman狼Wolf羊Sheep菜Vegatable,南岸状态：C44+C43+C42+C41+C40=24=16种，其中WS,SV,WSV，从而FV,FW,F为不允许状态,建立图的模型:以南岸的允许状态为顶点,共16个顶点,当且仅当两个状态可以通过一次摆渡互相转化时,就连一边.得到图G.问题就转化为求初始状态顶点到末状态顶点之间的最短路径问题.,1.渡河方案对应于图中从顶点“FWSV”到顶点“O”的链路？2.寻求图中从顶点“FWSV”到顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。,人狼羊菜
7、渡河问题,人狼羊菜渡河问题,返 回,图的矩阵表示方法,可达性矩阵,关联矩阵,边矩阵,邻接顺序表,返 回,邻接矩阵,邻接矩阵,无向图的邻接矩阵：A=(aij)nn，其中,无向图的邻接矩阵有何特点？由邻接矩阵是否能作出原图？,邻接矩阵,返 回,邻接矩阵,对有向图,其邻接矩阵,其中：,邻接矩阵,对于n=2,3,4,来说，考察邻接矩阵A的幂An.,邻接矩阵A中的第i行、第j列的元素为1,说明图中存在一条边(ui,uj),即存在一条从顶点ui到uj长度为1的路径。,矩阵A2中的第i行、第j列的元素aij(2)为,aij(2)等于从顶点ui到uj长度为2的不同路径的数目。,定理 设G=(V,E)是一简单有
8、向图，且A是G的邻接矩阵，对于m=1,2,3,来说，矩阵Am中(i,j)元素的值，等于从顶点ui到uj长度为m的路径数目。,邻接矩阵,其中：,对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义.,可达性矩阵,给定一个简单有向图G=(V,E),由G的邻接矩阵能够直接确定,G中是否存在一条从顶点vi到顶点vj的边。,构造矩阵Bn=A+A2+An,其中的(i,j)元素值，表明了从顶点vi到顶点vj长度小于或等于n的路径数目。如果(i,j)元素非零，则从vi到vj是可达的。,给定一个简单有向图G=(V,E),n=|V|,定义路径矩阵p=(pij)nn,使其元素为,关联矩阵,无向图的关联矩阵：
9、M=(mij)nm,其中,无向图的关联矩阵有哪些特征？由关联矩阵能否作出原图？,关联矩阵,返 回,边矩阵,返 回,无向或有向加权图 定义一个m列的矩阵第1、2行分别存放边的起点和 终点，如为加权图,只需增加一行数来表示各条边上的权.,好算法还是坏算法,算法无效,算法的时间复杂性分析,什么是算法,时间复杂度,量级比较,有效算法,返 回,一个算法就是解决某一特定问题的方法，是一系列确定步骤，它必须在有限的时间内终止。表述一个算法一般有两种方式（1）步骤描述；（2）框图。,什么是算法,例：求两个正整数m和n的最大公因子的Euclid算法,什么是算法,输入：正整数m,n。输出：m和n的最大 公因子。1
10、）求余数 m除以n，令r为所得的余数(0rn)。,2)判断r是否为0。若r=0，则算法终止；否则，转3)。3)互换。置mn,nr,返回第一步,返 回,用行列式的定义求一个20阶行列式的值，即使是每秒1000万次的计算机也要花大约15万年的时间。,算法无效,好算法还是坏算法,如何才能简便地判断一个算法的有效性呢？在什么情况下一个问题找不到有效算法来求出正确解？,返 回,算法的时间复杂度从输入数据到计算出结果所需要的时间，它是输入长n（问题规模）的一个函数。,算法的时间复杂性分析,算法的运行量：基本操作的执行次数 平均时间复杂度：,算法的时间复杂性分析,最坏时间复杂度：,返 回,时间复杂度,例如，
11、求n个数最大者的一个算法如下：max=-999999for i=1:n if number(i)maxn maxn=number(i)endend,记 T(n)=c1+c2n 为这个算法的时间复杂度。通常记T(n)=O(n).,好算法还是坏算法,时间复杂度,若存在正数C和n0，使当nn0时，一个算法的执行时间T(n)Cf(n)，则称该算法花了f(n)阶的时间，记为T(n)=O(f(n)。,时间复杂度分别是O(1),O(n),O(n2)。,例：对下面三个简单的程序段，求时间复杂度。,1)x=x+1,2)for i=1:n x=x+1 end,3)for i=1:n for j=1:n x=x+1 end end,好算法还是坏算法,典型算法的执行时间,n=128时各典型算法的执行时间,返 回,有效算法或好算法：以多项式时间为限界的算法。指数时间算法或坏算法：任何多项式都不是其时间复杂度T(n)的上界的算法,好算法还是坏算法,典型算法的处理规模,返 回,（1）若0O(f2(n)。,时间复杂度函数的量级比较,显然：1,log n,n,n2,n3,n3,2n,n!量级是由低到高。,时间复杂度函数的量级比较,1无论计算机速度多么高，功能多么强，用指数时间算法不能解大型问题。2.算法的时间复杂度函数的量级越低，算法的效率越高（就大型问题而言）。,返 回,再见！,
