C类运筹学第5章图与网络

6.1图与网路的基本概念6.1.1图与网路•节点(Vertex)–物理实体、事物、概念–一般用vi表示•边(Edge)–节点间的连线，表示有关系–一般用eij表示•图(Graph)–节点和边的集合，–一般用G(V,E)表示–点集V={v1,v2,…,vn}–边集E={eij}v1v5v4v3v2e12e34e13e24e22e'13e45图6.1•网络(Network)–边上具有表示连接强度的权值，如wij–又称加权图(Weightedgraph)无向图与有向图•边都没有方向的图称为无向图，如图6.1•在无向图中eij=eji，或(vi,vj)=(vj,vi)•当边都有方向时，称为有向图，用G(V,A)表示•在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识•图中既有边又有弧，称为混合图端点，关联边，相邻，次•图中可以只有点，而没有边；而有边必有点•若节点vi,vj之间有一条边eij，则称vi,vj是eij的端点(endvertex)，而eij是节点vi,vj的关联边(incidentedge)•同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边•一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(paralleledges)•既没有自环也没有平行边的图称为简单图(simplegraph)•在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为d；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(evengraph)•有向图中，由节点指向外的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–•次数为0的点称为孤立点(isolatedvertex)，次数为1的点称为悬挂点(pendantvertex)定理1：图中奇点的个数总是偶数个链，圈，路径，回路，欧拉回路•相邻节点的序列{v1,v2,…,vn}构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走•在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directedpath)•首尾相连的路径称为回路(circuit)；•走过图中所有边且每条边仅走一次的闭行走称为欧拉回路定理2：偶图一定存在欧拉回路(一笔画定理)设有两个图G1(V1,E1),G2(V2,E2),若V2V1,E2E1，则G2是G1的子图•无向图中，若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(disconnectedgraph)；非连通图中的每个连通子图称为成分(component)•链，圈，路径(简称路)，回路都是原图的子图6.2树图与最小生成树•一般研究无向图•树图：倒置的树，根(root)在上，树叶(leaf)在下•多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图C1C2C3C4根叶6.2.1树的定义及其性质•任两点之间有且只有一条路径的图称为树(tree)，记为T树的性质：•最少边的连通子图，树中必不存在回路•任何树必存在次数为1的点•具有n个节点的树T的边恰好为n1条，反之，任何有n个节点，n1条边的连通图必是一棵树6.2.2图的生成树•树T是连通图G的生成树(spanningtree)，若T是G的子图且包含图G的所有的节点；包含图G中部分指定节点的树称为steinertree•每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树(labeledtree)Caylay定理：n(2)个节点，有nn2个不同的标记树6.2.2图的生成树•如何找到一棵生成树–深探法(depthfirstsearch)：任选一点标记为0点开始搜索，选一条未标记的边走到下一点，该点标记为1，将走过的边标记；假设已标记到i点，总是从最新标记的点向下搜索，若从i点无法向下标记，即与i点相关联的边都已标记或相邻节点都已标记，则退回到i1点继续搜索，直到所有点都被标记–广探法(breadthfirstsearch)：是一种有层级结构的搜索，一般得到的是树形图ACDBACDBACDBADCB6.2.3最小生成树•有n个乡村，各村间道路的长度是已知的，如何敷设光缆线路使n个乡村连通且总长度最短•显然，这要求在已知边长度的网路图中找最小生成树最小生成树的算法：•Kruskal算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集T，只要不和前面加入的边构成回路，直到T中有n1条边，则T是最小生成树•Kruskal算法基于下述定理定理3指定图中任一点vi，如果vj是距vi最近的相邻节点，则关联边eij必在某个最小生成树中。推论：将网路中的节点划分为两个不相交的集合V1和V2，V2=VV1，则V1和V2间权值最小的边必定在某个最小生成树中。6.2.3最小生成树•最小生成树不一定唯一•定理3推论是一个构造性定理，它指示了找最小生成树的有效算法•Prim算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算边权矩阵上的Prim算法：1、根据网路写出边权矩阵，两点间若没有边，则用表示；2、从v1开始标记，在第一行打，划去第一列；3、从所有打的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打；4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边)；否则，返回第3步。•该算法中，打行对应的节点在V1中，未划去的列在V2中6.2.3最小生成树97125.19179810787111275.9165.195.9101710111610•Prim算法是多项式算法•Prim算法可以求最大生成树•网路的边权可以有多种解释，如效率•次数受限的最小生成树—尚无有效算法•最小Steiner树—尚无有效算法v1v4v6v3v5v2101081177169.51712919.5通过一个网络的最短路径•最短路径问题:假如产品的生产地和销售地之间有多条路径组成的网络连接,要求从产地到销地的最短路径.一个网络通常由若干个节点(城镇),连接节点的边(公路)或弧(单行道)组成,边或弧旁的数字代表距离.狄克斯特拉算法(Dijkstraalgorithm,1959)•计算两节点之间或一个节点到所有节点之间的最短路令dij表示vi到vj的直接距离(两点之间有边)，若两点之间没有边，则令dij=，若两点之间是有向边，则dji=；令dii=0，s表示始点，t表示终点0、令始点Ts=0，并用框住，所有其它节点标记Tj=；1、从vs出发，对其相邻节点vj1进行临时标记，有Tj1=ds,j1；2、在所有临时标记中找出最小者，并用框住，设其为vr。若此时全部节点都永久标记，算法结束；否则到下一步；3、从新的永久标记节点vr出发，对其相邻的临时标记节点进行再标记，设vj2为其相邻节点，则Tj2=min{Tj2,Tr+dr,j2}，返回第2步。例狄克斯特拉算法2s5t634107491881522023008151012151131132s5t6341074918815220230Dijkstra算法的特点和适应范围•一种隐阶段的动态规划方法•每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种深探法•被框住的永久标记Tj表示vs到vj的最短路，因此要求dij0，第k次迭代得到的永久标记，其最短路中最多有k条边，因此最多有n1次迭代•可以应用于简单有向图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第n1次迭代后仍有节点的标记为，则表明vs到该节点无有向路径•如果只求vs到vt的最短路，则当vt得到永久标记算法就结束了；但算法复杂度是一样的•应用Dijkstra算法n1次，可以求所有点间的最短路Warshall-Floyd算法(1962)•Warshall-Floyd算法可以解决有负权值边(弧)的最短路问题•该算法是一种整体算法，一次求出所有点间的最短路•该算法不允许有负权值回路，但可以发现负权值回路•该算法基于基本的三角运算定义：对给定的点间初始距离矩阵{dij}，令dii=，对所有i。对一个固定点j，运算dik=min{dik,dij+djk},对所有i,kj,称为三角运算。(注意，这里允许i=k)定理：依次对j=1,2,…,n执行三角运算，则dik最终等于i到k间最短路的长度。kjidijdjkdikFloyd-Warshall算法(1962)fori=1tondodii=;foralleij=0;forj=1tondofori=1tondoifijthenfork=1tondoifkjthenbegindik=min{dik,dij+djk};ifdikdij+djktheneik=jend;例1中1到7点的最短路是1-2-5-7查伴随矩阵E的第一行123456710020255•若网路中存在负回路，则计算中，某些dii会小于0，此时应中断算法•显然，Floyd算法要进行n(n-1)2次加法和比较•如何回溯找出任两点之间的最短路？•在Floyd算法中设一拌随矩阵E={eik}，eik记录了i到k最短路中最后一个中间节点小结•最短路有广泛的应用(6.3.4节市话局扩容方案)•最短路的多种形式：无向图，有向图无循环圈，有向图，混合图，无负边权，有负边权，有负回路，k-最短路等•当存在负权值边时，Floyd算法比Dijkstra算法效率高，且程序极简单。但Dijkstra算法灵活•若图是前向的，则Dijkstra算法也可以求两点间最长路•一般情况下，两点间最长路是NP-complete，但最短路是P算法•两点间k-最短路：边不相交的和边相交的求边不相交的k-最短路非常容易：先求最短路，将该最短路中的边从网路删去，再用Dijkstra算法可求次最短路，以此类推6.3.4最短路应用举例——市话扩容(实装率=0.8)年号0123456789101112预测数1.61.82.02.22.52.83.13.53.94.44.95.56.2t02000t64000t85000t96000t117000t128000t330001,42,76,135,124,8.83,8.31,3.52,6.04,8.33,7.15,8.91,32,4.53,6.84,7.51,2.52,4.33,5.5最短路应用举例—市话扩容0361211984128.8722.32.533.58.98.37.1647.56.84.58.3135.54.3通过一个网络的最大流量•最大流问题:假如从天然气的产地和销地之间有多条管道组成的网络连接,要求从产地到销地的最大流量.一个网络通常有若干个节点(城镇),连接节点之间的管道用边或弧(有向管道)组成,边或弧旁的数字代表管道的最大容量.基本概念•可行流•最大流•增广链•截集与截量网路的最大流-网路的最大流的概念•网路流一般在有向图上讨论•定义网路上支路的容量为其最大通过能力，记为cij，支路上的实际流量记为fij•图中规定一个发点s，一个收点t•节点没有容量限制，流在节点不会存储•容量限制条件：0fijcij•平衡条件：tifvtsisifvffijijvBvjivAvij)(,0)()()(•满足上述条件的网路流称为可行流，总存在最大可行流•当支路上fij=cij，称为饱和弧•最大流问题也是一个线性规划问题viA(vi)B(vi)6.4.2截集与截集容量定义：把网路分割为两个成分的弧的最小集合，其中一个成分包含s点，另一个包含t点。•一般包含s点的成