《图论和网络流优化概念.ppt》由会员分享，可在线阅读，更多相关《图论和网络流优化概念.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论和网络流优化概念图论和网络流优化概念华南理工大学数学学院刘深泉教授Konigsberg Konigsberg 七桥问题七桥问题1736年Euler访问Konigsberg时，发现当地市民正从事一项非常有趣的消遣活动。城中有一条名叫Pregel的河流横经其中，在河上建有七座桥,问题是能否作一次散步,走过所有七座桥的，每座桥只能经过一次,且起点与终点是同一地点。七桥问题的数学模型七桥问题的数学模型EulerEuler把每一块陆地考虑成一个点，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示，得到连接两块陆地的桥以线表示，得到如下的图形如下的图形-图图:EulerEuler推出此种走法是不可能
2、的。推出此种走法是不可能的。EulerEuler论点是这样的，除了起点以外，论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块每一次当一个人由一座桥进入一块陆地时，他同时也由另一座桥离开陆地时，他同时也由另一座桥离开此点。所以每行经一点时，计算两此点。所以每行经一点时，计算两座桥，从起点离开的线与最後回到座桥，从起点离开的线与最後回到始点的线亦计算两座桥，每一个陆始点的线亦计算两座桥，每一个陆地与其他陆地连接的桥数必为偶数。地与其他陆地连接的桥数必为偶数。七桥所成之图形中，没有一点含有七桥所成之图形中，没有一点含有偶数条数，任务不可能实现。偶数条数，任务不可能实现。欧拉欧拉数学数学判断
3、原理判断原理对给定的任意一个河道图与任意多座桥，判定可能不可能每座桥恰好走过一次（不一定回到原出发点），并用数学方法给出了3条判定的规则：（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。上述判定规则包含了任一连通无向图是否存在“欧拉路径”和“欧拉回路”的判定条件。根据判定规则（3）可以得出，任一连通无向图存在欧拉回路的充分必要条件是图的所有顶点均有偶数度。赛纳河问题赛纳河问题赛纳河流经巴黎的河中有两个岛，河岸与岛间架设了15座
4、桥,问：(1)能否从某地出发，经过这15座桥各一次后再回到出发点？-就是否存在欧拉回路的问题(2)若不要求回到出发点，能否在一次散步中，穿过所有的桥各一次？-就是否存在欧拉路径的问题A A和和B B是通偶数座桥的地方，是通偶数座桥的地方，C C和和D D是通奇数座桥的地方，满足欧是通奇数座桥的地方，满足欧拉给出的判定规则（拉给出的判定规则（2 2），即如果只有两个地方通奇数座桥，可），即如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到欧拉路径；但不满足规则（以从这两个地方之一出发，找到欧拉路径；但不满足规则（3 3），），即不存在欧拉回路。即不存在欧拉回路。图的定义图的定义有序二元数
5、组有序二元数组 G=G=（V V，E E）称为一个图）称为一个图.其中其中V V称为顶点集，称为顶点集，E E称为边。若每个边对应一个称为边。若每个边对应一个数数F F，称（，称（V V，E E，F F）为一个赋权图）为一个赋权图.如果两点是有序的，则称有向图，否则称无向图如果两点是有序的，则称有向图，否则称无向图.经过经过G G的每条边的迹叫做的每条边的迹叫做G G的的EulerEuler迹迹.闭的闭的EulerEuler迹叫做迹叫做EulerEuler回路回路.含含EulerEuler回路的图叫做回路的图叫做EulerEuler图图.EulerEuler图就是从一顶点出发每边恰通过一次能回
6、到图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回出发点的那种图，即不重复地行遍所有的边再回到出发点到出发点.EulerEuler图图G G是是EulerEuler图的充分必要条件是图的充分必要条件是G G连连通且每顶点皆偶次。通且每顶点皆偶次。弗罗莱（弗罗莱（FleuryFleury）算法）算法任取v0V(G)，令P0=v0；设Pi=v0e1v1e2ei vi已经行遍，按下面方法从中选取ei+1：（1）ei+1与vi相关联；（2）除非无别的边可供行遍，否则ei+1不应该为Gi=G-e1,e2,ei中的桥（所谓桥是一条删除后使连通图不再连通的边）；（3）当（2）
7、不能再进行时，算法停止。可以证明可以证明,当算法停止时所得的简单回路当算法停止时所得的简单回路v0,e1,v1,e2,.em,vm=v0v0,e1,v1,e2,.em,vm=v0为为G G中一条欧拉回路。中一条欧拉回路。HamiltonHamilton图图包含包含G G每个顶点的轨叫做每个顶点的轨叫做HamiltonHamilton轨；轨；闭的闭的HamiltonHamilton轨叫轨叫HamiltonHamilton圈；圈；含含HamiltonHamilton圈的图叫做圈的图叫做HamiltonHamilton图。图。直观地讲，直观地讲，HamiltonHamilton图就是从一顶点图就是从
8、一顶点出发每顶点恰通过一次能回到出发点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶的那种图，即不重复地行遍所有的顶点再回到出发点点再回到出发点。汉密尔顿问题汉密尔顿问题1859年威廉汉密尔顿爵士在给朋友的信中谈到关于十二面体的一个数学游戏，即能否在如图中找到一条回路，使其含有此图中所有结点？-周游世界问题欧拉回路和汉密尔顿回路欧拉回路和汉密尔顿回路欧拉图是每边经过一次.汉密尔顿图是每顶经过一次.最短路问题最短路问题shortest path problemshortest path problemInthefollowingnetworkvariouscostsareass
9、ignedforthepathfromonenodetoanother.Forexample,thecostfromnode2tonode4is6.Theobjectivefunctionconsidersthecosttomovefromeachnodetoanotherfromsourcetodestination.Theconstraintsarebrokenintothreegroups.Theconstraintfortheoriginnodesaysthatyoumustleavenode1andgotonode2or3.Theintermediatenodeconstraints
10、saythatifyouevercomeintoanodeyoumustleavethatnode.Thedestinationnodeissimilartooriginnodeinthatyoumustreachtothisnodefromoneoftheneighboringnode.指派问题指派问题Assignment problemAssignment problemTypically,wehaveagroupofnapplicantsapplyingfornjobs,andthenon-negativecostCijofassigningtheithapplicanttojthjob
11、isknown.Theobjectiveistoassignonejobtoeachapplicantinsuchawayastoachievetheminimumpossibletotalcost.DefinebinaryvariablesXijwithvalueofeither0or1.WhenXij=1,itindicatesthatweshouldassignapplicantitojobj.Otherwise(Xij=0),weshouldnotassignapplicantitojobj.中国邮递员问题中国邮递员问题Chinese postman problemChinese po
12、stman problem管梅谷负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过每条街道至少一次，最后返回邮局）？若图中有欧拉回路，任何一个欧拉回路即为此问题的解。若图中不存在欧拉回路，其中必存在有奇数个边的端点，且这类的端点一定大于等于2个。有些边需要再重复一次，使奇数边的端点变为偶数边的端点。用图来模拟一个镇的街道，标示红色的路口有奇数条路通过。旅行商问题旅行商问题Traveling salesman problemTraveling salesman problemAsalespersonhastovisitcities1,2,.n,andhis/hertr
13、ipbeginsat,andmustendin,HomeCity.LetCijbethecostoftravelingfromcityitocityj,whichisgiven.Theproblemistodetermineanoptimalorderfortravelingthecitiessothatthetotalcostisminimized.运输问题运输问题 Transportation ProblemTransportationmodelsplayanimportantroleinlogisticsandsupplychainmanagementforreducingcostand
14、improvingservice.Therefore,thegoalistofindthemostcosteffectivewaytotransportthegoods.Ashipperhavingmwarehouseswithsupplyaiofgoodsathisithwarehousemustshipgoodstongeographicallydispersedretailcenters,eachwithagivencustomerdemandej,whichmustbemet.Theobjectiveistodeterminetheminimumpossibletransportati
15、oncostsgiventheunitcostoftransportationbetweentheithwarehouseandthejthretailcenterisCij.Maximum Flow ProblemInanetworkwithflowcapacitiesonthearcs,theproblemistodeterminethemaximumpossibleflowfromthesourcetothesinkwhilehonoringthearcflowcapacities.Consideranetworkwithmnodesandnarcswithasinglecommodit
16、yflow.Denotetheflowalongarc(itoj)byXij.Weassociatewitheacharcaflowcapacity,kij.Insuchanetwork,wewishtofindthemaximumtotalflowinthenetwork,F,fromnodeltonodem.Maximum Flow ProblemIntheLPformulation,theobjectiveistomaximizeF.Theamountthatleavestheoriginbyvariousroutes.Foreveryintermediatenode,whatcomes
17、inmustbeequaltowhatgoesout.Insomeroutestheflowcangobothways.Thecapacityamountthatcanbesentinaparticulardirectionisalsoshownontheeachroute.Minimum Cost Flow ProblemAlltheabovenetworkproblemsarespecialcasesoftheminimumcostflowproblem.Likethemaximumflowproblem,itconsidersflowsinnetworkswithcapacities.L
18、iketheshortestpathproblem,itconsidersacostforflowthroughanarc.Likethetransportationproblem,itallowsmultiplesourcesanddestinations.Therefore,alloftheseproblemscanbeseenasspecialcasesoftheminimumcostflowproblem.Theproblemistominimizethetotalcostsubjecttoavailabilityanddemandatsomenodes,andupperboundon
19、flowthrougheacharcCritical Path in Project Plan NetworkThesuccessfulmanagementoflargeprojects,betheyconstruction,transportation,orfinancial,reliesoncarefulschedulingandcoordinatingofvarioustasks.CriticalPathMethod(CPM)attemptstoanalyzeprojectscheduling.Thisallowsforbettercontrolandevaluationofthepro
20、ject.Forexample,wewanttoknowhowlongwilltheprojecttake?Whenwillwebeabletostartaparticulartask?Ifthistaskisnotcompletedontime,willtheentireprojectbedelayed?Whichtasksshouldwespeedup(crash)inordertofinishtheprojectearlier?Givenanetworkofactivities,thefirstproblemofinterestistodeterminethelengthoftimere
21、quiredtocompletetheprojectandthesetofcriticalactivitiesthatcontroltheprojectcompletiontime.Supposethatinagivenprojectactivitynetworktherearemnodes,narcs(i.e.activities)andanestimateddurationtime,Cij,associatedwitheacharc(itoj)inthenetwork.Thebeginningnodeofanarccorrespondstothestartoftheassociatedac
22、tivityandtheendnodetothecompletionofanactivity.TofindtheCriticalPath(CP),definethebinaryvariablesXij,whereXij=1iftheactivityijisontheCPandXij=0otherwise.Thelengthofthepathisthesumofthedurationoftheactivitiesonthepath.Thelengthofthelongestpathistheshortesttimeneededtocompletetheproject.Formally,theCP
23、problemistofindthelongestpathfromnode1tonodem.公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，如何决定在哪些城市间修建高速公路，使得总成本最小？共同的两个特点寻求某种意义下的最优方案，数学上称为图论最优化或优化问题（optimization）.易于用图形直观地描述，数学上的结构称为网络（network）.图和网络相关的最优化问题就是网络最优化问题（netwok optimization）.网络优化
24、问题是以网络上的流（flow）为研究的对象，称为网络流（network flows）.GraphtheoryInmathematicsandcomputerscience,graph theoryisthestudyofgraphs,whicharemathematicalstructuresusedtomodelpairwiserelationsbetweenobjects.Agraphinthiscontextismadeupofverticesornodesandlinescallededgesthatconnectthem.Agraphmaybeundirected,meaningthatthereisnodistinctionbetweenthetwoverticesassociatedwitheachedge,oritsedgesmaybedirectedfromonevertextoanother;seegraph(mathematics)formoredetaileddefinitionsandforothervariationsinthetypesofgraphthatarecommonlyconsidered.Graphsareoneoftheprimeobjectsofstudyindiscretemathematics.