运筹学第十章图与网络优化

1第十章图与网络优化(GraphTheoryandNetworkAnalysis)1图的基本概念2树及最小支撑树3最短路问题4网络最大流问题5最小费用最大流问题6中国邮递员问题2图论的起源和发展•1736年，Euler哥尼斯堡七桥问题(KönigsbergBridgeProblem)BACDABCD一笔画问题3•1847年，kirchhoff，电网络，“树”；•1852年，《四色猜想》；•1964年，华罗庚，《统筹方法平话》。•1857年，Cogley，同分异构，“树”；•1956年，杜邦公司，CPM，关键路线法；•1958年，美国海军部，PERT，计划评审技术；•1962年，管梅谷，《中国邮路问题》；4第一节图的基本概念一、几个例子例1是北京、上海等十个城市间的铁路交通图。与此类似的还有电话线分布图、煤气管道图、航空路线图等。北京天津济南青岛武汉南京上海郑州连云港徐州5例2分别用点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，且这条线不过其他点。如下图所示：v1v2v3v4v5可知各队之间的比赛情况如下：甲——乙、丙、丁、戊乙——甲、丙丙——甲、乙、丁丁——甲、丙、戊戊——甲、丁6例3“染色问题”储存8种化学药品，其中某些药品不能存放在同一个库房里。用v1,v2,…,v8分别代表这8种药品。规定若两种药品不能存放在一起，则其相应的点之间联一条线。如下图所示：v1v2v3v4v5v6v7v8可知需要4个库房，其中一个答案是：{v1}{v2,v4,v7}{v3,v5}{v6,v8}还有其他的答案。7二、基本概念•有向图由点及弧所构成的图，记为D=(V,A)，V,A分别是D的点集合和弧集合。•无向图由点及边所构成的图。记为G=(V,E),V，E分别是G的点集合和边集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e3e4e5a6e68•边两点之间不带箭头的联线。如e3v1v4a3•弧两点之间带箭头的联线。如a3v1v4e3•端点及关联边若边e=[u,v]∈E，则称u,v为e的端点，也称u,v是相邻的，称e是点u(及点v)的关联边。如：v1,v4为e3的端点，v1,v4是相邻的，e3是v1（v4）的关联边。9•环若在图G中，某个边的两个端点相同，则称e是环。如e7v1v2v3v4e1e2e3e4e5e6e7•多重边若两个点之间有多于一条的边，称这些边为多重边。如e1,e2•简单图一个无环，无多重边的图。•多重图一个无环、但允许有多重边的图。10•点v的次以点vi为端点边的个数，记为dG(vi)或d(vi)。v1v2v3v4e1e2e3e4e5e6e7如d(v4)=5d(v2)=4v5•悬挂点次为1的点，如v5•悬挂边悬挂点的关联边，如e8e8•孤立点次为0的点•偶点次为偶数的点，如v2•奇点次为奇数的点,如v511•链•中间点•初等链•圈•初等圈•简单圈v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9在上图中,(v1,v2,v3,v4,v5,v3,v6,v7)是一条链,但不是初等链在该链中,v2,v3,v4,v5,v3,v6是中间点(v1,v2,v3,v6,v7)是一条初等链(v1,v2,v3,v4,v1)是一个初等圈(v4,v1,v2,v3,v5,v7,v6,v3,v4)是一个简单圈12•连通图图G中，若任何两个点之间，至少有一条链，称为连通图。否则称为不连通图。•连通分图(分图)若G是不连通图，则它的每个连通的部分称为连通分图。v1v2v3v4e1e2e3e4e5e6v5v6e7如左图就是个不连通图，它是由两个连通分图构成的。13•支撑子图给定一个图G=(V,E)，如果图G’=(V’,E’)，使V’=V及E’E，则称G’是G的一个支撑子图。v1v2v3v4(G)v1v2v3v4(G’)•基础图给定一个有向图D=(V,A)，从D中去掉所有弧上的箭头，所得到的无向图称为基础图。记之为G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)14v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7•路•初等路•回路v5是一个回路。在上图中),,,,,,,,(,385645233vavavavav。的路。也是一条初等路到是从616744321),,,,,,(vvvavavav•简单有向图•多重有向图15•权与网络在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。Avvji),(jiw16对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。),(jivvjiwEvvEvvwajijijiji),(0),(nnjiaA)(nnjiaA)(EvvEvvajijiji),(0),(1设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。•图的矩阵表示17654321654321010101101001010111101010001101111010vvvvvvvvvvvvB权矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437654321654321030303302004020576305020007204346040vvvvvvvvvvvvA图的矩阵表示18•定理1图G=(V,E)中，所有点的次之和是边数的两倍，即•定理2任一图中奇点的个数为偶数。三、基本定理qvdVv2)(19第二节树一、定义例1在五个城市之间架设电话线，要求任两个城市之间都可以相互通话（允许通过其他城市），并且电话线的根数最少。v1v5v2v3v4用v1,v2,v3,v4,v5代表五个城市,如果在某两个城市之间架设电话线,则在相应的两点之间联一条边,这样一个电话线网就可以用一个图来表示。显然,这个图必须是连通的,而且是不含圈的连通图。如右图所示。树的定义：一个无圈的连通图。20例2某工厂的组织机构如下图所示厂长行政办公室生产办公室生产计划科技术科设计组工艺组供销科财务科行政科车间铸造工段锻压工段二车间三车间四车间该厂的组织机构图就是一个树。21例3树图倒置的树，根(root)在上，叶(leaf)在下C1C2C3C4根叶22定理1设图G=(V,E)是一个树，p(G)≥2，则G中至少有两个悬挂点。二、性质也是悬挂点。为悬挂点。同理，所以与假设矛盾则存在链不在上述链中若与条件矛盾含圈则在上述链中若中的一条边。为使得则存在即不是悬挂点设时当命题成立。时即时当中边数最多的一条链。为设反证法kkssssskvvvvvvvGvGvvvvdvGpGpkGvvv12111121.),,,,,(,;,,),(,,2)(,,2)(,2)(,2),,,(证明23定理2图G=(V,E)是一个树的充分必要条件是G中不含圈，且恰有p-1条边。命题也成立。所以，，，且个点的树，由题设是因为记为中含有悬挂点时，当条边。时，命题成立，即含有设显然成立。时用数学归纳法。当先证必要性。即要证明,1)(1)()()(1)(.,11,2.1)(11111pnGqGqvGqnvGpnvGqnvGvGnpnnpppGq证明.,2)()(.1)(,,),,2,1(.,,,121矛盾则由必要性知为树则不含圈而的连通分图为不连通，则用反证法。假设是连通的。再证充分性。即要证明pspGqGqpGqGsiGGGGGGGsiiiiiiS24定理3图G=(V,E)是一个树的充分必要条件是G是连通图，并且q(G)=p(G)-1。证明由定理2，必要性显然。矛盾。这与从而有有否则，对每个点必有悬挂点。时，则当）时，结论也成立。（设时，结论显然成立。当法。中不含圈。用数学归纳再证充分性。只要证1)()(),()(21)(,2)(,1)(2)(2,1)()(1GpGqGpvdGqvdvGnGpnnGpGpGGpiiii也不含圈。不含圈，于是因此由归纳假设知由于也是连通的。的一个悬挂点，则图是设GvGvGpGpGqvGqvGGv11111,1)(2)(1)()(25定理4图G是树的充分必要条件是任意两个顶点之间恰有一条链。证明由树的定义，必要性显然。因为任两个顶点间恰有一条链，显然G是连通的。如果G中含有圈的话，则其中至少有两个顶点间有两条链，这与题设矛盾。充分性得证。推论：•从一个树中去掉一条边，则余下的图是不连通的。•在树中不相邻的两个点间添上一条边，则恰好得到一个圈。26三、图的支撑树定义：设图T=(V,E’)是图G的支撑子图，如果图T=(V,E’)是一个树，则称T是G的一个支撑树。定理：图G有支撑树的充分必要条件是图G是连通的。证明必要性显然。再证充分性。设图G是连通图，若G不含圈，则G本身是一个树，从而G是它自身的一个支撑树。如果G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk,它不含圈，于是Gk是G的一个支撑树。27支撑树的求解方法•破圈法例用破圈法求解图的一个支撑树v1v2v3v4v5e1e2e3e4e5e6e7e8这就得到了该图的一个支撑树。28•避圈法v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9这就得到了该图的一个支撑树。29)(min)(*TwTwT四、最小支撑树定义1给图G=(V,E)，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图G为赋权图，wij称为边[vi,vj]上的权。1.定义定义2如果T=(V,E’)是G的一个支撑树，称E’中所有边的权之和为支撑树T的权，记为w(T)，即TvvijjiwTw),()(最小支撑树如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树),即302.最小支撑树的求法方法一避圈法开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。v1v2v3v4v5v6651572344这就得到了该图的一个最小支撑树。31方法二破圈法任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。v1v2v3v4v5v6651572344这就得到了该图的一个最小支撑树。32第三节最短路问题一、最短路问题的提出v1v2v3v4v5v6v7v8v9132216610410423236例左图为单行线交通网，弧旁数字表示通过这条单行线所需要的费用。求从v1出发到v8总费用最小的路线。(1)有很多条路线，与图论中的路一一对应；(2)一条路线的费用就是相应的路中各条弧的费用之和。如上图所示的路线为最短路。33在图论中，最短路问题可归结为：(1)给定一个赋权有向图D＝(V,A)及W(a)=Wij；(2)给定D中两个顶点vs、vt，P是D中从vs到vt的一条路；(3)定义路P的权为P中所有弧的权之和，W(P)＝Wij；(4)求一条权最小的路P0:W(P0)=minW(P)34二、求解方法基本原理：最短路问题的特性最短路线上的任一中间点到终（起）点的路线一定是该中间点到终（起）点的所有路线中最短的路线。若求起点A到任一点G的最短路线，可先求A到G点的相邻前点的最短距离，在此基础上求出A到G点的最短距离。这样，最终求出起点到终点的最短距离。狄克斯屈拉