运筹学第三版之第六章图与网络分析

图与网络分析(GraphTheoryandNetworkAnalysis)图与网络的基本知识最短路问题树及最小树问题最大流问题最小费用最大流问题BDACABCD哥尼斯堡“七桥”难题一笔画问题问题：一个游者怎样才能一次连续走过这七座桥且每座桥只走一次，回到原出发点。欧拉用A,B,C,D四点表示河的两岸和小岛，用两点间的联线表示桥。七桥问题变为：从A,B,C,D任一点出发，能否通过每条边一次且仅一次，再回到该点?一、图与网络的基本知识（一）、图与网络的基本概念EADCBv1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10图1,,(,),uvVuvEuv两个点属于如果边属于，则称两点相邻.,,)uvuv称为边(的端点{}jVvV一个图是由点集和中元素的无序对的一个集合{},(,),kjEeGVEVv构成的二元组记为其中中的元素,,kVGEeE叫做顶点表示图的顶点集合,中的元素叫做边表示.G图的边集合123456,,,,,Vvvvvvv例12345678910,,,,,,,,,Eeeeeeeeeee112212323{,},{,},{,},evvevvevv434513635,,,,,evvevvevv735856966,,,,,,evvevvevv1016,evv,,.VEG当为有限集合时称为有限图否则为无限图()||,()||mGEGnGVG用表示图中的边数表示图的顶点.个数v4v6v1v2v3v5图2(,),(,),ijijvvEvv对于任一条边属于如果边端点无序则它是,.G无向边此时图称为无向图(,),,ijijvvvv如果边端点有序则它表示以为始点为终点的,.G有向边(或称为弧)此时图称为有向图123456,,,,,Vvvvvvv13212325{(,),(,),(,),(,),Evvvvvvvv35455456(,),(,),(,),(,)}vvvvvvvv,,,,ijijeeEuee两条边属于如果它们有一个公共端点则称相邻.,.ijeeu边称为的关联边4.一条边的两个端点如果相同,称此边为环。6.不含环和多重边的图称为简单图，含有多重边的图称为多重图。8.有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。5.两个点之间多于一条边的，称为多重边.7.每一对顶点间都有边相连的无向简单图称为完全图。有n个顶点的无向完全图记作Kn,deg(),()vvvdv10.以点为端点的边数叫做点的次记作简记为9.(,),,GVEVXY图的点集可以分为两个非空子集即,,XYVXYE使得中每条边的两个端点必有一个,,(),XYG端点属于另一个端点属于则称为二部图偶图(,,)GXYE有时记作1v3v5v2v4v6v1v2v3v4v1v2v3v4v次为零的点称为弧立点，次为1的点称为悬挂点。连结悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。定理2任何图中，次为奇数的顶点必为偶数个。有向图中,所有顶点的入次之和等于所有顶点的出次之和定理1任何图中，顶点次数的总和等于边数的2倍。,,(),iiivvdv有向图中以为始点的边数称为点的出次用表示,(),iiivvdv以为终点的边数称为点的入次用表示.iv点的出次与入次之和就是该点的次,,由于每条边必与两个顶点关联在计算点的次时每条边2,.均被计算了两次所以顶点次数的总和等于边数的倍1212(),VVGVVV设和分别为图中奇点和偶点的集合由1212()()()vVvVvVdvdvdvm定理知22,(),.vVmdv由于为偶数而是若干个偶数之和也是偶数11(),||.vVdvV所以必为偶数即是偶数v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图(,),,,GVEEEVVE图若是的子集是的子集且中的边仅,(,).VGVEG与中的顶点相关联则称是的一个子图,,().VVGG特别地若则称为的生成子图支撑子图(,),GVEG无向图若图中某些点与边的交替序列可以排成0112111(,,,,...,,,),(,)(,...,)kkktttiiiiiiiiiivevevevevvtk的形式且0kiivvk则称这个点边序列为连接与的一条链，链长为点边列中没有重复的点和重复边者为初等链。00,,kkiiiiGvvvv无向图中，连结与的一条链当与是同一个点时称此链为圈.圈中既无重复点也无重复边者为初等圈.,(,)(,),GVEDVA在实际应用中给定一个图或有向图1,(),,Vv在中指定两个点一个称为始点或发点记作一个称为(),,.nv终点或收点记作其余的点称为中间点对每一条弧(,),,.ijijvvAw对应一个数称为弧上的权通常把这种.赋权的图称为网络e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10图3()().当链圈上的边方向相同时，称为道路回路一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。v4v6v1v2v3v5e2e1e3e4e5e6e7e8e9e10图411635546{,,,,,,}Svevevev图4中，为一条道路.2495104{,,,,}Svevev为一个回路.11233547584423,{,,,,,,,,,,,,}Svevevevevevev图中1112335475{,,,,,,,,}Svevevevev223354758442{,,,,,,,,,,}Svevevevevev31123321{,,,,,,}Svevevev(二)、图的矩阵表示()(,),(,),ijijGVEvvw网络赋权图其边有权构造矩阵(),:ijnnAa其中0(,)ijijijwvvEa其他.AG称矩阵为网络的权矩阵(,),||,(),:ijnnGVEVnAa对于图构造一个矩阵其中10(,)ijijvvEa其他.AG则称矩阵为图的邻接矩阵654321654321010101101001010111101010001101111010vvvvvvvvvvvvB例权矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437654321654321030303302004020576305020007204346040vvvvvvvvvvvvA二、树及最小树问题已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。v1v2v3v4v5v6(,),,,.TVEVnEm则关于树的下列说法是等价的1().T是一个树21(),.Tmn无圈且31(),.Tmn连通且4(),T无圈但每加一新边即得唯一一个圈.5(),.T连通但任舍去一边就不连通6(),.T中任意两点有唯一链相连1、连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分支点。12()()证明,.TTT由于是树由定义知是连通的并且无圈只需证明中的1mmn边数等于顶点个数减1，即2.,,nT用归纳法当时由于是树所以两点间显然有且仅有1,mn一条边满足112,nkkTk归纳假设时命题成立即有个顶点时有.,,nkTk条边当时因为连通无圈个顶点中至少有一个点次1.,,(,).uuuvu为设此点为即为悬挂点设连结点的悬挂边为(,),,TvuuTTT从中去掉边及点不会影响的连通性得图为树12,,(,)kkvuu只有个顶点所以有条边再把，加上去,可知1.Tkk当有个顶点时有条边23()().T只需证明是连通图2.,(),Tlli反证法设不连通可以分为个连通分图设第个11,.,liiiinnnin子图有个顶点因为第个分图是树所以有,l条边个分图共有边数为111()liinnln..T与已知矛盾所以为连通图34()(),.,TCCT若中有圈设为可以去掉中一条边并不影响的连通性,....如果剩余图中仍有圈可如前那样继续拿去一条边1(),ppT像这样去掉条边后得到一个没有圈的连通图1.,TnpTT显然有条边但既然是树顶点个数又与相同1...nTnT为个,所以中应有条边矛盾即中无圈,,,TuvT设中两点间无边直接相连由于是连通图所以经由,uv其他点必有一条链连结，且此链是连结这两点的唯一链(),(,),.TTuv否则中出现圈则后出现唯一一个圈45()().,,TTuv先证连通若不是连通图由定义至少存在两点之间.(,),uv无路可通那么加上一边也不会形成圈与已知矛盾..(,),(,)Tuvuv再证每舍去一边便不连通若中有一边舍去后(,),(,)TuvTTuv图仍然连通那么由于无圈是一棵树4(,),()TuvT但加一边后就是仍无圈与中树每加一新边必.出现唯一圈相矛盾5661()(),()(),.均显然故定理证毕一个图G有生成树的充要条件是G是连通图。v1v2v3v4v5v1v2v3v4v5G若图的生成子图是一棵树，则称该树为G的生成树(支撑树).证必要性是显然的:.G充分性设是连通图1(),,GGG如果不含圈则本身就是一棵树从而是它自身的.生成树2(),,,GG如果含圈任取一圈从圈中任意去掉一条边得到图111,GGGG的一个生成子图如果不含圈,那么是的一棵生成11;,,GG树如果仍含圈那么从中任取一个圈从圈中再任意去掉2,,,GG一条边得到图的一个生成子图如此重复最终可以得,,kkGGGG到的一个生成子图它不含圈则是图的一棵生成树.用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8（一）破圈法（二）避圈法112,,eee在图中任取一条边找出一条不与构成圈的边再找出12312{,}.,{,,...,},keeeeee不与构成圈的边一般地设已有找出121{,,...,},,kkeeee一条不与构成圈的边重复这个过程直到.,不能进行下去为止这时由所有取出的边所构成的图是.G图的一棵支撑树v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v6123443.最小生成树问题11(,),TVEGE如果图是图的一个生成树那么称上所有边*,().TSTGT的权的和为生成树的权记作如果图的生成树*(),,STGT的权在的所有生成树中的权最小即*()min()TSTST*.TG那么称是的最小生成树求最小树的方法：一、破圈法：在给定连通图G中，任取一圈，去掉一条最大权边（若有两条或两条以上的权均是最大权边，则任意去掉其中一条），在余图中任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即得到图G的最小树。二、避圈法：在给定连通图G中，任取权值最小的一条边，在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止，已选边与顶点构成的图T即为所求的最小树。v1v2v3v4v514231352破圈法求最小树：v1v2v3v4v514231352v1v2v3v4v514231352避圈法求最小树：v1v2v3v4v514231352三、最短路问题最短路问题是重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等，而且经常被作为一个基本工具，用