运筹学课件第8章-图与网络分析

第8章图与网络分析图与网络模型GraphTheory

引言

十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有7座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这7座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡7桥”难题。ABCD图与网络模型GraphTheory

引言“哥尼斯堡7桥”难题最终在1736年由数学家Euler的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到1936年匈牙利数学家O.König写出了图论的第一本专著《有限图与无限图的理论》。在图论的发展过程中还有两位著名科学家值得一提，他们是克希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究。图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。它描述对一张地图着色的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白这一问题，但是，两人都无能为力。”幸运的是在1970‘s终于由美国的两位数学家借助大型计算机将其证明了。图与网络模型GraphTheory

图与网络的基本概念

图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正如一位数学家所说：“可以说，图论为任何一个包含了某种二元关系的系统提供了一种分析和描述的模型。”下面我们来看一个案例——

国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：图与网络模型GraphTheory

图与网络的基本概念各办事处已订购机票情况表成都重庆武汉上海西安郑州沈阳昆明广州北京成都重庆武汉上海西安郑州沈阳昆明广州北京105158121030106152510158861481881082610图与网络模型GraphTheory

图与网络的基本概念

将此问题通过图的模型描述：下图中，点——各城市，带箭头连线——从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字——机票数量。成重武昆上广西郑沈京8郑州办事处已订有的到北京的机票数量。图与网络模型GraphTheory

图与网络的基本概念一、图及其分类和术语

1、图论中所研究的图并非几何学中的图，也不是绘画中的图。在这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，也就是说我们研究的是某个系统中的元素——点，以及这些元素之间的某种关系——连线。定义：图——一个图G是一个有序二元组（V，E），记为G=（V，E）其中（1）V是一个有限非空的集合，其元素称为G的点或顶点，而称V为G的点集V={v1，v2，···，vn}；（2）E是V中元素的无序对(vi，vj)所构成的一个集合，其元素称为G的边，一般表示为e=(vi，vj)，而称E是G的边集。边（无向边）——没有方向的连线弧（有向边）——带有方向的连线无向图——有向图——简单图——多重图——完全图——二部图（偶图，双图）——图与网络模型GraphTheory

图与网络的基本概念子图——真子图——生成子图——点生成子图——边生成子图——点的次——奇次点——偶次点——链——圈——路——回路——赋权图——2、连通图在众多各类图中有一类在实际应用中占有重要地位的图连通图——在图中，任意两点间至少存在着一条链连通图不连通图图与网络模型GraphTheory

图与网络的基本概念3、图与矩阵在图与网络分析的应用中，将面临一个问题——如何分析、计算一个较大型的网络，这当然需借助快速的计算工具——计算机。那么，如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有——邻接矩阵、关联矩阵、权矩阵等。邻接矩阵——对于图G=（V，E），|V|=n，|E|=m，有n

n阶方矩阵A=（aij）n

n，其中

aij=k当且仅当vi与vj之间有条边时

0其它图与网络模型GraphTheory

图与网络的基本概念邻接矩阵A=（aij）n

n=0100100010101000010010020000011011100001000100100001110000201000v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8图与网络模型GraphTheory

图与网络的基本概念关联矩阵——对于图G=（V，E），|V|=n，|E|=m，有m

n阶矩阵M=（mij）m

n，其中

mij

=2当且仅当

vi是边ej

的两个端点1当且仅当

vi是边ej

的一个端点例——0其它v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8M=（mij）=101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12图与网络模型GraphTheory

最小树问题二、树（Tree）和最小树树是图论中一类重要的图，实际中有很多系统的结构都是树。树——连通且不含圈的图，简记为T。下面的说法是等价的：T是一个树。

T无圈，且m=n-1。T连通，且m=n-1。T无圈，但每加一条新的边即出现唯一一个圈。T连通，但每舍去一条边就不连通。T中任意两点，有唯一的一条链相连。T是边数最少的连通图。图的生成树——若G图的一个点生成子图是一个树，则称此树是G图的一个生成树。树的权——若Tk是加权图G的一棵树，则树T的全部边的权之和称为树Tk的权，记为（Tk

）=（e）；e

Tk最小树——T*是加权图G的一棵最小树，即（T*）=min{(Tk)}k图与网络模型GraphTheory

最小树问题破圈法，避圈法求生成树：图G生成树T生成树T图与网络模型GraphTheory

最小树问题破圈法，避圈法求最小生成树：图G生成树T生成树T15424531344215121231211212312112图与网络模型GraphTheory

最短路问题三、路（Path）和最短路最短路问题是网络分析中应用最广泛的问题之一。尽管前面介绍了用动态规划方法求解，但有时却较困难，此时图论的方法却十分有效。最短路问题的一般描述：G=（V，E）是连通图，图中各边（vi，vj）有权lij（=

表示vi，vj间无边），vs

、vt为图中任意两指定点，求一条路

µ，使其是从vs到vt的所有路中最短（路中各边的权之和最小）的一条路。即L（

µ）=min

lij（vi，vj）

µ图与网络模型GraphTheory

最短路问题

E.W.Dijkstra

算法（标号算法）算法基本思路分析：（逐步向外搜索）52165828997221210∞∞∞∞∞∞∞∞X（P标号）Y（T标号）起点到该点的最短距离起点到该点的最短距离的上界2527511121210575667991010633人、狼、羊、草渡河游戏一个人带着一条狼、一只羊、一筐白菜过河蛤由于船太小，人一次只能带一样东西乘船过河。狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉。人——M（Man），狼——W（Wolf），羊——G（Goat），草——H（Hay）。点——vi

表示河岸的状态，边——ek

表示由状态vi

经一次渡河到状态vj

，权——边ek

上的权定为1。我们可以得到下面的加权有向图：图与网络模型GraphTheory

最短路问题v1，u1=（M，W，G，H）；v2，u2=（M，W，G）；v3，u3=（M，W，H）；v4，u4=（M，G，H）；v5，u5=（M，G）。此游戏转化为在下面的二部图中求从v1到u1的最短路问题。v1v2v3v4v5u5u4u3u2u1图与网络模型GraphTheory

最短路问题

在E.W.Dijkstra

算法中必须满足一个条件——在图G中所有边的权lij

≥0。若在图G中存在有负权边（当然，这种情形只针对有向图而言）时必须对E.W.Dijkstra

算法加以修改——称为修改的E.W.Dijkstra

算法。2、情况二：wij≤0设从V1到Vj(j=1,2,…,t)的最短路长为P1jV1到Vj无任何中间点P1j（1）=wijV1到Vj中间最多经过一个点

P1j（2）=min{P1j（1）+wij}V1到Vj中间最多经过两个点

P1j（3）=min{P1j（2）+wij}…….V1到Vj中间最多经过t-2个点

P1j（t-1）=min{P1j（t-2）+wij}终止原则：1）当P1j（k）=P1j（k+1）可停止，最短路P1j*=P1j（k）2）当P1j（t-1）=P1j（t-2）时，再多迭代一次P1j（t），若P1j（t）

=P1j（t-1），则原问题无解，存在负回路。

例：求下图所示有向图中从v1到各点的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342

wij

d(t)(v1,vj)v1v2v3v4v5v6v7v8v1v2v3

v4v5v6v7v8025-30-2406400-30720320t=1t=2t=3t=4t=5t=6025-3020-3611020-36615020-3361410020-336910020-336910说明：表中空格处为+

。4例设备更新问题制订一设备更新问题，使得总费用最小

第1年第2年第3年第4年第5年购买费1314161924

使用年数0-11-22-33-44-5

维修费810131827

[解]设以vi(i=1,2,3,4,5)表示“第i年初购进一台新设备”这种状态，以v6表示“第5年末”这种状态；以弧(vi,

vj)表示“第i年初购置的一台设备一直使用到第j年初”这一方案，以wij表示这一方案所需购置费和维护费之和。v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31,V1)(44,V1)(62,V1)(78,V3)这样，可建立本例的网络模型。于是，该问题就可归结为从图中找出一条从v1到v6的最短路问题。用Dijkstra标号法，求得最短路为

v1v3v6

即第一年初购置的设备使用到第三年初予以更新，然后一直使用到第五年末。这样五年的总费用最少，为78。图与网络模型GraphTheory

距离矩阵摹乘法Dijkstra算法比较简单，但是，对于含有负权弧的网络可能失效。这时，应对算法加以修改，即所谓“修改的Dijkstra算法”。下面，介绍一种算法——距离矩阵摹乘法，它适用于任何网络的最短路问题。例如——v1v3v4v2v6v534233-24411-16333图与网络模型GraphTheory

距离矩阵摹乘法1、网络的距离矩阵设一网络N中有n个点，其中任意两点vi

与vj

之间都有一条边(vi,vj)，其权数为wij>-∞。若vi

与vj

不相邻，则虚设一条边(vi,vj)，并令其权数wij=∞。距离矩阵W=（wij

）前例中的距离矩阵为W=v1v2v3v4v5v6v1032∞∞4v2∞04∞41v3∞∞0-16∞v43-2∞01∞v55∞∞∞03v6∞∞33∞0图与网络模型GraphTheory

距离矩阵摹乘法2、求各点至某点的最短路求vi（i=1,2,…,n）至某点vr

的最短路。令：dir(k)=vi走k步达到vr

的最短距离，i=1,2,…,n则有dir(1)=wir,i=1,2,…,ndir(k)=min｛wij+djr(k-1)

｝,i=1,2,…,n1≤j≤n令：dk=（d1r(k),d2r(k),…dnr(k),）T,k=1,2,…图与网络模型GraphTheory

距离矩阵摹乘法矩阵摹乘运算法：

dk=Wdk-1,(k=2,3,…)当

dk=dk-1,(k=2,3,…)则计算停止，dk

中的元素即为各点到

vr

的最短距离。图与网络模型GraphTheory

网络中心和重心问题一、基本概念网络最短距离矩阵

D=(dij)n×ndij——表示vi到vj的最短距离（1）网络的中心令：d(vi)=maxdij,i=1,2,…,n若max

d(vi)=d(vk)1≤i≤n1≤j≤n则称点vk

为网络的中心。图与网络模型GraphTheory

网络中心和重心问题（2）网络的重心设gi

为点vi

的权重（i=1,2,…,n），令：h(vj)=∑gidij,j=1,2,…,ni=1n若max

h(vj)=h(vr)1≤j≤n则称点vr

为网络的重心。图与网络模型GraphTheory

网络中心和重心问题二、应用例——某地7个村镇之间的现有交通道路如下图，边旁数值为各村镇之间道路的长度，点旁数值为各村镇的小学生人数。现拟在某一村镇建一商店和小学，试问：（1）商店应该建在何村，能使各村都离它较近？（2）小学应该建在何村，能使各村小学生总的行走路程最短？图与网络模型GraphTheory

网络中心和重心问题v1v3v4v5v6v7v2746435712324230404535252050距离人数图与网络模型GraphTheory

网络中心和重心问题（1）中心问题网络最短距离矩阵如下：vjviD=(dij)d(vi)=maxdij

123456710345781010230324577343055688452502355(min)57452013768563102871078532010j结论：商店应该建在v4村。图与网络模型GraphTheory

网络中心和重心问题（2）重心问题vjvigidij123456710120160200280320400275075501001251753180135022522527036041506015006090150514080100400206062801752101053507075003504002501501000h(vj)13259201095870850(min)9251215结论：小学应该建在v5村。第四节最大流问题

如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？vsv2v1v3v4vt432312234图与网络模型GraphTheory

网络流问题定义1：定一个有向图D=(V,E),在V中有一个发点vs和一收点vt，其余的点为中间点。对于每一条弧(vi,vj),对应有一个c(vi,vj)0,(cij)称为弧的容量。这样的有向图称为容量网络。记为D=(V,E,C)。1、网络流——义在弧集合E上的一个函数f={f(vi,vj)}，称f(vi,vj)为弧(vi,vj)上的流量，简记fij。2、可行流——3、最大流——4、增广链——5、最小截集——2、可行流与最大流定义2满足下列条件的流称为可行流：1)0

fijcij2)平衡条件：中间点

fij=fji(vi,vj)A(vj,vi)A发点vs

fsj–fjs=v(f)(vs,vj)A(vj,vs)A

ftj–fjt=–v(f)(vt,vj)A收点vt，(vj,vt)A式中v(f)称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。最大流问题：求一流{fij}满足0

fijcijv(f)i=s

fij–fji=0i

s，t–v(f)i=t且使v(f)达到最大。3、增广链

给定可行流f={fij}，使fij=cij的弧称为饱和弧，使fij<cij的弧称为非饱和弧，把fij=0的弧称为零流弧，fij>0的弧称为非零流弧。

若是网络中连接发点vs和收点vt的一条链，定义链的方向是从vs到vt，则链上的弧被分成两类：前向弧：弧的方向与链的方向一致全体+后向弧：弧的方向与链的方向相反全体—定义3设f是一可行流，是从vs到vt的一条链，若满足下列条件，则称之为（关于流f的）一条增广链：在弧(vi,vj)

+上，0fij<cij

在弧(vi,vj)—上，0<fijcij

4、截集与截量

定义4给定网络D=(V,A,C)，若点集V被剖分为两个非空集合V1和V1，使vs

V1，vt

V1，则把弧集(V1,V1)称为是（分离vs和vt的）截集。截集是从vs到vt的必经之路。

定义5给定一截集(V1,V1)，把截集(V1,V1)中所有弧的容量之和称为这个截集的容量(截量),记为C(V1,V1)。v(f)

C(V1,V1)图与网络模型GraphTheory

网络流问题1、流量——截量定理容量网络上任何一个可行流的流量不超过任何一个截集的截量。2、增广链调整定理在增广链上对可行流进行调整可以得到一个流量更大的可行流。3、最大流定理可行流是最大流的充分必要条件是不存在关于该可行流的增广链。步骤：2、标号过程1、选取一个可行流（可选择零流弧）

从Vs出发，在前向弧上(vi,vj)，若fij<cij，则给vj标号(vi,l(vj))，其中l(vj)=min[l(vi)，cij–fij]。在后向弧(vj,vi)上，若fji>0，则给vj标号(–Vi,l(vj))，其中l(vj)=min[l(vi)，fji]。二、寻找最大流的标号法(FordFulkerson)

思想：从一可行流出发，检查关于此流是否存在增广链。若存在增广链，则增大流量，使此链变为非增广链；这时再检查是非还有增广链，若还有，继续调整，直至不存在增广链为止。3、若标号延续到vt，表明得到一条从vs到vt的增广链，转入调整阶段4，否则当前流即为最大流。4、调整过程令调整量为

=l(vt)令fij+

(vi,vj)

+fij´=fij–

(vi,vj)

—

fij(vi,vj)

去掉所有的标号，对新的可行流f´={fij´}，重新进入标号过程。可结合下图理解其实际涵义。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例求下列网络的最大流与最小截集。[解]一、标号过程则v1的标号为(vs,l(v1))，其中l(v1)=min{l(vs)，cs1–fs1}=min{+

，9–2}=2（3）检查v1,在弧(v1,v4)上,f14=7,c14=9,f14<c14,则v4的标号为(v1,l(v4))，其中l(v4)=min{l(v1)，c14–f14}=min{2，3-1}=2（4）检查v4,在弧(v3,v4)上,f14=1>0，则v3的标号为(-v4,l(v3))，其中l(v3)=min{l(v4)，f34}=min{2，1}=1（5）检查v3,在弧(v3,vt)上,f3t=3,c3t=6,f3t<c3t,则vt的标号为(v3,l(vt))，其中l(vt)=min{l(v3)，c3t–f3t}=min{1，6-3}=1这样，我们得到了一增广链

,如图所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0,)(vs,2)(v1,2)(-v4,1)(v3,1)其中

+={(vs,v1),(v1,v4),(v3,vt)}，

—={(v3,v4)}二、调整过程取调整量为

=1，在上调整f。在

+上：fs1+=7+1=8

f14+=2+1=3

f4t+=5+1=6在—上：f43–=1–1=0s1vtvv3(9,8)(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7)

在上图中重复上述标号过程，依次给vs,v2,v1,v4标号后，由于标号无法继续下去，算法结束。这时的流为最大流，最大流的流量为vvv(4,4)v(f)=8+3=11

与此同时，可找到最小截集(V1,V1)，其中V1为标号点集合，V1为未标号点集合，弧集合(V1,V1)即为最小截集。此例中，V1={vs,v2,v1,v4},V1={v3,vt},(V1,V1)={(v1,v3)，(v4,vt)}图与网络模型GraphTheory

网络流问题容量网络N上最大流的标号（Ford-Fulkerson）算法：下面，我们采用此算法来求解前面的旅行总社计划问题案例——图与网络模型GraphTheory

最大流问题各办事处已订购机票情况表成都vs重庆v1武汉v2上海v3西安v4郑州v5沈阳v6昆明v7广州v8北京vt成都重庆武汉上海西安郑州沈阳昆明广州北京101512812103010615251015886148