上海财经大学《运筹学》课件-第六章

上海财经大学

运筹学

第六章图与网路分析图是最直观的模型2BACD图论

GraphTheory哥尼斯堡七桥问题(KönigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联36.1图与网路的基本概念

6.1.1图与网路节点

(Vertex)物理实体、事物、概念一般用vi

表示边

(Edge)节点间的连线，表示有关联一般用eij

表示图

(Graph)节点和边的集合一般用G(V,E)表示点集V={v1,v2,…,vn}边集E={eij}网路

(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)46.1.2无向图与有向图所有边都没有方向的图称为无向图，如图6.1在无向图中eij=eji，或(vi,vj)=(vj,vi)当所有边都有方向时，称为有向图，用G(V,A)表示在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图

6.1.3端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点若节点vi,vj

之间有一条边eij，则称vi,vj

是eij的端点(endvertex)，而eij

是节点vi,vj的关联边(incidentedge)同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(paralleledges)既没有自环也没有平行边的图称为简单图(simplegraph)在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为d

；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(evengraph)6

6.1.3端点，关联边，相邻，次有向图中，由节点向外指的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–次数为0的点称为孤立点(isolatedvertex)

，次数为1的点称为悬挂点(pendantvertex)定理1：图中奇点的个数总是偶数个

6.1.4链，圈，路径，回路，欧拉回路相邻节点的序列

{v1

,v2

,…,vn

}构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directedpath)首尾相连的路径称为回路(circuit)；7

走过图中所有边且每条边仅走一次的闭行走称为欧拉回路定理2：偶图一定存在欧拉回路(一笔画定理)

6.1.5连通图，子图，成分设有两个图G1(V1,E1),G2(V2,E2),若V2

V1,E2

E1，则G2是G1的子图无向图中，若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(discon-nectedgraph)；非连通图中的每个连通子图称为成分

(component)链，圈，路径(简称路)，回路都是原图的子图平面图(planargraph)，若在平面上可以画出该图而没有任何边相交86.2树图与最小生成树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图96.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个不同的标记树10

6.2.2

图的生成树如何找到一棵生成树深探法(depthfirstsearch)：任选一点标记为0点开始搜索，选一条未标记的边走到下一点，该点标记为1，将走过的边标记；假设已标记到i

点，总是从最新标记的点向下搜索，若从i

点无法向下标记，即与i

点相关联的边都已标记或相邻节点都已标记，则退回到

i

1点继续搜索，直到所有点都被标记广探法(breadthfirstsearch)：是一种有层级结构的搜索，一般得到的是树形图116.2.3

最小生成树有n个乡村，各村间道路的长度是已知的，如何敷设光缆线路使n个乡村连通且总长度最短显然，这要求在已知边长度的网路图中找最小生成树

最小生成树的算法：Kruskal

算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集T，只要不和前面加入的边构成回路，直到T中有n

1条边，则T是最小生成树Kruskal

算法基于下述定理定理3

指定图中任一点vi，如果vj

是距vi最近的相邻节点，则关联边eij必在某个最小生成树中。推论将网路中的节点划分为两个不相交的集合V1和V2，V2=V

V1，则V1和V2间权值最小的边必定在某个最小生成树中。126.2.3

最小生成树最小生成树不一定唯一定理3推论是一个构造性定理，它指示了找最小生成树的有效算法Prim

算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算

边权矩阵上的Prim算法：1、根据网路写出边权矩阵，两点间若没有边，则用表示；2、从v1

开始标记，在第一行打，划去第一列；3、从所有打的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打；4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边)；否则，返回第3步。该算法中，打行对应的节点在V1中，未划去的列在V2中136.2.3

最小生成树Prim算法是多项式算法Prim算法可以求最大生成树网路的边权可以有多种解释，如效率次数受限的最小生成树—尚无有效算法最小Steiner树—尚无有效算法

146.3

最短路问题

6.3.1狄克斯特拉算法(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步。15例1狄克斯特拉算法0

81510121511311316

Dijkstra最短路算法的特点和适应范围一种隐阶段的动态规划方法，而且是正向递推每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种深探法被框住的永久标记Tj

表示vs

到vj

的最短路，因此要求dij0，第k次迭代得到的永久标记，其最短路中最多有

k

条边，因此最多有n1

次迭代可以应用于简单有向图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第n1

次迭代后仍有节点的标记为，则表明vs

到该节点无有向路径如果只求vs

到vt

的最短路，则当vt

得到永久标记算法就结束了；但算法复杂度是一样的应用Dijkstra算法n1

次，可以求所有点间的最短路vs

到所有点的最短路也是一棵生成树，但不是最小生成树176.3.2Warshall-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

间最短路的长度。186.3.2Floyd-Warshall算法(1962)fori=1tondodii=;foralleij=0;forj=1tondofori=1tondoifi

jthenfork=1tondoifk

jthenbegin

dik=min{dik,dij+djk};

ifdik>dij+djktheneik=j

end;若网路中存在负回路，则计算中，某些dii会小于0，此时应中断算法显然，Floyd算法要进行n(n-1)2次加法和比较如何回溯找出任两点之间的最短路？在Floyd算法中设一伴随矩阵E={eik}，eik

记录了i

到

k

最短路中最后一个中间节点19小结最短路有广泛的应用(6.3.4节市话局扩容方案)最短路的多种形式：无向图，有向图无循环圈，有向图，混合图，无负边权，有负边权，有负回路，k-最短路等当存在负权值边时，Floyd算法比Dijkstra算法效率高，且程序极简单。但Dijkstra算法灵活若图是前向的，则Dijkstra算法也可以求两点间最长路一般情况下，两点间最长路是NP-complete，但最短路是P算法两点间k-最短路：分为边不相交的和边相交的

求边不相交的k-最短路非常容易：先求最短路，将该最短路中的边从网路删去，再用Dijkstra算法可求次最短路，以此类推206.3.4最短路应用举例——市话扩容(实装率=0.8)21最短路应用举例—市话扩容226.4网路的最大流和最小截

6.4.1网路的最大流的概念网路流一般在有向图上讨论定义网路上支路的容量为其最大通过能力，记为cij，支路上的实际流量记为fij图中规定一个发点s，一个收点t节点没有容量限制，流在节点不会存储容量限制条件：0

fij

cij平衡条件：

满足上述条件的网路流称为可行流，总存在最大可行流当支路上fij=cij

，称为饱和弧最大流问题也是一个线性规划问题viA(vi)B(vi)236.4.2截集与截集容量定义：把网路分割为两个成分的弧的最小集合，其中一个成分包含s

点，另一个包含t

点。一般包含s

点的成分中的节点集合用V表示，包含t

点的成分中的节点集合用V表示截集容量是指截集中正向弧的容量之和

福特-富克森定理：网路的最大流等于最小截集容量246.4.3确定网路最大流的标号法从任一个初始可行流出发，如0流基本算法：找一条从s

到t

点的增广链(augmentingpath)若在当前可行流下找不到增广链，则已得到最大流增广链中与s

到t方向一致的弧称为前向弧，反之后向弧

增广过程：前向弧f

ij=fij+q,后向弧f

ij=fij

q

增广后仍是可行流

25

最大流最小截的标号法步骤第一步：标号过程，找一条增广链1、给源点s

标号[s+,q(s)=]，表示从s点有无限流出潜力2、找出与已标号节点i

相邻的所有未标号节点j，若(1)(i,j)是前向弧且饱和，则节点

j

不标号；(2)(i,j)是前向弧且未饱和，则节点

j

标号为[i+,q(j)]，表示从节点i

正向流出，可增广q(j)=min[q(i),cij

fij]；(3)(j,i)是后向弧，若fji=0，则节点j

不标号；(4)(j,i)是后向弧，若fji>0，则节点j

标号为[i

,q(j)]，表示从节点j

流向

i，可增广q(j)=min[q(i),fji]；3、重复步骤2，可能出现两种情况：(1)节点t

尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流v(f)就是最大流；所有获标号的节点在V

中，未获标号节点在V

中，V与V

间的弧即为最小截集；算法结束(2)节点t

获得标号，找到一条增广链，由节点t

标号回溯可找出该增广链；到第二步26

最大流最小截的标号法步骤第二步：增广过程1、对增广链中的前向弧，令f=f+q(t)，q(t)为节点t

的标记值2、对增广链中的后向弧，令f=f

q(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集27最大流最小截集的标号法举例(s+,)(s+,6)(2

,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5

,2)(4+,2)28最大流最小截集的标号法举例(s+,)(s+,3)(2

,3)最小截集29

最大流标号法的复杂度讨论找一条增广链的计算量是容易估计的，不会超过O(n2)但是最多迭代多少次(即增广的次数)就很难估计，在最坏情况下，与边的容量有关；如上图：先增广suvt,然后增广svut，每次只能增广1个单位，故要增广4000次才能结束克服这种缺点的经验方法：尽量先用段数少的增广链尽量不重复前面出现过的增广链306.4.4多端网路问题316.4.5

最小费用最大流双权网路：每条弧不但有容量，还有单位流量的通过费用两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧基于可行弧集的最大流算法：从0费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主-对偶规划的解法。使用这种方法的还有运输问题、匹配问题326.4.5

以最短路为基础汇总网路上的流在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设a25=10是节点2和5之间的电路需求，节点2和5之间的最短传输路径为2

1

3

5，则加载过程为:T21=T21+10,T13=T13+10,T35=T35+10；Tij

是传输链路i

j

上加载的电路数；当所有点间电路都加载完则算法结束336.5欧拉回路和中国邮递员问题中国邮递员问题(ChinesePostmanProblem,CPP)是由我国管梅谷教授于1962年首先提出并发表的问题是从邮局出发，走遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？如果街区图是一个偶图，根据定理3，一定有欧拉回路，CPP问题也就迎刃而解了若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点显然要在奇次点间加重复边如何使所加的边长度最少归结为求奇次点间的最小匹配(minimumweightedmatch)—由Edmons给出多项式算法(1965)34

解中国邮递员问题的步骤0、将图中的所有悬挂点依次摘去1、求所有奇次点间的最短距离和最短路径2、根据奇次点间的最短距离求最小完全匹配3、根据最小完全匹配和最短路径添加重复边4、将悬挂点逐一恢复，并加重复边5、根据得到的偶图，给出欧拉回路的若干种走法35

解中国邮递员问题的步骤366.6哈密尔顿回路及旅行推销员问题

6.6.1哈密尔顿回路(Hamiltoniancircuit)连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中所有的点。显然哈密尔顿回路有且只有n

条边，若|V|=n连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是由爱尔兰数学家哈密尔顿1859年提出的，但至今仍未解决欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题搜索哈密尔顿回路的难度是NP-complete任两点间都有边的图称为完全图(或全连接图)完全图中有多少个不同的哈密尔顿回路？完全图中有多少个边不相交的哈密尔顿回路？最小哈密尔顿回路问题

(NP-complete)哈密尔顿路径：包含图中所有点的路径为什么说找两点间的最长路是非常困难的问题？(n

1)!/2(n

1)/2376.6.2旅行推销员问题(TravelingSalesman

Problem)旅行推销员问题(TSP)：设v1,v2,...,vn

为n

个已知城市，城市之间的旅程也是已知的，要求推销员从v1出发，走遍所有城市一次且仅一次又回到出发点，并使总旅程最短这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路问题一般旅行推销员问题(GTSP)：允许点重复的TSP当网路边权满足三角不等式时，一般旅行推销员问题就等价于最小哈密尔顿回路问题当网路边权不满足三角不等式时，只要用两点间最短路的距离代替原来的边权，就可以满足三角不等式，在此基础上求最小哈密尔顿回路

典型的应用：乡邮员的投递路线邮递员开邮箱取信的路线问题邮车到各支局的转趟问题38

TSP的启发式算法(Heuristicalgorithm)穷举法：指数算法分支定界法：隐枚举法二交换法(two-option,Lin’salgorithm)哈密尔顿回路可以用点的序列表示从任一个哈密尔顿回路(即任何一个序列)出发按照一定顺序试图交换相邻两个点的顺序，若路程减少则完成交换，继续下一个交换；若没有改善，则不进行本次交换，尝试下一个交换；若所有的相临交换都试过而不能改善，则算法结束，得到一个局部最优点模拟退火(SimulatedAnnealing)随机地采用二交换法当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率被接受，但这种概率是随模拟的温度下降而减少的发挥了计算机的优点，尽量减少陷入局部极值点模拟物理机制39

二交换法举例初始解：1-2-3-4-5

1-3-2-4-51-3-2-4-5

1-3-4-2-51-3-4-2-5

1-3-4-5-2

5-3-4-2-13-1-4-2-540

算法复杂度Prim算法i=1n

1次比较，最多n

1次赋值i=22(n

2)次比较，最多2(n

2)次赋值i=k

k(n

k)次比较，最多k(n

k)次赋值Dijkstra算法i=1n

1次临时标记，永久标记n

1次比较和赋值i=2n

2次临时标记，永久标记n

2次比较和赋值i=k

n

k

次临时标记，永久标记n

k

次比较和赋值41Prim算法的改进增加一个辅助记录型数组，用以记录当前V

中各节点到V

的最小边，minedge[i].cost记录该边的权值，minedge[i].vex记录该边V

中的顶点。若minedge[i].cost<0则表明i

点进入集合Vfori:=2tondobeginminedge[i].vex:=1;minedge[i].cost:=w[1,i]end;fori:=1ton

1dobeginmi:=maxint;forj:=2tondoif(minedge[j].cost>0)and(minedge[j].cost<mi)thenbegink:=j;mi:=minedge[j].costend;minedge[k].cost:=

minedge[k].cost;{找到k，将k

加入集合V}forj:=2tondoif(w[k,j]<minedge[j].cost)thenbeginminedge[j].cost:=w[k,j];minedge[j].vex:=k;end;end;{该算法复杂度约为5n(n-1)}42

匹配问题(MatchingProblem)定义：图中一组边的集合，当图中的每个节点最多只与该集合中的一条边相关联，则该边集就成为匹配。1、两部图的匹配问题图中的节点可分为两个集合，X,Y，X与Y

之间有边相连，但X

内部和Y

内部无关联边，称为两部图运输问题实际上是两部图的最小费用最大流问题任务分配问题实际上是两部图的最小完全匹配问题2、非两部图的匹配问题(1)最大基数匹配(maximumcardinalitymatching)(2)最大权匹配(maximumweightmatching)(3)最小完全匹配(minimumweightperfectmatching)(4)最优分数匹配(optimalfractionalmatching)43两部图的最小完全匹配匈亚利算法任务分配问题的抽象就是两部图的最小完全匹配问题匈亚利算法(Hungarianmethod)由Kuhn教授提出，它实际上是主对偶算法的先驱匈亚利算法借助于效率矩阵和两部图来完成运算任务分配问题的效率矩阵对应的是两部图的边权{cij}，对偶问题的解对应的是每条边的两个端点{ai,bj}；对偶约束为ai,＋bj

cij匈亚利算法的实质是通过构造对偶问题的可行解，得到一个等值边子图，即所有ai,＋bj＝cij

的边构成的图；然后在等值边子图上求最大基数匹配；当得到原问题的完全匹配，则算法结束对偶问题的可行解

等值边子图满足互补松弛定理求原问题的解(部分可行解)检验扩充等值边子图

44最大基数匹配最大基数匹配是基于交错树的算法敞露点、根、交错链、外点、内点、增广链尚未匹配的节点称为敞露点以敞露点为根，由非匹配边和匹配边交替构成的链称为交错链交错链的根为外点，其后内点与外点交替；外点是交错链的生长点以内点结束的交错链称为增广链，因为反转该链上各边的匹配状态可使匹配的边数增加一条45匈亚利算法步骤令所有ai＝0在效率矩阵中找每列最小值qj，令bj＝qj

，故i,j，满足ai＋bj

cij在满足ai＋bj＝cij

的边构成的等值子图中求最大基数匹配；若达到完全匹配则结束，否则到下一步对敞露点求每列的最小松弛量sj＝mini*{ci*j－ai*－bj}求最大增广量S＝0.5

minj{sj}增广等值子图，

j，bj＝