图的模型与算法初步

Mathematicamodel,图的表示与算法初步,参考书：1.傅鹂龚劬刘琼荪何中市数学实验科学出版社2.张绍民李淑华数据结构教程C语言版中国电力出版社3.龚劬图论与网络最优化算法龚劬重庆大学出版社主讲：龚劬制作：龚劬,主要内容,图的模型,算法初步,图的矩阵表示方法,结束,图的模型,一个时间安排问题,图论的起源七桥问题,人、狼、羊、菜渡河问题,图论的起源：七桥问题,图论的起源：七桥问题,graph,以四块陆地a,b,c,d为4个点(称为顶点),当且仅当两块陆地之间有一座桥时,就在对应的两点之间连一条线(称为边),得到图G.,一般用大写字母G,H表示无向图。,一种表示工具图,三要素：顶点集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局比赛。,一种表示工具图,一些特殊的图,一种表示工具图,)既没有环也没有重边的图，称为简单图,)任意两顶点都相邻的简单图,称为完全图.记为Kv,一种表示工具图,)若，且X中任意两顶点不,相邻，Y中任意两顶点不相邻，则称为二部图或,偶图；若X中每一顶点皆与Y中一切顶点相邻,称为,完全二部图或完全偶图,记为(m=|X|,n=|Y|),你能给出一些可用二部图描述的实际例子吗？,有向图：,你能给出一个可用有向图描述的实际例子吗？,一种表示工具图,加权图,这些数字可以代表距离，费用，可靠性或其他的相关参数。,一种表示工具图,返回,一种表示工具图,返回,定义若图的每一条边e都赋以,一个实数w(e)，称w(e)为边e的权，G连同边上的权,称为赋权图.,定义设和是两个图.,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在图G,中连通.,4)若在图G中顶点u和v是连通的，则顶点u和v之,之间的距离d(u,v)是指图G中最短(u,v)路径的长；若,没有路径连接u和v，则定义为无穷大.,5)图G中任意两点皆连通的图称为连通图,一个时间安排问题,学校要为一年级的研究生开设六门基础数学课：数理统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。,一个时间安排问题,建立图的模型:以课程为顶点,当且仅当两门课程被同一个学生选(冲突)时,就在其对应的两顶点之间连一边。,一个时间安排问题,返回,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”的最短路径，这样的路径有几条？求出最优的渡河方案。,人狼羊菜渡河问题,人狼羊菜渡河问题,返回,图的矩阵表示方法,可达性矩阵,关联矩阵,边矩阵,邻接顺序表,返回,邻接矩阵,邻接矩阵,无向图的邻接矩阵：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)是一简单有向图，且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,使其元素为,关联矩阵,无向图的关联矩阵：M=(mij)nm,其中,无向图的关联矩阵有哪些特征？由关联矩阵能否作出原图？,关联矩阵,返回,边矩阵,返回,无向或有向加权图定义一个m列的矩阵第1、2行分别存放边的起点和终点，如为加权图,只需增加一行数来表示各条边上的权.,好算法还是坏算法,算法无效,算法的时间复杂性分析,什么是算法,时间复杂度,量级比较,有效算法,返回,一个算法就是解决某一特定问题的方法，是一系列确定步骤，它必须在有限的时间内终止。表述一个算法一般有两种方式（1）步骤描述；（2）框图。,什么是算法,例：求两个正整数m和n的最大公因子的Euclid算法,什么是算法,输入：正整数m,n。输出：m和n的最大公因子。1）求余数m除以n，令r为所得的余数(0rmaxnmaxn=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)fori=1:nx=x+1end,3)fori=1:nforj=1:nx=x+1endend,好算法还是坏算法,典型算法的执行时间,n=128时各典型算法的执行时间,返回,有效算法或好算法：以多项式时间为限界的算法。指数时间算法或坏算法：任何多项式都不是其时间复杂度T(n)的上界的算法,好算法还是坏算法,典型算法的