第八章 图与网络分析

第八章图与网络分析第1页，课件共83页，创作于2023年2月本章内容图与网络的基本知识树最短路问题最大流问题最小费用流问题第2页，课件共83页，创作于2023年2月BDACABCD哥尼斯堡七空桥一笔画问题§1图与网络的基本知识环球旅行问题第3页，课件共83页，创作于2023年2月一个图是由点集V={vj}和V中元素的无序对的一个集合E={ek}构成的二元组，记为G=(V,E),其中V

中的元素vj

叫做顶点，V表示图G的点集合；E中的元素ek

叫做边，E表示图

G的边集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例图1定义1图及其分类第4页，课件共83页，创作于2023年2月如果一个图是由点和边所构成的，则称其为无向图，记作G=(V,E)，连接点的边记作[vi,vj],或者[vj,vi]。如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj

的弧，记作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}图2图及其分类第5页，课件共83页，创作于2023年2月一条边的两个端点是相同的,那么称为这条边是环。如果两个端点之间有两条以上的边，那么称为它们为多重边。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。定义2定义3图及其分类第6页，课件共83页，创作于2023年2月定义4图G=(V,E)的点集V可以分为两个非空子集X，Y，即X∪Y=V,X∩Y=

，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图(偶图)，有时记作G=(X,Y,E)。X:{v1,v3,v5}Y:{v2,v4,v6}v1v3v5v6v4v2图及其分类第7页，课件共83页，创作于2023年2月v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。以点v为端点的边的个数称为点v的度（次），记作。图中d(v1)=4，d(v6)=4（环计两度）定义5顶点的次第8页，课件共83页，创作于2023年2月有向图中，以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi

的入次，用表示；vi

点的出次和入次之和就是该点的次。所有顶点的入次之和等于所有顶点的出次之和。定理1定理2所有顶点度数之和等于所有边数的2倍。在任一图中，奇点的个数必为偶数。定义6顶点的次第9页，课件共83页，创作于2023年2月图G=(V,E)，若E′是E的子集，V′是V的子集，且E′中的边仅与V′中的顶点相关联，则称G′=(V′,E′)是G的一个子图。特别是，若V′=V，则G′称为G的生成子图(支撑子图)。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图定义7子图第10页，课件共83页，创作于2023年2月在实际应用中，给定一个图G=（V,E）或有向图D=（V,A）,在V中指定两个点，一个称为始点（或发点），记作v1

，一个称为终点（或收点），记作vn

，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。

定义8无向图G=(V,E)，若图G中某些点与边的交替序列可以排成(vi0,ei1,vi1,ei2,…,vik-1,eik,vik)的形式，且eit=(vit-1,vit)(t=1,…,k)，则称这个点边序列为连接vi0与vik的一条链，链长为k。点边列中没有重复的点和重复边者为初等链。连

通

图第11页，课件共83页，创作于2023年2月连

通

图无向图G中，连结vi0与vik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中既无重复点也无重复边者为初等圈。定义9定义10一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图。对于有向图可以类似于无向图定义链和圈，初等链、圈，此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同。第12页，课件共83页，创作于2023年2月对于网络（赋权图）G=（V,E）,其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。设图G=（V,E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。定义11定义12图的矩阵表示当G为无向图时，邻接矩阵为对称矩阵。第13页，课件共83页，创作于2023年2月例权矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437图的矩阵表示第14页，课件共83页，创作于2023年2月欧拉回路与中国邮路问题定义13

连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图(E图)。在引言中提到的哥尼斯堡七桥问题就是要在图中寻找一条欧拉回路。定理3无向连通图G是欧拉图，当且仅当G中无奇点。定理4连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。第15页，课件共83页，创作于2023年2月欧拉回路与中国邮路问题定理5已知图G*=G+E1无奇点，则最小的充分必要条件为：(1)每条边最多重复一次；(2)对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。第16页，课件共83页，创作于2023年2月本章内容图与网络的基本知识树最短路问题最大流问题最小费用流问题第17页，课件共83页，创作于2023年2月§2树ACBEDGFIHJKNML运动员乒乓球单打比赛第18页，课件共83页，创作于2023年2月树的概念和性质定理6定义14连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。图T=(V,E),|V|=n,|E|=m，则下列关于树的说法是等价的。(1)T是一个树。(2)T无圈，且m=n-1。(3)T连通，且m=n-1。(4)T无圈，但每加一新边即得惟一一个圈。(5)T连通，但任舍去一边就不连通。(6)T中任意两点，有惟一链相连。第19页，课件共83页，创作于2023年2月一个图G有生成树的充要条件是G

是连通图。v1v2v3v4v5v1v2v3v4v5设图是图G=(V,E)的一支撑子图，如果图是一个树,那么称K是G的一个生成树（支撑树），或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。定义15定理7图的生成树第20页，课件共83页，创作于2023年2月（一）避圈法

在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3。一般设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。第21页，课件共83页，创作于2023年2月e5v1v2v5e2e3e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6v3v1v2v3v5e1e6e8e4v4第22页，课件共83页，创作于2023年2月（二）破圈法第23页，课件共83页，创作于2023年2月用破圈法求出下图的一个生成树。

v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8第24页，课件共83页，创作于2023年2月最小生成树问题定义16如果图是图G的一个生成树，那么称E1上所有边的权的和为生成树T的权，记作S(T)。如果图G的生成树T*的权S(T*)，在G的所有生成树T中的权最小，即那么称T*是G的最小生成树。某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v612344第25页，课件共83页，创作于2023年2月v1v2v3v4v514231352根据破圈法和避圈法两种方式得到了图的两个不同的支撑树，由此可以看到连通图的支撑树不是唯一的。第26页，课件共83页，创作于2023年2月最小树的两种算法

算法1（Kruskal算法）

算法2（破圈法）第27页，课件共83页，创作于2023年2月树根及其应用定义17若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。定义18有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树(又称外向树)。定义19在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树。若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。第28页，课件共83页，创作于2023年2月本章内容图与网络的基本知识树最短路问题最大流问题最小费用流问题第29页，课件共83页，创作于2023年2月最短路的一般提法为：设为连通图，图中各边有权（表示之间没有边），为图中任意两点，求一条路，使它为从到的所有路中总权最短。即：最小。§3最短路问题(一)狄克斯屈拉(Dijkstra)算法适用于wij≥0，给出了从vs到任意一个点vj的最短路。Dijkstra算法是在1959年提出来的。目前公认，在所有的权wij≥0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。第30页，课件共83页，创作于2023年2月算法步骤：1.给始点vs以P标号，这表示从vs到

vs的最短距离为0，其余节点均给T标号，

2.设节点vi

为刚得到P标号的点，考虑点vj，其中，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。第31页，课件共83页，创作于2023年2月例9用Dijkstra算法求下图从v1到v8的最短路。

解（1）首先给v1以P标号，给其余所有点T标号。（2）（3）（4）v1v7v2v3v6v4v8v54594546467157比较所有T标号，T(v2)最小，令P(v2)=4，并记录路径(v1,v2)第32页，课件共83页，创作于2023年2月比较所有T标号，T(v3)最小，令P(v3)=6,并记录路径(v1,v3)比较所有T标号，T(v5)最小，令P(v5)=8,并记录路径(v2,v3)比较所有T标号，T(v4)最小，令P(v4)=9,并记录路径(v2,v4)比较所有T标号，T(v6)最小，令P(v6)=13,并记录路径(v5,v6)第33页，课件共83页，创作于2023年2月比较所有T标号，T(v7)最小，令P(v7)=14,并记录路径(v7,v8)因为只有一个T标号T(v8)最小，令P(v8)=15,并记录路径(v7,v8)，v1到v8之最短路为:v2v1v7v5v8

Dijkstra算法仅适合于所有的权wij>=0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。第34页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.55222140如图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。标号法练习第35页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.552221403第36页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.552221403第37页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.5522214034第38页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.5522214034第39页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.55222140345第40页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.55222140345第41页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.5522214034665第42页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.5522214034665第43页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.55222140346756第44页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.552221403467568.5第45页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.552221403467568.59第46页，课件共83页，创作于2023年2月v1v9v8v7v6v5v4v3v23333342.552221403467568.59第47页，课件共83页，创作于2023年2月练习：求从v1到v8的最短路(0)(1,1)(1,3)(3,5)(2,6)(5,10)(5,9)(5,12)第48页，课件共83页，创作于2023年2月标号法练习求从v1到v8的最短路(2,6)第49页，课件共83页，创作于2023年2月算法的基本思路与步骤：首先：设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令即用v1到vj的直接距离做初始解。第二步，使用递推公式：

求，当进行到第t步，若出现则停止计算，即为v1到各点的最短路长。（二）逐次逼近法第50页，课件共83页，创作于2023年2月例10

求图中v1到各点的最短路v1v2v3v4v5v6v7v85-32443－1-217-324第51页，课件共83页，创作于2023年2月解：初始条件为第一轮迭代：第52页，课件共83页，创作于2023年2月类似可得v1v2v3v4v5v6v7v8P1j(1)P1j

(2)P1j

(3)P1j

(4)P1j

(5)P1j

(6)v1025-3

000000v20

-2

4

22222-5v3

0

6

500000v4

40

-3-3-3-3-3-3v5

0

66333v6

-304

116666v7

7

2

0

1499v8

3

-10

15101010表中最后一列数字表示v1到各点的最短路长第53页，课件共83页，创作于2023年2月例11求：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1）分析：可行的购置方案（更新计划）是很多的，如：1)每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59

显然不同的方案对应不同的费用。

第i年度

12345购置费1111121213设备役龄0-11-22-33-44-5维修费用

5681118第54页，课件共83页，创作于2023年2月

（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：

1）画赋权有向图：设vi表示第i年初，(vi,vj

)表示第i年初购买新设备用到第j年初（j-1年底），而Wij表示相应费用，则5年的一个更新计划相当于从v1

到v6的一条路。

2）求解（标号法）

第55页，课件共83页，创作于2023年2月W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31第56页，课件共83页，创作于2023年2月（三）Floyd算法可直接求出网络中任意两点间的最短路；第57页，课件共83页，创作于2023年2月本章内容图与网络的基本知识树最短路问题最大流问题最小费用流问题第58页，课件共83页，创作于2023年2月§4最大流问题

最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，等等。20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。第59页，课件共83页，创作于2023年2月问题引入vsv2v3v4v1vt33244242321上图可看作输油管道网，vs为起点，vt为终点，v1,v2,v3,v4为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大?第60页，课件共83页，创作于2023年2月网络D上的流，是指定义在弧集合E上的一个函数其中f(vi,vj)=fij

叫做弧(vi，vj)上的流量。最大流有关概念定义20设一个赋权有向图D=（V,E）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）∈E,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，E，C）。第61页，课件共83页，创作于2023年2月称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi,vj）∈E

有0≤

fij

≤

cij

。（2）平衡条件：对于发点vs，有对于收点vt

，有对于中间点，有可行流中fij＝cij

的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0的弧为非零流弧，fij＝0的弧叫做零流弧。第62页，课件共83页，创作于2023年2月定义21容量网络G=(V,E,C),vs,vt为发、收点，若有边集E′为E的子集，将G分为两个子图G1,G2，其顶点集合分别记S，，S∪=V,S∩=,vs,vt分属S，，满足：①G(V,E-E′)不连通；②E″为E′的真子集，而G(V,E-E″)仍连通，则称E′为G的割集，记E′=(S,)。第63页，课件共83页，创作于2023年2月最大流-最小流定理定理11设f为网络G=(V,E,C)的任一可行流，流量为W，(S，)是分离vs,vt的任一割集，则有W≤C(S,)。定理10(最大流-最小割定理)任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。第64页，课件共83页，创作于2023年2月可行流f是最大流的充分必要条件是不存在从vs到vt

的关于f的一条可增广链。

定义22容量网络G，若为网络中从vs到vt的一条链，给定向为从vs到vt，上的弧凡与方向相同的称为前向弧，凡与方向相反的称为后向弧，其集合分别用和表示。f

是一个可行流，如果满足：

则称为从vs到vt

的关于f的一条增广链即中的每一条弧都是非饱和弧即中的每一条弧都是非零流弧推论第65页，课件共83页，创作于2023年2月求最大流的标号算法

设已有一个可行流f，标号的方法可分为两步：第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿可增广链调整f以增加流量。

从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。第66页，课件共83页，创作于2023年2月一、标号过程：1．给发点vs

标号（0，+∞）。2．取一个已标号的点vi，对于vi一切未标号的邻接点vj

按下列规则处理：（1）如果边，且，那么给vj

标号，其中：（2）如果边，且，那么给vj

标号，其中：

3．重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。第67页，课件共83页，创作于2023年2月二、调整过程设1．令

2．去掉所有标号，回到第一步，对可行流重新标号。第68页，课件共83页，创作于2023年2月例：求下图所示网络中的最大流，弧旁数为(3,1)v2v1v4vsvtv3(5,5)(5,1)(2,1)(5,4)(2,2)(5,5)(1,1)(2,0)第69页，课件共83页，创作于2023年2月例：求下图所示网络中的最大流，弧旁数为(3,0)v2v1v4vsvtv3(3,3)(5,1)(2,1)(4,3)(2,2)(5,3)(2,1)(1,1)第70页，课件共83页，创作于2023年2月例14求下图所示网络中的最大流，弧旁数为(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)图8-40第71页，课件共83页，创作于2023年2月解.用标号法。1.标号过程。1）首先给vs标号（0，+∞）2）看vs:在弧(vs,v1)上,fs2=2<cs2=4,具备标号条件。故给v2标号(+vs,δv2),其中δv2=min[(cs2-fs2),

δvs]=min[2,+∞]=4.3）看v2:在弧(v2,v5)上,f25=0<c25=3,具备标号条件。故给v5标号(+v2,2),其中δv5=min[3，2]=2.….

vt类似前面的步骤，可由v4得到标号[+v4，2]由于vt已得到标号，说明存在可增广链，所以标号过程结束。第72页，课件共83页，创作于2023年2月(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)（△，+∞）（-v5

，2）（+v1

，2）（+v4

，2）（+v2

，2）（+vS

，1）（+vs

，2）图8-41第73页，课件共83页，创作于2023年2月2.转入调整过程令δ=δvt=2为调整量，从vt点开始，由逆可增广链方向按标号［+v4,2］找到点v4,令f4t′=f4t+2。再由v4点标号［+v1,2］找到前一个点v1，并令f14′=f14+2。按v1点标号找到点v5，由于标号为-v5,(v5,v1)为反向边，令f15′=f15-2。由v5点的标号再找到v2，令f25′=f25+2。由v2点找到vs，令fs2′=fs2+2。调整过程结束，调整中的可增广链见图8-41中的粗线边，调整后的可行流见图8-42第74页，课件共83页，创作于2023年2月（△，+∞）（+vS

，1）图8-42(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)重新开始标号过程，寻找可增广链，当标到v3点为［+vs,1］以后，与vs,v3点邻接的v1,v2,v6点都不满足标号条件，所以标号过程无法再继续，而vt点并未得到标号，如图8-42。这时W=fs1+fs2+fs3=f4t+f5t+f6t=11，即为最大流的流量，算法结束。第75页，课件共83页，创作于2023年2月本章内容图与网络的基本知识树最短路问题最大流问题最小费用流问题第76页，课件共83页，创作于2023年2月§5最小费用流问题

最小费用流问题的一般提法：已知容量网络G=(V,E,C)，每条边(vi,vj)除了已给出容量cij外，还给出了单位流量的费用dij(≥0)，记G=(V,E,C,d)。求G的一个可行流f={fij}，使得流量W(f)=v，且总费用最小。d(f)=∑(vi,vj)∈Edijfij特别地，当要求f为最大流时，此问题即为最小费用最大流问题。最小费用流问题的常用算法有两种：原始算法；(2)对偶算法。下面只介绍第