图论和网络流优化概念.ppt

图论和网络流优化概念,华南理工大学数学学院刘深泉教授,Konigsberg七桥问题,1736年Euler访问Konigsberg时，发现当地市民正从事一项非常有趣的消遣活动。城中有一条名叫Pregel的河流横经其中，在河上建有七座桥,问题是能否作一次散步,走过所有七座桥的，每座桥只能经过一次,且起点与终点是同一地点。,七桥问题的数学模型,Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示，得到如下的图形-图:Euler推出此种走法是不可能的。Euler论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地时，他同时也由另一座桥离开此点。所以每行经一点时，计算两座桥，从起点离开的线与最後回到始点的线亦计算两座桥，每一个陆地与其他陆地连接的桥数必为偶数。七桥所成之图形中，没有一点含有偶数条数，任务不可能实现。,欧拉数学判断原理,对给定的任意一个河道图与任意多座桥，判定可能不可能每座桥恰好走过一次（不一定回到原出发点），并用数学方法给出了3条判定的规则：（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。上述判定规则包含了任一连通无向图是否存在“欧拉路径”和“欧拉回路”的判定条件。根据判定规则（3）可以得出，任一连通无向图存在欧拉回路的充分必要条件是图的所有顶点均有偶数度。,赛纳河问题,赛纳河流经巴黎的河中有两个岛，河岸与岛间架设了15座桥,问：(1)能否从某地出发，经过这15座桥各一次后再回到出发点？-就是否存在欧拉回路的问题(2)若不要求回到出发点，能否在一次散步中，穿过所有的桥各一次？-就是否存在欧拉路径的问题A和B是通偶数座桥的地方，C和D是通奇数座桥的地方，满足欧拉给出的判定规则（2），即如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到欧拉路径；但不满足规则（3），即不存在欧拉回路。,图的定义,有序二元数组G=（V，E）称为一个图.其中V称为顶点集，E称为边。若每个边对应一个数F，称（V，E，F）为一个赋权图.如果两点是有序的，则称有向图，否则称无向图.经过G的每条边的迹叫做G的Euler迹.闭的Euler迹叫做Euler回路.含Euler回路的图叫做Euler图.Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点.,Euler图,G是Euler图的充分必要条件是G连通且每顶点皆偶次。,弗罗莱（Fleury）算法,任取v0V(G)，令P0=v0；设Pi=v0e1v1e2eivi已经行遍，按下面方法从中选取ei+1：（1）ei+1与vi相关联；（2）除非无别的边可供行遍，否则ei+1不应该为Gi=G-e1,e2,ei中的桥（所谓桥是一条删除后使连通图不再连通的边）；（3）当（2）不能再进行时，算法停止。可以证明,当算法停止时所得的简单回路v0,e1,v1,e2,.em,vm=v0为G中一条欧拉回路。,Hamilton图,包含G每个顶点的轨叫做Hamilton轨；闭的Hamilton轨叫Hamilton圈；含Hamilton圈的图叫做Hamilton图。直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。,汉密尔顿问题,1859年威廉汉密尔顿爵士在给朋友的信中谈到关于十二面体的一个数学游戏，即能否在如图中找到一条回路，使其含有此图中所有结点？-周游世界问题,欧拉回路和汉密尔顿回路,欧拉图是每边经过一次.汉密尔顿图是每顶经过一次.http:/home.ubalt.edu/ntsbarsh/opre640a/partIII.htm,最短路问题shortestpathproblem,Inthefollowingnetworkvariouscostsareassignedforthepathfromonenodetoanother.Forexample,thecostfromnode2tonode4is6.Theobjectivefunctionconsidersthecosttomovefromeachnodetoanotherfromsourcetodestination.Theconstraintsarebrokenintothreegroups.Theconstraintfortheoriginnodesaysthatyoumustleavenode1andgotonode2or3.Theintermediatenodeconstraintssaythatifyouevercomeintoanodeyoumustleavethatnode.Thedestinationnodeissimilartooriginnodeinthatyoumustreachtothisnodefromoneoftheneighboringnode.,指派问题Assignmentproblem,Typically,wehaveagroupofnapplicantsapplyingfornjobs,andthenon-negativecostCijofassigningtheithapplicanttojthjobisknown.Theobjectiveistoassignonejobtoeachapplicantinsuchawayastoachievetheminimumpossibletotalcost.DefinebinaryvariablesXijwithvalueofeither0or1.WhenXij=1,itindicatesthatweshouldassignapplicantitojobj.Otherwise(Xij=0),weshouldnotassignapplicantitojobj.,中国邮递员问题Chinesepostmanproblem,管梅谷负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过每条街道至少一次，最后返回邮局）？若图中有欧拉回路，任何一个欧拉回路即为此问题的解。若图中不存在欧拉回路，其中必存在有奇数个边的端点，且这类的端点一定大于等于2个。有些边需要再重复一次，使奇数边的端点变为偶数边的端点。,用图来模拟一个镇的街道，标示红色的路口有奇数条路通过。,旅行商问题Travelingsalesmanproblem,Asalespersonhastovisitcities1,2,.n,andhis/hertripbeginsat,andmustendin,HomeCity.LetCijbethecostoftravelingfromcityitocityj,whichisgiven.Theproblemistodetermineanoptimalorderfortravelingthecitiessothatthetotalcostisminimized.,运输问题TransportationProblem,Transportationmodelsplayanimportantroleinlogisticsandsupplychainmanagementforreducingcostandimprovingservice.Therefore,thegoalistofindthemostcosteffectivewaytotransportthegoods.Ashipperhavingmwarehouseswithsupplyaiofgoodsathisithwarehousemustshipgoodstongeographicallydispersedretailcenters,eachwithagivencustomerdemandej,whichmustbemet.TheobjectiveistodeterminetheminimumpossibletransportationcostsgiventheunitcostoftransportationbetweentheithwarehouseandthejthretailcenterisCij.,MaximumFlowProblem,Inanetworkwithflowcapacitiesonthearcs,theproblemistodeterminethemaximumpossibleflowfromthesourcetothesinkwhilehonoringthearcflowcapacities.Consideranetworkwithmnodesandnarcswithasinglecommodityflow.Denotetheflowalongarc(itoj)byXij.Weassociatewitheacharcaflowcapacity,kij.Insuchanetwork,wewishtofindthemaximumtotalflowinthenetwork,F,fromnodeltonodem.,MaximumFlowProblem,IntheLPformulation,theobjectiveistomaximizeF.Theamountthatleavestheoriginbyvariousroutes.Foreveryintermediatenode,whatcomesinmustbeequaltowhatgoesout.Insomeroutestheflowcangobothways.Thecapacityamountthatcanbesentinaparticulardirectionisalsoshownontheeachroute.,MinimumCostFlowProblem,Alltheabovenetworkproblemsarespecialcasesoftheminimumcostflowproblem.Likethemaximumflowproblem,itconsidersflowsinnetworkswithcapacities.Liketheshortestpathproblem,itconsidersacostforflowthroughanarc.Likethetransportationproblem,itallowsmultiplesourcesanddestinations.Therefore,alloftheseproblemscanbeseenasspecialcasesoftheminimumcostflowproblem.Theproblemistominimizethetotalcostsubjecttoavailabilityanddemandatsomenodes,andupperboundonflowthrougheacharc,CriticalPathinProjectPlanNetwork,Thesuccessfulmanagementoflargeprojects,betheyconstruction,transportation,orfinancial,reliesoncarefulschedulingandcoordinatingofvarioustasks.CriticalPathMethod(CPM)attemptstoanalyzeprojectscheduling.Thisallowsforbettercontrolandevaluationoftheproject.Forexample,wewanttoknowhowlongwilltheprojecttake?Whenwillwebeabletostartaparticulartask?Ifthistaskisnotcompletedontime,willtheentireprojectbedelayed?Whichtasksshouldwespeedup(crash)inordertofinishtheprojectearlier?,Givenanetworkofactivities,thefirstproblemofinterestistodeterminethelengthoftimerequiredtocompletetheprojectandthesetofcriticalactivitiesthatcontroltheprojectcompletiontime.Supposethatinagivenprojectactivitynetworktherearemnodes,narcs(i.e.activities)andanestimateddurationtime,Cij,associatedwitheacharc(itoj)inthenetwork.Thebeginningnodeofanarccorrespondstothestartoftheassociatedactivityandtheendnodetothecompletionofanactivity.TofindtheCriticalPath(CP),definethebinaryvariablesXij,whereXij=1iftheactivityijisontheCPandXij=0otherwise.Thelengthofthepathisthesumofthedurationoftheactivitiesonthepath.Thelengthofthelongestpathistheshortesttimeneededtocompletetheproject.Formally,theCPproblemistofindthelongestpathfromnode1tonodem.,公路连接问题,某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，如何决定在哪些城市间修建高速公路，使得总成本最小？,共同的两个特点,寻求某种意义下的最优方案，数学上称为图论最优化或优化问题（optimization）.易于用图形直观地描述，数学上的结构称为网络（network）.图和网络相关的最优化问题就是网络最优化问题（netwokoptimization）.网络优化问题是以网络上的流（flow）为研究的对象，称为网络流（networkflows）.,Graphtheory,Inmathematicsandcomputerscience,graphtheoryisthestudyofgraphs,whicharemathematicalstructuresusedtomodelpairwiserelationsbetweenobjects.Agraphinthiscontextismadeupofverticesornodesandlinescallededgesthatconnectthem.Agraphmaybeundirected,meaningthatthereisnodistinctionbetweenthetwoverticesassociatedwitheachedge,oritsedgesmaybedirectedfromonevertextoanother;seegraph(mathematics)formoredetaileddefinitionsandforothervariationsinthetypesofgraphthatarecommonlyconsidered.Graphsareoneoftheprimeobjectsofstudyindiscretemathematics.,