08运筹学-图论.

运筹帷幄之中决胜千里之外图与网络分析GraphTheoryandNetworkAnalysis第八章图与网络分析图与网络的基本知识树和最小支撑树最短路问题最大流问题最小费用流问题中国邮路问题本章主要内容：2020/1/15§1图与网络的基本知识图论起源——哥尼斯堡七桥问题问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？结论：不能。每个结点关联的边数要均为偶数。BDACABCD一笔画问题2020/1/15环球旅行问题：2020/1/15环球旅行问题的解另一个著名的问题:中国邮路问题2020/1/15图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点(顶点)和边的集合，记作：},{EVG其中:V——点集E——边集※图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。2020/1/15(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。2020/1/15又如：我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。石家庄太原北京天津塘沽济南青岛徐州连云港南京上海郑州武汉重庆2020/1/15再如：有六支球队进行足球比赛，我们分别用点v1，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用如下所示的有向图反映出来v3v5v2v4v6v12020/1/15定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6,e7,e8}，边数：m(G)=|E|=m顶点数：n(G)=|V|=n2020/1/15无向边与无向图：若图中任一条边的端点无序，即(vi,vj)与(vj,vi)是同一条边，则称它为无向边，此时图称为无向图。有向图：若图中边(vi,vj)的端点是有序的，则称它是有向边（或弧），vi与vj分别称为这条有向边的始点和终点，相应的图称为有向图。有向图无向图无向图,有向图2020/1/15环,多重边,简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。含多重边的图称为多重图。v3e7e4e8e5e6e1e2e3v1v2v4v5简单图多重图环多重边2020/1/15完全图每一对顶点间都有边相连的无向简单图称为无向完全图；有向完全图是指每一对顶点间有且仅有一条有向边的简单图。完全图顶点数n与边数m间成立如下关系:m=n(n-1)/22020/1/15二部图（偶图）图G=(V,E)的点集V可以分为两个非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为二部图（偶图）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。2020/1/15次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。2020/1/15v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3悬挂点孤立点悬挂边偶点奇点2020/1/15图中顶点次的性质定理1任何图中顶点次数的总和等于边数的2倍。定理2任何图中次为奇数的顶点必有偶数个。定义在有向图中，以顶点v为始点的边数称为顶点v的出次，记为d+(v)；以v为终点的边数称为v的入次，记为d-(v)。顶点v的出次与入次的和称为点v的次。定义图G=(V,E),若E'是E的子集，若V'是V的子集，且E'中的边仅与V'中的顶点相关联，则称G'=(V',E')为图G的一个子图，特别地，若V'=V,则称G'为G的一个生成子图（支撑子图）。2020/1/15子图，生成子图(支撑子图)图G1={V1、E1}和图G2={V2，E2}如果有称G1是G2的一个子图。若有，则称G1是G2的一个生成子图(支撑子图)。2121EEVV和2121EEVV，＝v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）2020/1/15网络（赋权图）设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。①②③④⑤⑥9102015714192562020/1/15链，圈，连通图定义无向图中一个点、边交错的序列，序列中的第一个和最后一个元素都是点，若其中每条边以序列中位于它之前和之后的点为端点，则称这个点边序列为图中连接其第一个点与最后一个点的称为链。链中所含的边数称为链长。链，但只是简单链而非初等链简单链：没有重复边；初等链：既无重复边也无重复点。对有向图可类似定义链，如果各边方向一致，则称为道路。kkvevev011{,,,,,}L2020/1/15链，圈，连通图定义若在无向图中，一条链的第一个点与最后一个点重合，则称这条链为圈。只有重复点而无重复边的圈为简单圈，既无重复点又无重复边的圈为初等圈。初等圈非简单的圈2020/1/15有向图无向图道路链（或道路）回路圈（或回路）道路(边的方向一致)2020/1/15连通图定义一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图总可以分为若干个连通子图，每一个称为原图的一个分图（连通分支）。连通图非连通图2020/1/15图的基本性质：定理1任何图中，顶点次数之和等于所有边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：mvdvdvdVvVvVv2)()()(212m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。2)(Vvvd1)(Vvvd2020/1/15图的矩阵表示：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中其他,0),(,1Evvajiij2020/1/15v5v1v2v3v4v64332256437vvvvvvvvvAvvv12345612366456010111101100010101111010100101101010例8.1下图所表示的图可以构造邻接矩阵A如下2020/1/15对于赋权图G=(V,E),其中边有权,构造矩阵B=(bij)nn其中：2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:其他的一个端点是边当且仅当的两个端点是边当且仅当0ev1ev2jijiijm3.权矩阵),(jivvjiwEvvEvvwbjijijiji),(0),(2020/1/15101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例8.2下图所表示的图可以构造邻接矩阵M如下:M=（mij）=2020/1/15654321654321030303302004020576305020007204346040vvvvvvvvvvvvBv5v1v2v3v4v64332256437例8.3下图所表示的图可以构造权矩阵B如下:2020/1/15§2最小支撑树问题本节主要内容：树支撑树最小支撑树2020/1/15树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例8.4乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员2020/1/15例8.5某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科2020/1/15树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v62020/1/15图的最小部分树(支撑树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G22020/1/15abcfedhgbfed2020/1/15abcfedhgbfdg2020/1/15bcedabcfedhg2020/1/15abchabcfedhg2020/1/15afdgabcfedhg2020/1/15求树的方法：破圈法和避圈法破圈法2020/1/15部分树2020/1/15避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v52020/1/15赋权图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=52020/1/15v1v2v3v4v5v643521得到最小树：MinC(T)=152020/1/15避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v68437526182020/1/15v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=152020/1/15例8.6某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居