End;
四、关键路径算法
利用AOV网络,对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一定的时间,为了能估算出某个活动的开始时间,找出那些影响工程完成时间的最主要的活动,我们可以利用带权的有向网,图中的边表示活动,边上的权表示完成该活动所需要的时间,一条边的两个顶点分别表示活动的开始事件和结束事件,这种用边表示活动的网络,称为“AOE网”。其中,有两个特殊的顶点(事件),分别称为源点和汇点,源点表示整个工程的开始,通常令第一个事件(事件1)作为源点,它只有出边没有入边;汇点表示整个工程的结束,通常令最后一个事件(事件n)作为汇点,它只有入边没有出边;其余事件的编号为2到n-1。在实际应用中,AOE网应该是没有回路的,并且存在唯一的入度为0的源点和唯一的出度为0的汇点。
下图表示一个具有12个活动的AOE网。图中有8个顶点,分别表示事件0到7,其中,0表示开始事件,7表示结束事件,边上的权表示完成该活动所需要的时间。
AOE网络要研究的问题是完成整个工程至少需要多少时间?哪些活动是影响工程进度的关键?
下面先讨论一个事件的最早发生时间和一个活动的最早开始时间。如上图,事件V j必须
在它的所有入边活动e ik(1≤k≤n)都完成后才能发生。活动e ik(1≤k≤n)的最早开始时间是与它对应的起点事件V ik的最早发生时间。所有以事件V j为起点事件的出边活动e jk(1≤k≤m)的最早开始时间都等于事件V j的最早发生时间。所以,我们可以从源点出发按照上述方法,求出所有事件的最早发生时间。
设数组earliest[1..n]表示所有事件的最早发生时间,则我们可以按照拓扑顺序依次计算出earliest[k]:
earliest[1]=0
earliest[k]=max{earliest[j]+dut[j,k]}
(其中,事件j是事件k的直接前驱事件,dut[j,k]表示边上的权) 对于图5_10,用上述方法求earliest[0..7]的过程如下:
earliest[0]=0
earliest[1]=earliest[0]+dut[0,1]=0+6=6
earliest[2]=earliest[0]+dut[0,2]=0+7=7
earliest[4]=max{earliest[1]+dut[1,4],earliest[2]+dut[2,4]}
=max{6+5,7+4}
=11
earliest[3]=max{earliest[1]+dut[1,3],earliest[4]+dut[4,3]}
=max{6+3,11+3}
=14
earliest[5]=max{earliest[3]+dut[3,5],earliest[4]+dut[4,5]}
=max{14+2,11+4}
=16
earliest[6]=earliest[4]+dut[4,6]=11+3=14
earliest[7]=max{earliest[3]+dut[3,7],earliest[5]+dut[5,7], earliest[6]+dut[6,7]} =max{14+5,16+2,14+4}
=19
最后得到的earliest[7]就是汇点的最早发生时间,从而可知整个工程至少需要19天完成。但是,在不影响整个工程按时完成的前提下,一些事件可以不在最早发生时间发生,而向后推迟一段时间,我们把事件最晚必须发生的时间称为该事件的最迟发生时间。同样,有些活动也可以推迟一段时间完成而不影响整个工程的完成,我们把活动最晚必须开始的时间称为该活动的最迟开始时间。一个事件在最迟发生时间内仍没发生,或一个活动在最迟开始时间内仍没开始,则必然会影响整个工程的按时完成。如上图,事件V j的最迟发生时间应该为:它的所有直接后继事件V jk(1≤k≤m)的最迟发生时间减去相应边上的权(活动e jk需要时间),取其中的最小值。且汇点的最迟发生时间就是它的最早发生时间,再按照逆拓扑顺序依次计算出所有事件的最迟发生时间,设用数组lastest[1..n]表示,即:lastest[n]=earliest[n]
lastest[j]=min{lastest[k]-dut[j,k]}
(其中,事件k是事件j的直接后继事件,dut[j,k]表示边上的权) 对于图5_10,用上述方法求lastest [0..7]的过程如下:
lastest[7]=earliest[7]=19
lastest[6]=lastest[7]-dut[6,7]=19-4=15
lastest[5]=lastest[7]-dut[5,7]=19-2=17
lastest[3]=min{lastest[5]-dut[3,5],lastest[7]-dut[3,7]}
=min{17-2,19-5}
=14
lastest[4]=min{lastest[3]-dut[4,3],lastest[5]-dut[4,5], lastest[6]-dut[4,6]}
=min{14-3,17-4,15-3}
=11
lastest[2]=lastest[4]-dut[2,4]=11-4=7
lastest[1]=min{lastest[3]-dut[1,3],lastest[4]-dut[1,4]}
=min{14-3,11-5}
=6
lastest[0]=min{lastest[1]-dut[0,1],lastest[2]-dut[0,2]}
=min{6-6,7-7}
=0
计算好每个事件的最早和最迟发生时间后,我们可以很容易地算出每个活动的最早和最迟开始时间,假设分别用actearliest和actlastest数组表示,设活动i的两端事件分别为事件j和事件k,如下所示:
活动i
事件j ————————> 事件k
则:actearliest[i]=earliest[j]
actlastest[i]=lastest[k]-dut[j,k]
对于上面的例子,用上述方法求得所有活动的最早和最迟开始时间如下表:
上表中的余量(称为开始时间余量)是该活动的最迟开始时间减去最早开始时间,余量不等于0的活动表示该活动不一定要在最早开始时间时就进行,可以拖延一定的余量时间再进行,也不会影响整个工程的完成。而余量等于0的活动必须在最早开始时间时进行,而且在规定的工期内完成,否则将影响整个工程的完成。我们把开始时间余量为0的活动称为“关键活动”,由关键活动所形成的从源点到汇点的每一条路径称为“关键路径”。
其实关键路径就是从源点到汇点具有最大路径长度的那些路径。这很容易理解,因为整个工程的工期就是按照最长路径计算出来的。很显然,要想缩短整个工程的工期,就应该想法设法去缩短关键活动的持续时间。读者可以根据上面的思想编程求出AOE网的关键路径。
Ch6、作业:
1、最短路径问题(short.pas,short.exe)
[问题描述] 平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
[输入格式]
输入文件为short.in,共n+m+3行,其中:
第一行为整数n。
第2行到第n+1行(共n行),每行两个整数x和y,描述了一个点的坐标。
第n+2行为一个整数m,表示图中连线的个数。
此后的m行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。
最后一行:两个整数s和t,分别表示源点和目标点。
[输出格式]
输出文件为short.out,仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度。
[样例输入]
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
[样例输出]
3.41
2、最优布线问题(wire.pas,wire.exe)
[问题描述] 学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们时间有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。
当然,如果将任意两台计算机都用数据线连接,费用将是相当庞大的。为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。
现在由你负责连接这些计算机,你的任务是使任意两台计算机都连通(不管是直接的或间接的)。
[输入格式]
输入文件wire.in,第一行为整数n(2<=n<=100),表示计算机的数目。此后的n行,每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
[输出格式] 输出文件wire.out,一个整数,表示最小的连接费用。
[样例输入]
3
0 1 2
1 0 1
2 1 0
[样例输出]
2(注:表示连接1和2,2和3,费用为2)
3、奇怪的数列(num.pas,num.exe)
[问题描述] 编程输入3个整数n,p,q,寻找一个由整数组成的数列(a1,a2,……,a n),要求:其中任意连续p项之和为正数,任意连续q项之和为负数。0[输入格式]
输入文件名为num.in,仅一行分别表示n,p,q,之间用一个空格隔开。
[输出格式]
输出文件名为num.out,只有一行,有解即输出这个数列,每个数之间用一个空格隔开。否则输出NO。
[输入输出样例]
num.in
6 5 3
num.out
-3 5 –3 -3 5 -3
num.in
3 2 1
num.out
NO
图论算法及其MATLAB程序代码
图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法: 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j <d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii <0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解:用Warshall-Floyd 算法,MATLAB 程序代码如下: n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)一笔画问题是图论中一个著名的问题
一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题[1]。一般认为,欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。 目录[隐藏] 1 问题的提出 2 一笔画定理 2.1 定理一 2.2 定理二 3 例子 3.1 七桥问题 3.2 一个可以一笔画的例子 4 一笔画问题与哈密顿问题 5 参见 6 参考来源 [编辑] 问题的提出 一笔画问题是柯尼斯堡问题经抽象化后的推广,是图遍历问题的一种。在柯尼斯堡问题中,如果将桥所连接的地区视为点,将每座桥视为一条边,那么问题将变成:对于一个有着四个顶点和七条边的连通图G(S,E),能否找到一个恰好包含了所有的边,并且没有重复的路径。欧拉将这个问题推广为:对于一个给定的连通图,怎样判断是否存在着一个恰好包含了所有的边,并且没有重复的路径?这就是一笔画问题。用图论的术语来说,就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径(一个圈或者一条链),如果路径闭合(一个圈),则称为欧拉回路[1]。 一笔画问题的推广是多笔画问题,即对于不能一笔画的图,探讨最少能用多少笔来画成。 [编辑] 一笔画定理 对于一笔画问题,有两个判断的准则,它们都由欧拉提出并证明[1]。 [编辑] 定理一 有限图G是链或圈的充要条件是:G为连通图,且其中奇顶点的数目等于0或者2。有限连通图G是圈当且仅当它没有奇顶点[2]。 证明[2][3]: 必要性:如果一个图能一笔画成,那么对每一个顶点,要么路径中“进入”这个点的边数等于“离开”这个点的边数:这时点的度为偶数。要么两者相差一:这时这个点必然是起点或终点之一。注意到有起点就必然有终点,因此奇顶点的数目要么是0,要么是2。 充分性: 如果图中没有奇顶点,那么随便选一个点出发,连一个圈C1。如果这个圈就是原图,那么
建立数学模型的方法步骤特点及分类
§16.3 建立数学模型的方法、步骤、特点及分类 [学习目标] 1.能表述建立数学模型的方法、步骤; 2.能表述建立数学模型的逼真性、可行性、渐进性、强健性、可转移性、非预制性、条理 性、技艺性和局限性等特点;; 3.能表述数学建模的分类; 4.会采用灵活的表述方法建立数学模型; 5.培养建模的想象力和洞察力。 一、建立数学模型的方法和步骤 —般说来建立数学模型的方法大体上可分为两大类、一类是机理分析方法,一类是测试分析方法.机理分析是根据对现实对象特性的认识、分析其因果关系,找出反映内部机理的规律,建立的模型常有明确的物理或现实意义.§16.2节的示例都属于机理分析方法。测试分折将研究对象视为一个“黑箱”系统,内部机理无法直接寻求,可以测量系统的输人输出数据、并以此为基础运用统计分析方法,按照事先确定的准则在某一类模型中选出一个与数据拟合得最好的模型。这种方法称为系统辨识(System Identification).将这两种方法结合起来也是常用的建模方法。即用机理分析建立模型的结构,用系统辨识确定模型的参数. 可以看出,用上面的哪一类方法建模主要是根据我们对研究对象的了解程度和建模目的决定的.如果掌握了机理方面的一定知识,模型也要求具有反映内部特性的物理意义。那么应该以机理分析方法为主.当然,若需要模型参数的具体数值,还可以用系统辨识或其他统计方法得到.如果对象的内部机理基本上没掌握,模型也不用于分析内部特性,譬如仅用来做输出预报,则可以系统辩识方法为主.系统辨识是一门专门学科,需要一定的控制理论和随机过程方面的知识.以下所谓建模方法只指机理分析。 建模要经过哪些步骤并没有一定的模式,通常与实际问题的性质、建模的目的等有关,从§16.2节的几个例子也可以看出这点.下面给出建模的—般步骤,如图16-5所示. 图16-5 建模步骤示意图 模型准备首先要了解问题的实际背景,明确建模的目的搜集建模必需的各种信息如现象、数据等,尽量弄清对象的特征,由此初步确定用哪一类模型,总之是做好建模的准备工作.情况明才能方法对,这一步一定不能忽视,碰到问题要虚心向从事实际工作的同志请教,尽量掌握第一手资料. 模型假设根据对象的特征和建模的目的,对问题进行必要的、合理的简化,用精确的语言做出假设,可以说是建模的关键一步.一般地说,一个实际问题不经过简化假设就很难翻译成数学问题,即使可能,也很难求解.不同的简化假设会得到不同的模型.假设作得不合理或过份
经典图论问题
5经典图论问题 5.1 一笔画问题 一笔画算法即是从起点a开始选择关联边(第一这条边不是往回倒,第二这条边在前面延伸路上没有出现过)向前延伸,如果到达终点b,得到a—b迹,判断路上的的边数是否为图的总边数,是就终止,否则选择迹上某个关联边没有用完的顶点v,用同样方式再搜索v—v的闭迹,添加到a—b迹上,即得到a—v---v—b迹,如果这个迹的边数还没有达到总边数,则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。
二、弗罗莱(Fleury )算法 任取v 0∈V(G),令P 0=v 0; 设P i =v 0e 1v 1e 2…e i v i 已经行遍,按下面方法从中选取e i+1: (a )e i+1与v i 相关联; (b )除非无别的边可供行遍,否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥(所谓桥是一条删除后使连通图不再连通的边); (c )当(b )不能再进行时,算法停止。 5.2 中国邮递员问题(CPP ) 规划模型: 设ij x 为经过边j i v v 的次数,则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s
5.3旅行推销员问题(TSP,货郎担问题)(NPC问题) 定义:包含图G的所有定点的路(圈)称为哈密顿路(圈),含有哈密顿圈得图称为哈密顿图。 分析:从一个哈密顿圈出发, 算法一:(哈密顿圈的充要条件:一包含所有顶点的连通子图,二每个顶点度数为2) 象求最小生成树一样,从最小权边加边,顶点度数大于3以及形成小回路的边去掉。 算法二: 算法三:
图论算法及matlab程序的三个案例
图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是,设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点,记()l v 为顶点 v 到源点v 1的最短距离, ,i j v v V ?∈,若 (,)i j v v E ?,记i v 到j v 的权ij w =∞。 Dijkstra 算法: ① 1{}S v =,1()0l v =;1{}v V v ??-,()l v =∞,1i =,1{}S V v =-; ② S φ=,停止,否则转③; ③ ()min{(),(,)} j l v l v d v v =, j v S ∈,v S ?∈; ④ 存在 1 i v +,使 1()min{()} i l v l v +=,v S ∈; ⑤ 1{} i S S v +=, 1{} i S S v +=-,1i i =+,转②; 实际上,Dijkstra 算法也是最优化原理的应用:如果12 1n n v v v v -是从1v 到 n v 的最短路径,则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中,我们用到了距离矩阵,矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ,若i v 到j v 无边,则realmax ij w =,其中realmax 是 MATLAB 常量,表示最大的实数+308)。 function re=Dijkstra(ma)
图论问题
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。 图论与数学的关系 图论本身是应用数学的一部份,因此,历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中,他所考虑的原始问题有很强的实际背景。 图论的起源 图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来 问题是要从这四块陆地中任何一块开始,通过每一座桥正好一次,再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题,他用抽像分析法将这个问题化为第一个图论问题:即把每一块陆地用一个点来代替,将每一座桥用联接相应的两个点的一条线来代替,从而相当于得到一个“图”(如下图)。 欧拉证明了这个问题没有解,并且推广了这个问题,给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后
来的欧拉路径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。 汉密尔顿的游戏与图论 1859年,英国数学家汉密尔顿发明了一种游戏:用一个规则的实心十二面体,它的20个顶点标出世界著名的20个城市,要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路,即“绕行世界”。用图论的语言来说,游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题,从而引起广泛的注意和研究。 四色猜想 在图论的历史中,还有一个最著名的问题--四色猜想。这个猜想说,在一个平面或球面上的任何地图能够只用四种颜色来着色,使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成,而两个国家相邻是指它们有一段公共的边界,而不仅仅只有一个公共点。这一问题最早于1852年由Francis Guthrie提出,最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特(Tait)、希伍德(Heawood)、拉姆齐和哈德维格(Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后,四色问题仍未解决。1969年,Heinrich Heesch发表了一
maab图论程序算法大全
图论算法m a t l a b实现求最小费用最大流算法的 MATLAB 程序代码如下: n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1)
for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;e nd if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 向赋权图中不会含负权回路, 所以不会出现k=n dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量
图论基础知识
图论基本知识 对于网络的研究,最早是从数学家开始的,其基本的理论就是图 论,它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络,无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台,而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论,尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生,我在此专辟一章介绍图论的基本知识,同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识,请参考相关文献[1-5]。 本章只给出非平凡的定理的证明,过于简单直观的定理的证明将 留给读者。个别定理涉及到非常深入的数学知识和繁复的证明,我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章,不影响整体阅读。 图的基本概念 图G 是指两个集合(V ,E),其中集合E 是集合V×V 的一个子集。 集合V 称为图的顶点集,往往被用来代表实际系统中的个体,集合E 被称为图的边集,多用于表示实际系统中个体之间的关系或相互作用。若{,}x y E ,就称图G 中有一条从x 到y 的弧(有向边),记为x→
y ,其中顶点x 叫做弧的起点,顶点y 叫做弧的终点。根据定义,从任意顶点x 到y 至多只有一条弧,这是因为如果两个顶点有多种需要区分的关系或相互作用,我们总是乐意在多个图中分别表示,从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G 中不含自己到自己的弧,我们就称图G 为简单图,或者更精确地叫做有向简单图。以后如果没有特殊的说明,所有出现的图都是简单图。记G 中顶点数为()||G V ν=,边数为()||G E ε=,分别叫做图G 的阶和规模,显然有()()(()1)G G G ενν≤-。图2.1a 给出了一个计算机分级网络的示意图,及其表示为顶点集和边集的形式。 图2.1:网络拓扑结构示意图。图a 是10阶有向图,顶点集为 {1,2,3,4,5,6,7,8,9,10},边集为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10};图b 是6阶无向图,顶点集为{1,2,3,4,5,6},边集为{13,14,15,23,24,26,36,56}。 从定义中可以看到,从任意顶点x 到y 不能连接两条或以上 边,本文所讨论的图,均符合上述要求,既均为不含多重边的图。如
图论及其算法
《图论及其算法》 --最短路问题 学院:通信学院 姓名:周旋 学号: S110131133 指导老师:陈六新
摘要 图论是数学的一个分支,它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这些图形通常用来描述某些事物之间的特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有的关系。通过对《图论及其应用》中最短路问题的深入学习,本文利用Dijkstra算法来解决日常生活中寻找最短路的问题。同时也是对本学期学习知识的巩固。 关键词:最短路径 Dijkstra算法迭代
Abstract Graph theory is a branch of mathematics, it studies the object of picture. Graph theory graph is given by the number of points and lines connecting the two points of the graphic form. These graphics are often used to describe a specific relationship between certain things. And with the point on behalf of things, with the line connecting the two points that have a corresponding relationship between two things. Through the "Graph Theory and Its Applications," in-depth study of the shortest path problem. In this paper, we use The Dijkstra's algorithm not only to solve everyday life to find the shortest path problem, but also for the consolidation of the semester to learn the knowledge. Keyword: shortest path Dijkstra's algorithm Iteration
图论模型的建立与转化
图论模型的建立与转化 关键字:图论模型、建立、转化 摘要 本文主要写图论模型的建立与转化,共分四部分: 第一部分引言说明了图论建模在整个信息学竞赛中的地位,以及图论模型与其它数学模型的异同,并指出很有研究总结图论建模的思想、方法及技巧的必要。 第二部分提出了图论模型建立中的两个要点:对原型中的要素进行适当的取舍和选择合适的理论体系,并分别举例加以详细分析,然后从中总结出了图论建模的总的原则:准确、清晰、简明。 第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方法:拆分转化和补集转化,并着重分析了前者。文中把前者分为三类:点→边、点→点、边→边,其中详细分析了第二类。 第四部分总结了全文,并指出了进一步研究图论模型的必要性 目录 一.引言 (2) 二.图论模型的建立 (2) I.要素的取舍 (2) II.选择合适的理论体系 (4) 三.图论模型的转化 (7) I.拆分转化 (7) II.补集转化 (10) 四.结语 (11)
正文 一.引言 信息学竞赛以解题为主,整个解题过程中一个重要的步骤就是数学建模,本文要讨论的就是数学建模的一个分支——图论建模。 图论建模是指对一些客观事物进行抽象、化简,并用图1来描述事物特征及内在联系的过程。 建立图论模型的目的和建立其它的数学模型一样,都是为了简化问题,突出要点,以便更深入地研究问题的本质;它的求解目标可以是最优化问题,也可以是存在性或是构造性问题;并且,和几何模型、运筹学模型一样,在建立图论模型的过程中,也需要用到集合、映射、函数等基本的数学概念和工具; 但图论模型和其它模型在它们的研究方法上又有着很大的不同,例如我们可以运用典型的图论算法来对图论模型进行求解,或是根据图论的基本理论来分析图论模型的性质,这些特殊的算法和理论都是其它模型所不具备的,而且在其它模型中,能用类似于图这种直观的结构来描述的也很少。 我们学习图论,一般都是通过书籍,但书上介绍的往往只限于图论模型的基本要素、一些图论的相关理论和经典算法等,至于如何建立图论模型、如何运用这些理论和算法、如何研究图论问题,都只有靠自己来理解、来领会,并通过实践来验证这些理解,通过摸索总结来提高自己的能力。 在建立图论模型的过程中,我们常常会遇到一些困难,例如难以建立点、边、权关系,或是原型中的一些重要因素无法纳入现有模型,或是现有模型虽能表示原型,却无法求解等等。为了克服这些困难,就需要用到某些独特的思想、方法和技巧,本文要写的正是我在学习、实践中得出的这方面的一点认识。 二.图论模型的建立 在建立模型之前,我们首先要对研究对象进行全面的调查,将原型理想化、简单化(对于竞赛题而言,这一步大部分已经由出题人完成了);然后对原型进行初步的分析,分清其中的各个要素及求解目标,理出它们之间的联系;下一步就是用恰当的模型来描述这些要素及联系。 I.要素的取舍 在用图论模型描述研究对象时,为了更突出与求解目标息息相关的要素,降低思考的复杂度,就不可避免地要舍去部分要素。下面我们就通过例1来分析一下。 【例1】导线排布Line[7]: 题目(文档附件:导线排布.doc)中蓝色的一段是问题描述的重点,其中涉及的要素有圆圈、N根导线、2N个端点、编号规则、导线的交叉等,求解目标是构造一种符合所给的导线交叉情况的导线排布方案。 起先,我们对题目描述的导线排布并不熟悉,或许我们能够画出几个无解或是多解的1在本文中,“图”专指由若干不同顶点与连接其中某些顶点的边所组成的图形[6],不包括一般的示意图。
图论经典问题
常见问题: 1、图论的历史 图论以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物,用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。 在自然界和人类社会的实际生活中,用图形来描述和表示某些事物之间的关系既方便又直观。例如,国家用点表示,有外交关系的国家用线连接代表这两个国家的点,于是世界各国之间的外交关系就被一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系,用网络图来描述某通讯系统中各通讯站之间信息传递关系,用开关电路图来描述IC中各元件电路导线连接关系等等。 事实上,任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系,所以图形中两点之间连接与否最重要,而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 图论的产生和发展经历了二百多年的历史,大体上可分为三个阶段: 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒,在波罗的海南岸)位于普雷格尔(Pregel)河的两岸,河中有一个岛,于是城市被河的分支和岛分成了四个部分,各部分通过7座桥彼此相通。如同德国其他城市的居民一样,该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题:从四部分陆地任一块出发,按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂,因此立刻吸引所有人的注意,但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文,Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题---一笔画问题,并给出一笔画问题的判别准则,从而判定七桥问题不存在解。Euler是这样解决这个问题的:将四块陆地表示成四个点,桥看成是对应结点之间的连线,则哥尼斯堡七桥问题就变成了:从A,B,C,D任一点出发,通过每边一次且仅一次返回原出发点的路线(回路)是否存在?Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题:迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树
数学竞赛中的图论问题
数学竞赛中的图论问题
分类号密级 U D C 编号 本科毕业论文(设计) 题目数学竞赛中的图论问题 所在院系数学与数量经济学院 专业名称数学与应用数学 年级 08级 学生姓名李曼 学号 0850410013 指导教师孙静
二 0一二年三月 学位论文原创性声明 本人郑重声明:所呈交的论文是本人在孙静老师的指导下独立进行研究所取得的研究成果. 除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品.本人完全意识到本声明的法律后果由本人承担. 作者:
日期:2012年3月29日 文献综述 一综述 在18世纪30年代,一个非常有趣的问题引起了欧洲数学家的浓厚兴趣,这个问题就是著名的哥尼斯堡七桥问题,即要求遍历哥尼斯堡七桥中的每一座桥恰好一次后回到出发点. 欧拉证明这是不可能完成的. 此后,欧拉发表了著名的论文《依据集合位置的阶梯方法》,这是图论领域的第一篇论文,标志着图论的诞生. 图论的真正发展始于20世纪五六十年代之间,是一门既古老又年轻的学科. 图论极有趣味性,严格来讲,它是组合数学的一个重要分支. 虽然图论只是研究点和线的学科,但是它的应用领域十分广泛,不仅局限于数学和计算机学科,还涵盖了社会学、交通管理等. 总的来说,图论这门科学具有以下特点:(1)图论蕴含了丰富的思想、漂亮的图形和巧妙的证明; (2)涉及的问题多且广泛,问题表明上简单朴素,本质上却十分深刻复杂; (3)解决问题的方法千变万化,非常灵活,常常是一种问题一种解法. 由以上三个特点可以看出,图论与其他的数学分支不同,它不像群论、拓扑等学科那样有一套完整的体系和解决问题的系统. 而且图论所研究的内容非常广泛,如图的连通性、遍历性、图的着色、图的可平面性等等. 二内容 由于图论具有蕴含了丰富的思想、漂亮的图形和巧妙的证明,涉及的问题多且广泛,问题表面上简单朴素,本质上却十分深刻复杂,解决问题的方法千变万化,非常灵活,常常是一种问题一种解法的特点. 随着数学竞赛越来越规范化,并且越来越考察考生的灵活运用知识的能力. 因此近年来,图论问题频繁的出现在数学竞赛中,如典型的一笔画问题、中国邮递员问题、旅游推销员问题、排课表问题等.
离散数学图论部分经典精彩试题及问题详解
离散数学图论部分综合练习 一、单项选择题 1.设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( ). A .6 B .5 C .4 D .3 2.已知图G 的邻接矩阵为 , 则G 有( ). A .5点,8边 B .6点,7边 C .6点,8边 D .5点,7边 3.设图G =,则下列结论成立的是 ( ). A .deg(V )=2∣E ∣ B .deg(V )=∣E ∣ C .E v V v 2)deg(=∑∈ D .E v V v =∑∈)deg( 4.图G 如图一所示,以下说法正确的是 ( ) . A .{(a , d )}是割边 B .{(a , d )}是边割集 C .{(d , e )}是边割集 D .{(a, d ) ,(a, c )}是边割集 5.如图二所示,以下说法正确的是 ( ). A .e 是割点 B .{a, e }是点割集 C .{b , e }是点割集 D .{d }是点割集 6.如图三所示,以下说法正确的是 ( ) . A .{(a, e )}是割边 B .{(a, e )}是边割集 C .{(a, e ) ,(b, c )}是边割集 D .{(d , e )}是边割集 ο ο ο ο ο c a b e d ο f 图一 图二
图三 7.设有向图(a )、(b )、(c )与(d )如图四所示,则下列结论成立的是 ( ). 图四 A .(a )是强连通的 B .(b )是强连通的 C .(c )是强连通的 D .(d )是强连通的 应该填写:D 8.设完全图K n 有n 个结点(n ≥2),m 条边,当( )时,K n 中存在欧拉回路. A .m 为奇数 B .n 为偶数 C .n 为奇数 D .m 为偶数 9.设G 是连通平面图,有v 个结点,e 条边,r 个面,则r = ( ). A .e -v +2 B .v +e -2 C .e -v -2 D .e +v +2 10.无向图G 存在欧拉通路,当且仅当( ). A .G 中所有结点的度数全为偶数 B .G 中至多有两个奇数度结点 C .G 连通且所有结点的度数全为偶数 D .G 连通且至多有两个奇数度结点 11.设G 是有n 个结点,m 条边的连通图,必须删去G 的( )条边,才能确定G 的一棵生成树. A .1m n -+ B .m n - C .1m n ++ D .1n m -+ 12.无向简单图G 是棵树,当且仅当( ). A .G 连通且边数比结点数少1 B .G 连通且结点数比边数少1 C .G 的边数比结点数少1 D .G 中没有回路. 二、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结 点,则G 的边数是 . 2.设给定图G (如图四所示),则图G 的点割 ο ο ο ο c a b f
图论的发展及其在现实生活中的几个应用
图论的发展及其在生活中的应用 数学与应用数学张佳丽 指导教师刘秀丽 摘要主要介绍了图论的起源与发展及其生活中的若干应用,如:渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法,如:最邻近法、求最小生成树的方法、求最优路线的方法等。 关键词图论生活问题应用 Graph Theory Development and the Application in Life Mathematics and applied mathematics Zhang Jiali Tutor Liu Xiuli Abstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem,arrangement problem,Chinese postman problem.It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree,the method of the best route,and so on. Key words graph theory life problem application 引言 图论是一门古老的学科,是数学中有广泛应用的一个分支,与其他的数学分支,如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系.图论中以图为研究对象,图形中我们用点表示对象,两点之间的连线表示对象之间的某种特定的关系.事实上,任何一个包含了二元关系的系统都可以用图论来模拟.而且,图论能把纷杂的信息变的有序、直观、清晰.由于我们感兴趣的是两对象之间是否有某种特定关系,所以图形中两点间连接与否尤为重要,而图形的位置、大小、形状及连接线的曲直长短则无关紧要.图论在自然科学、社会科学等各个领域都有广泛的应用.随着科学的发展,以及生产管理、军事、交通运输等方面提出了大量实际的需要,图论的理论及其应用研究得到飞速发展。从20世纪50年代以后,由于计算机的迅速发展,有力地推动了图论的发展,加速了图论向各个学科的渗透,尤其是网络理论的建立,图论与线性规划、动态规划等优化理论和方法互相渗透。同时,计算机的发展使图论成为数学领域中发展最快的分支
建立数学模型方法步骤 特点及分类
建立数学模型的方法、步骤、特点及分类 [学习目标] 1.能表述建立数学模型的方法、步骤; 2.能表述建立数学模型的逼真性、可行性、渐进性、强健性、可转移性、非 预制性、条理性、技艺性和局限性等特点;; 3.能表述数学建模的分类; 4.会采用灵活的表述方法建立数学模型; 5.培养建模的想象力和洞察力。 一、建立数学模型的方法和步骤 —般说来建立数学模型的方法大体上可分为两大类、一类是机理分析方法,一类是测试分析方法.机理分析是根据对现实对象特性的认识、分析其因果关系,找出反映内部机理的规律,建立的模型常有明确的物理或现实意义.测试分折将研究对象视为一个“黑箱”系统,内部机理无法直接寻求,可以测量系统的输人输出数据、并以此为基础运用统计分析方法,按照事先确定的准则在某一类模型中选出一个与数据拟合得最好的模型。这种方法称为系统辨识(System Identification).将这两种方法结合起来也是常用的建模方法。即用机理分析建立模型的结构,用系统辨识确定模型的参数. 可以看出,用上面的哪一类方法建模主要是根据我们对研究对象的了解程度和建模目的决定的.如果掌握了机理方面的一定知识,模型也要求具有反映内部特性的物理意义。那么应该以机理分析方法为主.当然,若需要模型参数的具体数值,还可以用系统辨识或其他统计方法得到.如果对象的内部机理基本上没掌握,模型也不用于分析内部特性,譬如仅用来做输出预报,则可以系统辩识方法
为主.系统辨识是一门专门学科,需要一定的控制理论和随机过程方面的知识.以下所谓建模方法只指机理分析。 建模要经过哪些步骤并没有一定的模式,通常与实际问题的性质、建模的目的等有关,从 §16.2节的几个例子也可以看出这点.下面给出建模的—般步骤,如图16-5所示. 图16-5 建模步骤示意图 模型准备首先要了解问题的实际背景,明确建模的目的搜集建模必需的各种信息如现象、数据等,尽量弄清对象的特征,由此初步确定用哪一类模型,总之是做好建模的准备工作.情况明才能方法对,这一步一定不能忽视,碰到问题要虚心向从事实际工作的同志请教,尽量掌握第一手资料. 模型假设根据对象的特征和建模的目的,对问题进行必要的、合理的简化,用精确的语言做出假设,可以说是建模的关键一步.一般地说,一个实际问题不经过简化假设就很难翻译成数学问题,即使可能,也很难求解.不同的简化假设会得到不同的模型.假设作得不合理或过份简单,会导致模型失败或部分失败,于是应该修改和补充假设;假设作得过分详细,试图把复杂对象的各方面因素都考虑进去,可能使你很难甚至无法继续下一步的工作.通常,作假设的依据,一是出于对问题内在规律的认识,二是来自对数据或现象的分析,也可以是二者的综合.作假设时既要运用与问题相关的物理、化学、生物、经济等方面的知识,又要充分发挥想象力、洞察力和判断力,善于辨别问题的主次,果断地抓住主要因素,舍弃次要因素,尽量将问题线性化、均匀化.经验在这里也常起重要作用.写出假设时,语言要精确,就象做习题时写出已知条件那样.
(完整word版)图论算法及matlab程序的三个案例
图论实验三个案例 单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是,设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点,记()l v 为顶点 v 到源点v 1的最短距离, ,i j v v V ?∈,若 (,)i j v v E ?,记i v 到j v 的权ij w =∞。 Dijkstra 算法: ① 1{}S v =,1()0l v =;1{}v V v ??-,()l v =∞,1i =,1{}S V v =-; ② S φ=,停止,否则转③; ③ ()min{(),(,)} j l v l v d v v =, j v S ∈,v S ?∈; ④ 存在 1 i v +,使 1()min{()} i l v l v +=,v S ∈; ⑤ 1{} i S S v +=U , 1{} i S S v +=-,1i i =+,转②; 实际上,Dijkstra 算法也是最优化原理的应用:如果121n n v v v v -L 是从1v 到 n v 的最短路径,则 121 n v v v -L 也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中,我们用到了距离矩阵,矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ,若i v 到j v 无边,则realmax ij w =,其中realmax 是 MATLAB 常量,表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma)
图论模型建立与转化
图论模型的建立与转化 安徽徐静 关键字:图论模型、建立、转化 摘要 本文主要写图论模型的建立与转化,共分四部分: 第一部分引言说明了图论建模在整个信息学竞赛中的地位,以及图论模型与其它数学模型的异同,并指出很有研究总结图论建模的思想、方法及技巧的必要。 第二部分提出了图论模型建立中的两个要点:对原型中的要素进行适当的取舍和选择合适的理论体系,并分别举例加以详细分析,然后从中总结出了图论建模的总的原则:准确、清晰、简明。 第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方法:拆分转化和补集转化,并着重分析了前者。文中把前者分为三类:点→边、点→点、边→边,其中详细分析了第二类。 第四部分总结了全文,并指出了进一步研究图论模型的必要性。 目录 一.引言 (2) 二.图论模型的建立 (2) I.要素的取舍 (2) II.选择合适的理论体系 (4) 三.图论模型的转化 (7) I.拆分转化 (7) II.补集转化 (10) 四.结语 (11)
正文 一.引言 信息学竞赛以解题为主,整个解题过程中一个重要的步骤就是数学建模,本文要讨论的就是数学建模的一个分支——图论建模。 图论建模是指对一些客观事物进行抽象、化简,并用图[1]来描述事物特征及内在联系的过程。 建立图论模型的目的和建立其它的数学模型一样,都是为了简化问题,突出要点,以便更深入地研究问题的本质;它的求解目标可以是最优化问题,也可以是存在性或是构造性问题;并且,和几何模型、运筹学模型一样,在建立图论模型的过程中,也需要用到集合、映射、函数等基本的数学概念和工具; 但图论模型和其它模型在它们的研究方法上又有着很大的不同,例如我们可以运用典型的图论算法来对图论模型进行求解,或是根据图论的基本理论来分析图论模型的性质,这些特殊的算法和理论都是其它模型所不具备的,而且在其它模型中,能用类似于图这种直观的结构来描述的也很少。 我们学习图论,一般都是通过书籍,但书上介绍的往往只限于图论模型的基本要素、一些图论的相关理论和经典算法等,至于如何建立图论模型、如何运用这些理论和算法、如何研究图论问题,都只有靠自己来理解、来领会,并通过实践来验证这些理解,通过摸索总结来提高自己的能力。 在建立图论模型的过程中,我们常常会遇到一些困难,例如难以建立点、边、权关系,或是原型中的一些重要因素无法纳入现有模型,或是现有模型虽能表示原型,却无法求解等等。为了克服这些困难,就需要用到某些独特的思想、方法和技巧,本文要写的正是我在学习、实践中得出的这方面的一点认识。 二.图论模型的建立 在建立模型之前,我们首先要对研究对象进行全面的调查,将原型理想化、简单化(对于竞赛题而言,这一步大部分已经由出题人完成了);然后对原型进行初步的分析,分清其中的各个要素及求解目标,理出它们之间的联系;下一步就是用恰当的模型来描述这些要素及联系。 I.要素的取舍 在用图论模型描述研究对象时,为了更突出与求解目标息息相关的要素,降低思考的复杂度,就不可避免地要舍去部分要素。下面我们就通过例1来分析一下。 【例1】导线排布Line[7]: 题目(文档附件:导线排布.doc)中蓝色的一段是问题描述的重点,其中涉及的要素有圆圈、N根导线、2N个端点、编号规则、导线的交叉等,求解目标是构造一种符合所给的导线交叉情况的导线排布方案。 起先,我们对题目描述的导线排布并不熟悉,或许我们能够画出几个无解或是多解的例子,但竞赛时我们不可能花更多的时间在熟悉题目上了,这时只有尽快地把我们不熟悉的、难于思考的原型转化成我们熟知的、便于思考的模型。 先来分析求解目标:所谓的构造导线排布方案,也就是找出每根导线两个端点的编号;而编号要满足的条件就是导线交叉的情况。 那么下一步我们就来分析一下编号与导线交叉之间的关系。记第i根导线两端点的标号为Ai和Bi(AiB1,A2>B2,A1>A2(根据编号规则),不同的是(a)满足A2>B1,B1>B2,