05：图与网络模型01

第五讲图与网络分析1.图与网络的基本概念2.最短路问题3.最小树问题4.最大流问题5.最小费用最大流问题本章内容例：七桥问题ABCD问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。问题：能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。例：中国邮路问题一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。问题：他如何走？点：路口；边：两路口之间道路，第i条道路长ei。问题：求一个圈，过每边至少一次，并使圈的长度最短。例：四色猜想能否用四种颜色给地图染色，使相邻的国家有不同的颜色。点：国家；边：两个国家有公共边界。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。例：有甲、乙、丙、丁、戊五个球队，各队之间比赛情况如表：甲乙丙丁戊甲×胜负胜胜乙负×胜丙胜负×胜丁负负×负戊负胜×点：球队；连线：两个球队之间比赛过，如甲胜乙，用v1v2表示。v1v2v3v4v51.图的基本概念点：研究对象（陆地、路口、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、路口之间道路、两国边界、两球队比赛及结果)。对称关系：桥、道路、边界；用不带箭头的连线表示，称为边。非对称关系：甲队胜乙队，用带箭头的连线表示，称为弧。图：点及边（或弧）组成。•图的基本概念•链、路、连通图的概念•网络的概念1.1图的概念如果一个图G是由点及边所构成的,则称之为无向图(简称图),记为G=(V，E)。其中V={vi}和E={ek}分别是G的点集和边集。一条联结点vi，vj∈V的边记为ek=(vi,vj)或(vj,vi).为区别起见,把两点之间的不带箭头的连线称为边,带箭头的连线称为弧。顶点、端点、节点图：点及边（或弧）组成。如果一个图G是由点及弧所构成的,则称之为有向图,记为D=(V，A)。其中V和A分别是G的点集和弧集。一条方向是从点vi，指向vj的弧记为(vi,vj)。无向图：由点及边构成，边[vi，vj]有向图：由点及弧构成，弧（vi，vj）1.2链、路、连通图的概念(1)链:在无向图G中的一个点、边交错序列则这个点边交错序列称为链。圈：首尾相连的链称为圈。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9，，满足)(),,,,,,,(1ttt112211iiikikikiiiiivvevevevev如（v3,e2,v5,e6,v6,e5,v3）如（v1，e1，v3，e2，v5，e6，v6，e5，v3，e4，v4）无向图中，链与路的概念是一致的。有向图中，路一定是链，但链不一定是路。当链上弧的方向一致时，是路。（2）路：在有向图D中,一个点弧序列｛vi1,ei1,vi2,…,vin｝满足eit=（vit,vit+1），vit→vit+1则称该序列为一条vi1到vin的路。回路：首尾相连的路叫回路。（3）连通图：任意两点之间可由一条链直接链起来相通的图叫连通图。否则，称为非连通图。若对图G=（V，E）中每条边[vi，vj]赋予一个数wij，则称wij为边[vi，vj]的权，并称图G为网络（或赋权图）。网络：无向网络、有向网络。1.3网络的概念2.最短路问题一、最短路问题例下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从v1到v8：P1=（v1，v2，v5，v8）费用6+1+6=13P2=（v1，v3，v4，v6，v7，v8）费用3+2+10+2+4=21P3=……从v1到v8的旅行路线从v1到v8的路。旅行路线总费用路上所有弧权之和。v2v523464v3v1v4v6121061210v8v9v72363最短路问题对一个赋权的有向(无向)图D中的指定的两个点vs，vt，找到一条从vs到vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从vs到vt的最短路。这条路上所有弧的权数的总和，称之为从vs到vt的距离。二、Dijkstra算法Dijkstra算法,适用于每条弧的赋权数wij≥0的情况。事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。最短路的子路也是最短路。Dijkstra算法的基本思想：从vs出发，逐步地向外探寻最短路。基本步骤:1.给起点v1以标号(0,s)表示从v1到v1的距离为0，v1为起点。2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合{(vi,vj)︱vi∈I,vj∈J}，这里这个弧的集合是指所有从已标号的点到未标号的点的弧的集合。3.如果上述弧的集合是空集，则计算结束。如果vt已标号(lt,kt)，则vs到vt的距离即为lt，从而vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。如果上述的弧的集合不是空集，转下一步。4.对上述弧的集合中的每一条弧，计算sij=li+cij在所有的中sij，找到其值为最小的弧，不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c），返回步骤2。图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s1,1此时,I={v1}，J={v2，v3，…，v9},弧的集合{(vi,vj)︱vi∈I,vj∈J}={(v1,v2)，(v1,v3)，(v1,v4)}有s12=l1+c12=0+6＝6，s13=l1+c13=0+3＝3，s14=l1+c14=0+1＝1，Min(s12,s13,s14)=s14=1v1图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s1,13,1此时,I={v1，v4}，J={v2，v3,v5,v6,v7,v8,v9},弧的集合{(vi,vj)︱vi∈I,vj∈J}={(v1,v2)，(v1,v3)，(v4,v6)}有s12=l1+c12=0+6＝6，s13=l1+c13=0+3＝3，s46=l4+c46=1+10＝11，Min(s12,s13,s46)=s13=35,3图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s1,13,1此时,I={v1,v4,v3}，J={v2,v5,v6,v7,v8,v9},弧的集合{(vi,vj)︱vi∈I,vj∈J}={(v1,v2)，(v3,v2)，(v4,v6)}有s12=l1+c12=0+6＝6，s32=l3+c32=3+2＝5，s46=l4+c46=1+10＝11，Min(s12,s32,s46)=s32=51,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s1,16,23,15,3此时,I={v1,v4,v3,v2}，J={v5,v6,v7,v8,v9},弧的集合{(vi,vj)︱vi∈I,vj∈J}={(v2,v5)，(v4,v6)}有s25=l2+c25=5+1＝6s46=l4+c46=1+10＝11Min(s25,s46)=s25=61,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s9,51,16,23,15,3此时,I={v1,v4,v3,v2,v5}，J={v6,v7,v8,v9},弧的集合{(vi,vj)︱vi∈I,vj∈J}={(v4,v6),(v5,v6),(v5,v7),(v5,v8)}有s46=l4+c46=1+10＝11s56=l5+c56=6+4＝10s57=l5+c57=6+3＝9s58=l5+c58=6+6＝12Min(s46,s56s57,s58)=s57=95,3图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s9,510,51,13,16,2此时,I={v1,v4,v3,v2,v5,v7}，J={v6,v8,v9},弧的集合{(vi,vj)︱vi∈I,vj∈J}={(v4,v6),(v5,v6),(v5,v8),(v7,v8)}有s46=l4+c46=1+10＝11s56=l5+c56=6+4＝10s58=l5+c58=6+6＝12s78=l7+c78=9+4＝13Min(s46,s56,s58,s78,)=s56=105,3图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s9,510,51,112,53,16,2此时,I={v1,v4,v3,v2,v5,v6,v7}，J={v8,v9},弧的集合{(vi,vj)︱vi∈I,vj∈J}={(v7,v8),(v5,v8)}有s58=l5+c58=6+6＝12s78=l7+c78=9+4＝13Min(s58,s78,)=s58=125,3图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s9,510,51,112,53,16,2此时,I={v1,v4,v3,v2,v5,v6,v7,v8}，J={v9},弧的集合{(vi,vj)︱vi∈I,vj∈J}=，计算结束。此时J={v9}，也即v9还未标号，说明从v1到v9没有有向路。5,3图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,s11,510,51,112,53,16,2从最终图中各点vi的标号可得到v1到vi的距离及v1到vi的最短路径.。如v1到v8的距离为12，v1到v8的最短路径v1→v3→v2→v5→v8问题：①本例中，v1到v9的最短路？②无向网络③负权弧时。wijvivjwijwijvjvi无向网络中，最短路→最短链。v1v2v312-3Dijkstra算法失效4v5v23152v3v1v41046174v765v613,3P209例2图上标号法:0,s14,310,122,616,518,5181717233123413022594130221616P213例3图上标号法:v1v2v3v4v5v63.最小树问题3.1树的概念无圈的连通图称为树。用T表示。如：有线通讯网、交通运输网，在保证节点连通的条件下，边数最少的线路图必然是树。-----------最小连接问题。一些行政管理机构和军队的建制也常用树来表示相互隶属关系；图书分类、会计科目、决策过程等也都可以画成树图。3.2图的生成树定义2设EE，则图T=[V，E]是图G=（V，E）的生成子图，如果T是一个树，则称T是G的一个生成树。v1v3v2v4v5v6（a）v3v1v2v4v5v6（b）（b）是（a）的一个生成树。也称为支撑树。（一）破圈法（二）避圈法在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3。一般设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5求最小生成树的问题，就是在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。2345674v3v1v2v4v5v6152345674v3v1v2v4v5v615234564v3v1v2v4v5v615234564v3v1v2v4v5v61523454v3v1v2v4v5v61523454v3v1v2v4v5v6152344v3v1v2v4v5v6152344v3v1v2v4v5v615234v3v1v2v4v5v615作业•P2311•P2323