数学建模十大经典算法(__数学建模必备资料)

1、From clown studio建模十大经典算法1、蒙特卡罗算法。该算法又称随机性模拟算法，足通过计算机仿真来解决问题的算法，同时通过模拟町以 来检验自己模型的正确性。2、数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到人最的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工几。3、线性规划、整数规划、多元规划、二次规划等规划类问题。建模竞赛人多数问题属于最优化问题，很多时候这些问题町以用数学规划算法米描述， 通常使用Lindo、Lingo、MATLAB软件实现。4、图论算法。这类算法町以分为很多种，包括故短路、网络流、二分图等算法，涉及到图论的问题町 以用这些

2、方法解决，需要认真准备。5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，很多场合町以用到竟赛中。6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。这些问题是用来解决一些较困难的故优化问题的算法，对于有些问题非常有帮助，但是 算敢的实现比较困难，需慎觅使用。7、网格算法和穷举法。网格算法和穷举法都是眾力搜索/优点的算法，在很多竟赛题中仃应用，当重点讨论模 型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工貝。8、一些连续离散化方法。很多问题都是实际來的，数据町以是连续的，而计算机只认的是离散的数据，因此将英 离散

3、化后进行差分代替微分、求和代替积分等思想是非常乘要的。9、数值分析算法。如果在比赛中釆用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求 解、矩阵运算、函数枳分等算法就需要额外编写库歯数进行调用。10、图象处理算法。赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理。历年全国数学建模试题及解法赛题解法93A非线性交调的频率设计拟合、规划93B足球队排名图论、层次分析、整数规划94A逢山开路图论、插值、动态规划94B锁只装箱问题图论、组合数学95A飞行管理问题非线性规划、线性规划95B大车

4、与冶炼炉的作业调度动态规划、排队论、图论96A最优捕鱼策略微分方程、优化96B节水洗衣机非线性规划97A冬件的参数设计非线性规划97B截断切割的最优排列随机模拟、图论98A类投资组合问题多目标优化、非线性规划98B灾情巡视的最佳路线图论、组合优化99A自动化乍床管理随机优化、计算机模拟99B钻井布局0-1规划、图论00ADNA序列分类模式识别、Fishei-判别、人工神经网络00B钢管订购和运输组合优化、运输问题01A血管三维巫建曲线拟合、曲面巫建01B公交乍调度问题多冃标规划02A车灯线光源的优化非线性规划02B彩栗问题单目标决策03ASARS的传播微分方程、差分方程03B露天矿生产的车辆安

5、排整数规划、运输问题04A奥运会临时超市网点设计统计分析、数据处理、优化04B电力市场的输电阻塞管理数据拟合、优化05A氏江水质的评价和预测预测评价、数据处理05B DVD在线租赁随机规划、整数规划06A出版资源配置06B艾滋病疗法的评价及疗效的预测07A中国人口增长预测07B乘公交，看奥运多目标规划 数据处理 图论08A数码相机定位08B高等教育学费标准探讨09A制动器试验台的控制方法分析09B眼科病床的合理安排动态规划10A10B赛题发展的特点：1对选F的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较兔，于工 计算不能完成，如03B,某些问题需要使用计算机软件，01A。问题

6、的数据读取需要计算机 技术，如00A （大数据），01A （图象数据，图象处理的方法获得），04A （数据库数据，数 据库方法，统计软件包）。计算机模拟和以算法形式给出最终结果。2赛题的开放性增人解法的女样性，一道赛题可用多种解法。开放性还衷现在对模型假设和 对数据处理上。3试题向大规模数据处理方向发展4求解算法和各类现代算法的融合从历年竞赛题来看，常用的方法：线性规划整数规划非线性规划动态规划层次分析法图论方法拟合方法插值方法随机方法微分方程方法各种算法的详解一、蒙特卡洛算法1、含义的理解以概率和统计理论方法为基础的一种计算方法。也称统计模拟方法，是指使用随机数（或更 常见的伪随机数）來解决

7、很多计算问题的方法，它是将所求解的问题同一定的概率模型相 联系，用计算机实现统计模拟或抽样，以获得问题的近似解。2、算法实例（有很多相似的例题，包括平行线等）在数值枳分法中，利用求单位圆的1/4的面积来求得P1/4从而得到Pl。单位圆的1/4面枳是 一个扇形，它是边长为1单位正方形的一部分。只要能求出扇形面积S1在正方形而积S中 占的比例K=S1/S就立即能得到S1,从而得到P1的值。怎样求出扇形面积在正方形面积中 占的比例K呢？ 一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个 位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数m与所投点的总数n的比m/n作为k的近

8、似值。P落在扇形内的充要条件足lC + y<l .求Pio已知：K= , K« , s=l, sl= sn4程序：(该算法口J以修改后用Mathematica计算或Matlab)/*利用蒙特卡洛算法近似求圆周率Pi*/*程序使用：VC4H5.0*/#indude<stdio.h>#indude<math.h>#include<stdlib.h>#define COUNT 800严循环取样次数，每次取样范围依次变大*/void mainOdouble x,y;int num=0;int i;for(i=0 ;i VCOUNT i 卄)x=ran

9、dO*l 0/RAND_MAX;/*RAND_MAX=32767,包含在vstdio.h>中水/ y=randO*l 0/RAND_MAX;if(x*x+y*y)<=l)mmi-H-; /*统计落在四分之一圆之内的点数*7printf(nPi 值等于：%firnum*4.0/COUNT);结果：测试6次的结果显示：循坏取样次数求得的P1值8003 085CC080003.110C00800003.1352008000003 13915080000003 141393From clown studio800000003 141321可以看出:随看点数的增加，求得的Pl值渐渐接近真实值

10、。如果加入程序：si*and（time（NULL）,同时循环取样次数一定，让取样结果随时间变化，当 取样次数为80000000时，可得6次的结果显示：3 1412903.141400 3 1412683.141484 3 141358 3 1414623、应用的范国蒙特卡罗方法在金融工程学，宏观经济学，计算物理学（如粒子输运计算、最子热力学计算、空气动力学计算）等领域应用广泛。4、参考书籍1 蒙特卡罗方法及其在粒子输运问题中的应用2蒙特卡罗方法引论二、数据拟合、参数估计、插值等数据处理算法（1）数据拟合在Nfathematica中，用Fit对数据进行最小二乘拟合：Fit data,fims,v

11、ars在Matlab中，工具箱（toolboxes）中有曲线拟合工具（curve Fitting）* 实例：2010年苏北赛B题 温室中的绿色生态臭氧病虫害防治中关于中华稻蝗密度与水稻减产 率之间的关系町以通过数据拟合來观察（简单举例，没有考虑全部数据）数据:密度（头/m）310203040减产率（%）2.412. 916. 320. 126. 8程序(Mathematica )：data=(3,2.4,(10,12.9,(20,16.3),30,20.1,(40,26.8; al=Fitdata,1,x,x八2,x八3,xShowListPlotdata,Filling->Axis,P

12、lot al, x,0,60 结果：-3.68428+2.38529 x-0.0934637 x=+0.00132433 x3（2）参数估计（参考书：概率论与数理统计） 参数估计为统计推断的基本问题，分为点估计和区间估计。点估计：矩估计法x连续型随机变最，概率密度f（x；q,q,q）x为离散型随机变量分布律px=x= p（%q,q,久）q，2，,q为待估参数，是来自x的样本，假设总体x的前k阶矩存在，为（X连续型）或” = E（X】）=工£p（x；q,，,久）（X离散型）1 =1,2,k （其中&是xuj能取 JCERy值的范国）。一般來说，它们是q,a,q的函数。基于样本矩

13、a =依概率收敛1】台于相应的总体矩“（l=l,2,k）,样本矩的连续函数依概率收敛于相应的总体矩的连续函 数，我们就用样本矩作为相应的总体矩的估计量，而以样本矩的连续函数作为相应的总体矩 的连续函数的估计量。这种估计方法成为矩估计法。最大似然估计法X连续型随机变量 似然函数L（9） = L（x1,x2,.,xn；） = nf（；）其中1=1 1=1是来自X的样本XpX"九的联合密度。x为离散型随机变最似然函数1/0 = 1/齐,冯,£；0 =冇卩（;0,6®其中fjp区；。）是來自X的样本务仝2，£的联合分布律。 1=1若 L（0 = 1/逅，圣,，斗

14、；6 = 111宓1/齐心,0E则称&.*,£）为8的最人似然估计值，称/（XpX?,£）为0的最人似然估计量。这样，确定最人似然估计最的问题就归结为微分学中的求垠人值的问题了。估计量的评选标准为：（丄）无偏性（2）有效性（3）相合性区间估计：对于一个未知最，人们在测最或计算时，常不以得到近似值为满足，还需要估计误差，即要 求知道近似值的精确程度（亦即所求真值所在的范I韦I）。这样的范I韦I常以区间的形式给出， 同时还给出此区间包含参数真值的对信度，这种形式的估计称为区间估计，这样的区间即所 谓冒信区间。正态总体均值、方差的置信区间与单侧置信限（置信水平为1-

15、71;）一个正态总体未知参数英他参数枢轴量的分布置信区间b2己知z = £dn（oj） cr! yjn（唇 Z“）A未知1 =t(n-l)S/Vn-s(X 土za/2 (n 一 1)CT未知(n-l)S2(n-l)S2zt2(Ta(T另外还包括两个正态总体的情况，其他区间估计：(0-1)分布参数的区间估计(3) 插值1、含义的理解在离散数据的基础匕补插连续曲数，使得这条连续曲线通过全部给定的离散数据点。插值是 离散函数逼近的巫要方法，利用它叮通过函数在有限个点处的取值状况，估算出函数在其他 点处的近似值(与拟合的不同点在于拟合的函数不需通过每一个离散点)。插值问题的提法是：假定区间a

16、, b上的实值函数f (x)在该区间上n+1个互不相 同点x0, xl . xn处的值是fx0,f (xn),要求估算f (x)在a, b中某点的值。 其做法是：在事先选定的一个由简单函数构成的有n+1个参数CO, Cl, .Cn的函 数类(CO, Cl, .Cn)中求出满足条件 P (xi) =f (xi) (1 = 0, 1. . n)的函数 P(x), 并以P0作为f0的估值。此处f (x)称为被插值旳数，x0, xl, .xn称为插值结(节) 点，(CO, Cl, .Cn)称为插值函数类，上面等式称为插值条件，(CO, . Cn)中 满足上式的函数称为插值函数，R (x) = f (x

17、) -P (x)称为插值余项。当估算点 属于包含x0, xl. xn的最小闭区间时，相应的插值称为内插，否则称为外插。2、基本类型多项式插值在般插值问题中，若选取为n次多项式类，由插值条件可以唯一确定一个n次插 值多项式满足上述条件。拉恪朗口插值和牛顿插值都屈于多项式插值。拉格朗日插值：设连续函数y = f (x)在a,b上对给定n+1个不同结点：,检分别取函数值,%,其中 乂=片(兀)i = 0,1 v n(1)试构造一个次数不超过n的插值多项式匕(x) = % + aX+gx2 + + ©疋(2)使之满足条件匕(兀)i = 0,1,-2-,n(3)构造n次多项式l'x)

18、k = 0,lv n 使(4)由 只（兀）=Z yA） =y： i = o, i ,2,n k=i即pn（x）满足插值条件，于是问题归结为具体求出基本插值实项式h（x）。根拯（4）式h（x）以外所有的节点都是lk（x）的根，因此令h (x) = 2(x- Xq)(x-齐)(x- Vi)(x-观乜)(x xj= 2fJ(x-xJ) j=0 存k又由lk(x)=l,得:（兀一毛）（怎氏）-忑1）（彖兀也）（ xj所以旳(X)= (Xf( -况)(忑-xi) - Vi)( - +1) ( - )代入（5）得拉格朗日插值多项式为:W = S1k(x)yk=Sk=0k=OYk牛顿描值：（拉格朗日插值的峡

19、点）拉格朗口插值公式的形式虽然冇一定的规律，但是肖增加 一个节点时，不仅要增加项数，而且以前各项也必须觅新全部计算，不能利用己有的 结果。为克服这一缺点，我们取用另一种形式一一牛顿插值公式。牛顿插值公式中用到了差商。一般称：差商町列表计算：XIyi一阶差商二阶差商三阶差商xOf(xO)X1f(xl)f xO, xlxZf (xZ)f xl, xZf xO, xl, x2x3f(x3)f x2, x3f xl, x2» x3f xO, xl, x2, x3为f（x）在Xg,Xp,处的n阶差商。四阶差商x4 f (x4) f x3, x4 f x2, x3, x4 f xlt x2t x

20、3, x4 f xOm> x4由差商定义可知E(x)= f(Xo)+坷(X-Xjj)+ f%,兀，叩(X-Xjj)(X-齐)由差商定义町求得f(X)= f (Xq) +(X- Xq) fXo，xJ+(X-Xq)(X-齐)口毛,齐,卷+ +(x_x；j)(x_ 齐)(x_ 心i)fXo，»i，兀+ (X-Xo)(X-Xi).(X-) 口耳忌，齐,，兀J记Nn(x) = f (*)+ (x- Xq) fXQ,齐+ (x- Xq)(X-舌)f%“+ -+(x-x0)(x-).(x-_1)fx0,x1,.,x11%( x> g oX)(X 1 X) K x)fl %jX ,冲则

21、(x) = Nn(x) + Rh(x)其中Nn(x)称为n次牛顿插值多项式，RJx)是截断误差。最终我们町以证明Nn(X)满足插值条件Nn() = §(兀)i = 0,1,2,.,n因此有叫(£)=(X牛顿插值公式的优点是：当增加一个节点时，只要再增加一项就行了，即有递推式当然，与拉格朗口插值相比它还有节省运算次数的优点(尤其是节省乘法运算次数)。 分段插值与样条插值为了避免高次插值町能出现的大幅度波动现象，在实际应用中通常采用分段低次插值 来提离近似程度埃尔米特插值许多实际插值问题中，为使插值两数能更好地和原來的两数更合，不但要求二者在节 点上函数值相等，而且还要求柑切，

22、对应的导数值也相等，其至要求高阶导数也相等。 这类插值称作切触插值，或埃尔米特(Hermite)插值。满足这种要求的插值多项式就是 埃尔米特插值多项式三角函数插值当被插曲数是以2兀为周期的函数时，通常用n阶三角多项式作为插值函数，并通过 高斯三角插值表出。三、线性规划、整数规划.多元规划、二次规划(1) 线性规划1、含义的理解线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅 助人们进行科学管理的一种数学方法研究线性约束条件下线性目标函数的极值问题的数学 理论和方法，英文缩写LP。它是运筹学的一个重要分支。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果

23、是人们不可缺少的要求, 而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设 $和新型原材料二是生产组织与计划的改进，即介理安排人力物力资源线性规划所研究的 是：在一定条件F，合理安排人力物力等资源，使经济效果达到最好一般地，求线性目标 函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条 件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变童、约束条件、目标函 数是线性规划的三要素。2、线性规划问题的数学模型的-般形式和模型建立（1）列出约束条件及目标函数（2）画出约束条件所表示的可行域（3）在可行域内求目 标函数的最优解及最优值（实

24、际问题中建立数学模型一般有以下三个步骤：根据影响所要达 到目的的因素找到决策变最：2由决策变量和所在达到目的之间的函数关系确定目标函数； 3由决策变量所受的限制条件确定决策变量所要满足的约束条件。） 所建立的数学模型具有以下特点：（1）、每个模型都有若干个决策变量（xl,x2,x3，xn）,其中n为决策变量个数。决策变 量的一组值表示一种方案，同时决策变量一般是非负的。（2）、目标函数是决策变屋的线性函数，根据具体问题可以是最人化（max）或最小化（min）, 二者统称为最优化（opt）。（3）、约束条件也是决策变量的线性函数。当我们得到的数学模型的目标函数为线性函数, 约束条件为线性等式或不

25、等式时称此数学模型为线性规划模型。3、实例生产计划问题问题：某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备18台时, 原材料A : 4吨，原材料B： 12吨；已知单位产品所需消耗生产资料及利润如卜表。问 应如何确定生产计划使企业获利最多？品资源'、甲乙资源量设备/台时318原料A/吨104原料B/吨012单位嵐利/万元55设xl为甲产品分配的设备台数，为乙产品分配的台数。则 条件限制为：3*xl+2*x2<18 l*xl+0*x2<4 0*xl+2*x2<12 xl>0, x2>0 求 max z=3*xl+5*x2用lingo编

26、程，程序如卜：max=3*xl+5*x2;3*xl+2*x2<=l &xlv=4,x2<=6,xl>=0,x2>=0,结果为：Global optimal solution foundObjective value:36. 00000Total solver iterations:1VariableValue2.0000006.000000Reduced Cost0.000000D.000000XIX2RowSlack.or SurplusDual Price136.000001.000000o0.0000001.0000D03o0000000.0000D040

27、.0000003.0000005o0000000.00000066.0000000.0000D0即在xl=2» 乂2=6时企业获利最多，为36万元。4、线性规划的应用在企业的各项管理活动中，例如计划、生产、运输、技术等问题,线性规划是指从各种限制条 件的组合中，选择出放为介理的计算方法,建立线性规划模型从而求得最佳结果广泛应用于 军爭作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力 等资源作出的最优决策，提供科学的依据。（2）整数规划一类要求问题的解中的全部或一部分变最为整数的数学规划。从约束条件的构成又町细分为 线性，二次和非线性的整数规划。在线性规划问

28、题中，有些域优解町能是分数或小数,但对于某些具体问题，常要求某些变量的解必须足整数。例如，当变量代表的是机器的台 数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整 数解舍入化整就町以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的 方法来求解整数规划。在整数规划中，如果所仃变量都限制为整数，则称为纯整数规划； 如果仅一部分变量限制为盛数，则称为混介整数规划。整数规划的一种特殊情形是01规划, 它的变数仅限于0或1。不同于线性规划问题，整数和01规划问题至今尚未找到一般的多 项式解法。组合锻优化通常都可表述为整数规划问题。两者都是在有限个町供选择的方案中

29、，寻找满 足一定约束的最好方案。有许多典型的问题反映整数规划的广泛巧景。例如，背袋（或装载） 问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的 覆孟问题）、旅行推销员问题，车辆路径问题等。因此整数规划的应用范圉也是极其广泛的。 它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编 码和经济分析等方面也有新的应用。整数规划是从1958年由RE戈莫里提出割平面法之后形成独立分支的。解整数规划最典 型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随 一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通

30、过松地问题的解來 确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题來 替代它。随即再选择一个尚未被舍弃的或替代的原问题的衍生问题，車复以上步骤直至不 再剩令未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它 们都是在上述框架下形成的。0-1规划在整数规划中占有更要地位，一方面因为许多实际问题，例如指派问题、选地问题、 送货问题都町归结为此类规划，另一方面任何右界变最的整数规划都与0规划等价，用 0-1规划方法还町以把多种非线性规划问题表示成整数规划问题，所以不少人致力丁这个 方向的研究。求解01规划的常用方法是分枝定界法，对齐种特殊问题还冇一些

31、特殊方法， 例如求解指派问题用匈牙利方法就比较方便。（4）二次规划二次规划是非线形规划中一类特殊的数学规划问题，它的解是町以通过求解得到的。通常通 过解英库恩一塔克条件（KT条件），获取一个KT条件的解称为KT对，英中与原问题的变 最对应的部分称为KT点。二次观划分为凸二次规划与非凸二次规划，前者的KT点便是其全局极小值点，而后者的 KT点町能连局部极小值点都不是。若它的目标函数是二次函数，则约束条件是线性的。由 于求解二次规划的方法很多，所以较为复杂：英较简便易行的足沃尔夫法，它是依据库恩 塔克条件，在线性规划单纯形法的基础卜.加以修正而成的。此外还有莱姆基法、毕尔法、 凯勒法等。From

32、clown studioFrom clown studioU!图论: （参考资料：建模教程（图与网络）From clown studio（1）含义的理解图论是专门研究图的理论的一门数学分支，属于离散数学范踌，与运筹学有交叉。图论中常用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定 关系。一般来说，通常用点表示研究对象、用点与点之间的线表示研究对彖之间的特定关系。在一般情况卜，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之 间的关系，显的并不重要。因此，图论中的图与几何图，工程图等本质上是不同的。（2）历史（包括应用范闱）它有200多年历史，大体可划分为三

33、个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题閑游戏而产生，故有 代表性的工作是所谓的Euler七桥问题，即一笔画问题。第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大最出现，如Hamilton问题, 地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把 树应用于化学领域，Kirchhoff用树去研究电网络等.第三阶段是二十世纪中叶以后，由生产管理、军班、交通、运输、计算机网络等方面提出实 际问题，以及人型计算机使人规模问题的求解成为可能，特别是以Ford和Fulkerson建立 的网络流理论，与线性规划、动态规划等优化理论和方法

34、柑互渗透，促进了图论対实际问题 的应用。算法重要的算法1、求有向图的强连通分支(Strongerst Connected Component)(1) Kos ar a j u 算法(2) Gabow 算法(3) Tarjan 算法2、求最小生成树(Minimal Spanning Trees)(1) Kruskal 算法(2) Prim 算法3、最小树形图(1)朱水津刘振宏算法4、最短路径问题(1) SSSP (Single-source Shortest Paths)©Dijkstra 算法BelIman-Ford 算法(SPFA 算法)(2) APSP(All-pairs Sho

35、rtest Paths) Floyd-Warshall 算法 Johnson算法5、网络流问题(1) 最人网络流 增广路算法1 .Ford-Fulkerson 篦法2. Edmonds-Karp 算法3加短路径增殖EK-2 (MPLA)4.Dinic 预流推进算法(2) 最小费用流6、图匹配问题(1) 匈牙利算法(2) Hopcroft Karp 算法(3) KuhnMunkres 算法(4) Edmonds' blossom_contraction 算法(有关资料网址：http: www. nocow. cn/index, php/%E5%9B%BE%E8%AE%BA)(1)基本概念

36、无向图一个无向图(undirected graph) G是由一个非空有限集合V(G)和V(G)中某些元素的 无序对集合E(G)构成的二元组，记为G=(V(G),E(G)。其中V(G) = %“,称 为图G的顶点集(vertex set )或节点集(node set ) , V(G)中的每一个元素 出(i = 12,口)称为该图的个顶点(vertex)或廿点(node )； E(G) = 勺冷,称 为图G的边集(edge set), E(G)中的每一个元素q (即V(G)中某两个元素乂,耳的无序From clown studio对)记为岂= (V"Vj)或ek =vy =Vj2 (k

37、= 12,m),被称为该图的一条从v】到Vj的 边(edge)。当边时，称V,V)为边耳的端点，并称V：与V相邻(adjacent)：边乞称为与顶点V,Vj关联(incident )o如果某两条边至少有一个公共端点，则称这两条边在图G中 相邻。边上赋权的无向图称为赋权无向图或无向网络(undirected network)。我们对图和网络不 作严格区分，因为任何图总是可以赋权的有向图一个有向图(directed graph或digraph) G是由一个非空有限集合V和V中某些元素的有序 对集合A构成的二元组，记为G=(V,丹。其中V = %,%,*称为图G的顶点集或节点集， V中的每一个元素v

38、】(i =称为该图的一个顶点或节点；A=a1,a2,- -,am称为图G的弧集(arc set), A中的每一个元素兀(即V中某两个元素vx,Vj的有序对)记为孔=(VpVj)或孔=vy (k = 12,n)，被称为该图的一条从y到v的弧(arc)a肖弧ak = 时，称V为疋的尾(tail),耳为a的头(head),并称弧a*为V】的出弧(outgoing arc), 为V)的入弧 (incoming arc)。对应于每个有向图D,可以在相同顶点集上作一个图G,使得对于D的每条弧，G有一条 有相同端点的边与之相对应。这个图称为D的基础图。反之，给定任意图G,对于它的每 个边，给其端点指定一个顺

39、序，从而确定一条弧，由此得到一个有向图，这样的有向图称 为G的一个定向图。完全图、二分图每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)o n个顶点的完全图 记为Kn。若V (G)=XUY, XnY=<D, |X|Y|hO (这里| X |表示集合X中的元素个数)，X中无相邻顶点对,Y中亦然,则称G为二分图(bipartitegraph)；特别地,若VxwXNywY,则取wE(G),则称G为完全二分图，记成片巩曲。最短路、网络流、二分图1、最短路问题(SPPshortest patli problem)最短路径问题足图论中十分币.要的最优化问题之一，它作为

40、一个经常被用到的基本工只，町 以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点 和阱节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典 型问题之一，可用來解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最 短路问题，我们通常归属为三类单源瑕短路径问题包扌舌起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问 题是已知终结结点，求授短路径的问题。在无向图中该问题与确定起点的问题完全相 同，在有向图中该问题等同

41、于把所有路径方向反转的确定起点的问题。）确定起点终点的最短路径问题即己知起点和终点，求两点之间的最短路径。全局最短路径问题求图中所有的最短路径。算法只要采用Floyed-Warshall算法（这是北洛伊德利用动态 规划（dynamic programming）的原理设计的一个高效算法）。Floyed-Warshall算法用來找出每对点之间的绘短距离。它需要用邻接矩阵来储存边，这个 算法通过考世最佳子路径來得到瑕佳路径。注意单独一条边的路径也不一定是最佳路径。从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有 边相连。对于每一对顶点u和v,看看是否存在一个顶点w使得

42、从u到w再到v比己知的路径 更短。如果是更新它。不可思议的是，只要按排适半，就能得到结果。最短路算法：Dijkstra 算法Dijksti'a 复杂度是 o（nt）,如果用 binary heap 优化可以达到 o（E+N）iogN），用 fibonacci heap可以优化到o（NiogN+E）其基本思想是釆用贪心法，对于每个节点vi,维护估计敲短路长度敲人值，每次取出一个 使得该估计值最小的t,并采用与t相连的边对英余点的估计值进行更新，更新后不再考虑 to在此过程中，估计值单调递减，所以町以得到确切的最短路。Dijkstra 程序：:void DijkstraO ；for(int

43、 i=l;i<=n;i+)；disi = mapl i;II:int k;:for(int i=l;i<n;i+)int tmin = maxint;:for(int j=l:j<=n;j+):if( !usedj && tmin > disj )；tmin 二 dis j;:k = j;: ；usedk = 1;:for(int j=l;j<=n;j+) if ( disk + mapk j < disj):disj = disk + mapk j:I printfdis n);:II:/*求1到N的最短路,disij表示第i个点到第一个点

44、的最短路By Ping*/II«»OB«还有其他算法：FloydWarshal 1 算法Be liman "Ford 算法Johnson 算法实例：某公司在六个城市q,c2，-,c6中有分公司，从c,到勺的直接航程票价记在下述矩阵的(i,j)位宣上。(s表示无直接航路)，请帮助该公司设计一张城市q到其它城市间的票价最便宜的路线图。050co4025105001520CO25CO1501020CO4020100102525CO20100551025CO25550用矩阵玄如“(n为顶点个数)存放备边权的邻接矩阵，行向最pb、index、index.d分别用来

45、存放P标号信息、标号顶点顺序.标号顶点索引、最短通路的值。其中分最pb(i) = ?为第订贞点己标号当第订页点未标号iiidex2(i)存放始点到第i点蚁短通路中第i顶点前一顶点的序号;d(i)存放由始点到第i点最短通路的值。求第一个城市到其它城市的蚁短路径的Matlab程序如K：clear;clc;M=10000;a(l, :) = 0,50,M, 40,25,10;a (2,:) = zeros(1<2)r15r20rMr25;a(3r:) = zeros(lz 3)r10f20rM;a(4,:) = zeros(lz 4)F10r25;a(5r:) = zeros (1,5),55

46、;a(6r:)=zeros (1,6);a=a+a1;pb(1:length(a)=0;pb(1)=1;indexl=l;index2=ones(lrlength(a); d(1:length(a)=M;d(1)=0;temp=l;while sum(pb)<iength (a)tb=find(pb=0);d (tb)=min (d (tb)# d(temp)+a(temp,tb);tmpb=find(d(tb)=min(d(tb);temp=tb(tmpb(1);pb (temp)=1;indexl=indexlf temp;index=indexl (find(d (indexl)=

47、d (temp)-a(temp,indexl); if length (index)>=2index=index(1);endindexZ (temp)=index;endd, indexlrindex?运行结果为：d =03545352510indexl =1 6543index?=1 65611即:d （最短通路的值）03545352510indexl （标号顶点顺序）16543index?（标号顶点索引）1656112、网络流（1）含义的理解网络流（network flows）是图论中的一种理论与方法，研究网络上的一类址优化问题。（2）历史及应用1955年，T. E.哈里斯在研究铁

48、路最大通量时首先提出在一个给定的网络上寻求两点间最 人运输量的问题。1956年，L. R.福特和D.R.常尔克森等人给出了解决这类问题的算法， 从而建立了网络流理论。所谓网络或容屋网络指的是一个连通的赋权有向图D= （V、E、C）, 其中V是该图的顶点集，E是有向边（即弧）集，C是弧上的容量。此外顶点集中包括一个起 点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数, 它一方而受到容量的限制，另一方而除去起点和终点以外，在所有中途点要求保持流入量和 流出量是平衡的。最人流理论是由福特和富尔克森于1956年创立的，他们指出最人流的流值等于绘小割（截 集）的容屋这个重要

49、的事实，并根据这-原理设计了用标号法求最人流的方法，后來又宿人 加以改进，使得求解最人流的方法更加丰富和完善。最人流问题的研究密切了图论和运筹 学，特别是与线性规划的联系，开辟了图论应用的新途径。最人流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用内素是很重要的。 例如在交通运输问题中，往往要求在完成运输任务的前提F，寻求一个使总运输费用般省的 运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成 最短路问题。由此町见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成 功方法。最小费用流（或绘小费用最人流）问题，町以交替使用求解最人流和址短路两

50、种方 法，通过迭代得到解决。目前网络流的理论和应用在不断发展，出现了具有熠益的流、多终端流、毛商品流以及网络 流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、 设备更新以及计算机辅助设计等众多领域。（3）算法的实现Edmonds _Karp 算法建立在Ford-Fulkerson方法上的增广路算法，与一般的Ford-Fulkerson算法不 同的是，它用广度搜索实现对增广路的寻找.以下为代码：int n;long int c128 128:long maxflow int s, int tint p, q, queue ., u, v, pre 128;long

51、 int flow, aug;flow = 0;while truememset pre, 1, sizeof pre 丨；for(queue p = q = _ = s; p <= q; p+u = queue p ;for(v = 0; (v < n) && (pre t) < 0; v+) if (c u v > 0) && (prev < 0)pre v一 = u; queue +q= v;if pre t >= ： breakif (pre t < 0)breakaug = OxTfff;v = u , u=p

52、re ufor u = pre v 二 t ; v if c u v < aug aug = c u_ V-;for u = pre v 二 t ; vcuv -= aug; c v u += aug;flow += aug;return flow:3、二分图(1) 含义的理解二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V 可分割为两个互不相交的子集(A,B),并且图中的每条边(I, j)所关联的两个顶点1和j分 别属于这两个不同的顶点集(iinAjinB),则称图G为一个二分图。2、相关应用作为种数学模型，二分用途是十分有用的，许多问题可以用它來刻

53、划。例如“资源匹配”、 “工作安排”、“人员择偶”等等。而这就需要考虑匹配问题。匹配：给定一个二分图G,在G的一个子图M中，M的边集中的任意两条边都不依 附于同一个顶点，则称M是一个匹配。而二分图最人匹配可以用最人流或者匈牙利算法。最大流在网络流中有介绍。匈牙利算法为：(资料：百度百科)匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理（此定理使用于组合问题中。二部图G中的两部分顶点组成的集介分别为X, Y, Z,=X1, X2, X3.X4,Xm , Y=yl,y2, y3, y4 yn,G 中有一组无公共点的边，一端恰好为组成X的点的充分必要条

54、件足：X中的任意k个点至少与Y中的k个点相邻.（l<k<m）中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增 广路径，它是一种用増广路径求二分图最大匹配的算法。算法的思路：不停的找增广轨，并增加匹配的个数，增广轨顾名思义是指一条町以使匹配数变多的路 径，在匹配问题中,增广轨的表现形式是一条”交错轨，也就是说这条由图的边组成的路 径，它的第一条边是冃前还没有参与匹配的，第二条边参与了匹配,第三条边没有最后 一条边没有参与匹配，并且始点和终点还没有被选择过这样交错进行，显然他有奇数 条边那么对于这样一条路径，我们可以将第一条边改为己匹配，第二条边改为未匹配 以此类推也就是将所冇的边进行反色"，容易发现这样修改以后，匹配仍然是介法的, 但是匹配数增加了一对另外，单独的一条连接两个未匹配点的边显然也是交错轨可 以证明，当不能再找到增广轨时,就得到了一个最人匹配这也就是匈牙