1、图与网络分析图与网络分析(Graph Theory and Network Analysis)图与网络的基本知识图与网络的基本知识最短路问题最短路问题树及最小树问题树及最小树问题最大流问题最大流问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城哥尼斯堡（现名加里宁格勒）是欧洲一个城市，市，PregeiPregei河把该城分成两部分，河中有两个小河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处当时人们提出这样的问题：有没有办法从某处（如（如A A）出发，经过各桥
2、一次且仅一次最后回到）出发，经过各桥一次且仅一次最后回到原地呢？原地呢？BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题引论引论 图的用处图的用处 某公司的 组织机构设置图总公司总公司分公司分公司工厂或工厂或办事处办事处一、一、图与网络的基本知识图与网络的基本知识（一）、（一）、图与网络的基本概念图与网络的基本概念 EADCB 1、一个图是由点和连线组成。（连线可带箭头，也可、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）不带，前者叫弧，后者叫边）v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例 654321,vvvvvvV ,10
3、987654321eeeeeeeeeeE，,211vve ,212vve ,323vve ,434vve ,315vve ,536vve ,537vve ,658vve ,669vve ,6110vve 图图1一个图是由点集一个图是由点集 和和 中元素的无序对的一个中元素的无序对的一个集合集合 构成的二元组，记为构成的二元组，记为G G=(=(V V，E E)，其中其中V V中的中的元素元素 叫做顶点，叫做顶点，V表示图表示图G 的点集合；的点集合；E中的元素中的元素 叫叫做边，做边，E 表示图表示图G的边集合。的边集合。keE jvkeV jvV 2 2、不带箭头的连线叫做边。如果一个图是由
4、点和边所构成的，、不带箭头的连线叫做边。如果一个图是由点和边所构成的，则称其为无向图，记作则称其为无向图，记作G G=(=(V V，E E)，连接点的边记作连接点的边记作 v vi i,v vj j，或或者者 v vj j,v,vi i。3 3、若点与点之间的连线有方向，称为弧。如果一个图是由点、若点与点之间的连线有方向，称为弧。如果一个图是由点和弧所构成的，那么称它为有向图，记作和弧所构成的，那么称它为有向图，记作D D=(=(V,AV,A)，其中其中V V 表示有表示有向图向图D D 的点集合，的点集合，A A 表示有向图表示有向图D D 的弧集合。一条方向从的弧集合。一条方向从v vi
5、i指向指向v vj j 的弧，记作的弧，记作(v vi i,v vj j)。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 4 4、一条边的两个端点是相同的、一条边的两个端点是相同的,那么称这条边是环。那么称这条边是环。5 5、如果两个端点之间有两条以上的边，那么称它们为、如果两个端点之间有两条以上的边，那么称它们为多重边。多重边。6 6、不含环和多重边的图称为简单图；有多重边的图称、不含环和多重边的图称为简单图；有多重边的图称为多重图。为多
6、重图。7、每一对顶点间都有边相连的无向简单图称为完全图。、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。向边的简单图。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 次为零的点称为弧立点，次为次为零的点称为弧立点，次为1 1的点称为悬挂点。悬挂的点称为悬挂点。悬挂点的关联边称为悬挂边。次为奇数的点称为奇点，次为偶点的关联边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。数的点称为偶点。8 8、以点、以点v v为端点的边的个数称为点为端点的边的个数称为点v v 的
7、次，记作的次，记作 。)(vd图中图中 d(v1)=4，d(v6)=4（环计两次环计两次）定理定理1 1 所有顶点次数之和等于所有边数的所有顶点次数之和等于所有边数的2 2倍。倍。在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。所有顶点的入次之和等于所有顶点的出次之和。所有顶点的入次之和等于所有顶点的出次之和。有向图中，以有向图中，以 v vi i 为始点的边数称为点为始点的边数称为点v vi i的出次，用的出次，用 表示表示 ；以；以 v vi i 为终点的边数称为点为终点的边数称为点v vi i 的入次，的入次，用用 表示；表示；v vi i 点的出次和入次之和就是该点的次
8、。点的出次和入次之和就是该点的次。)(ivd)(ivd 如果如果V V,E E，称，称G是是G的子图；如果的子图；如果V=V,E E，称称G 是是G的生成子图或支的生成子图或支撑子图。撑子图。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图支撑子图在实际应用中，给定图中每条边在实际应用中，给定图中每条边 ，对应，对应一个数一个数 ，称之为，称之为“权权”。通常把这种赋权的图称。通常把这种赋权的图称为网络。为网络。),(jivvjiw 10
9、 10、由两两相邻的点及其相关联的边构成的点边序列、由两两相邻的点及其相关联的边构成的点边序列称为链。称为链。如如:v v0 0 ，e e1 1，v v1 1，e e2 2，v v2 2，e e3 3 ，v v3 3,v,vn-1n-1,e en n ，v vn n，e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10 11 11、图中任意两点之间均至少有一条链相连，则称此、图中任意两点之间均至少有一条链相连，则称此图为连通图。图为连通图。其链长为其链长为 n，其中其中 v0，vn 分别称为链的起点和终点分别称为链的起点和终点 。所含的点、边均不相同的链称为初等链。起点和终点是同
10、所含的点、边均不相同的链称为初等链。起点和终点是同一个点的链称为圈。一个点的链称为圈。（二）、（二）、图的矩阵表示图的矩阵表示对于网络（赋权图）对于网络（赋权图）G=（V，E），其中边其中边有权有权 ，构造矩阵，构造矩阵 ，其中：，其中：称矩阵称矩阵A A为网络为网络G G的权矩阵。的权矩阵。),(jivvjiw EvvEvvwajijijiji),(0),(nnjiaA )(nnjiaA )(EvvEvvajijiji),(0),(1 设图设图G=（V，E）中顶点的个数为中顶点的个数为n，构造一个构造一个矩阵矩阵 ，其中：，其中：称矩阵称矩阵A A为网络为网络G G的邻接矩阵。的邻接矩阵。6
11、54321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 例例权矩阵为：权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437654321654321 030303302004020576305020007204346040vvvvvvvvvvvvA 二、二、树及最小树问题树及最小树问题 已知有六个城市，它们之间已知有六个城市，它们之间 要架设电话线，要求任意要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。两个城市均可以互相通话，并且电话线的总长度最短。v1v2v3v4v5v6 1
12、1、一个连通的无圈的无向图叫做树。、一个连通的无圈的无向图叫做树。树中次为树中次为1 1的点称为树叶，次大于的点称为树叶，次大于1 1的点称为分支点。的点称为分支点。树树 的性质：的性质：（1 1）数必连通，但无回路（圈）。数必连通，但无回路（圈）。（2 2）n 个顶点的树必有个顶点的树必有n-1 条边条边。（3 3）树树 中任意两个顶点之间，恰有且仅有一条链（初中任意两个顶点之间，恰有且仅有一条链（初等链）。等链）。（4 4）树）树 连通，但去掉任一条边，连通，但去掉任一条边，必变为不连通。必变为不连通。（5 5）树树 无回路（圈），但不相邻的两个点之间加一条无回路（圈），但不相邻的两个点之
13、间加一条边，恰得到一个回路（圈）。边，恰得到一个回路（圈）。v1v2v3v4v5v6 2 2、若图若图G=(V,E)的生成子图是一个树的生成子图是一个树,那么称那么称该树该树 是是G 的一个生成树（支撑树），或简称为图的一个生成树（支撑树），或简称为图G 的树。图的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。中属于生成树的边称为树枝，不在生成树中的边称为弦。一个图一个图G 有生成树的充要条件是有生成树的充要条件是G 是连通图。是连通图。v1v2v3v4v5v1v2v3v4v5（一）（一）破圈法：在图中任选一个圈，从这个圈破圈法：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中
14、重复这个步骤，中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。直到得到一不含圈的图为止。用破圈法求出下图的一个生成树。用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8（二）（二）避圈法：开始选一条边，以后每一步中，避圈法：开始选一条边，以后每一步中，总从未被选取的边中选出一条与已选边不构成总从未被选取的边中选出一条与已选边不构成圈的边，重复这个过程，直到不能进行为止。圈的边，重复这个过程，直到不能进行为止。v1v2v3v4v5v6v1v3v1v3v2v1v
15、3v2v5v6v1v3v2v5v6v4v1v3v2v5根据破圈法和避圈法两种方式得到了根据破圈法和避圈法两种方式得到了图的两个不同的生成树，由此可以看到连图的两个不同的生成树，由此可以看到连通图的生成树不是唯一的。通图的生成树不是唯一的。3 3、最小生成树问题、最小生成树问题 一棵生成树所有树枝上权的总和为这个生成树一棵生成树所有树枝上权的总和为这个生成树的权的权。具有最小权的生成树，称为最小生成树。具有最小权的生成树，称为最小生成树。求赋权图求赋权图G G的最小支撑树的方法也有两种，的最小支撑树的方法也有两种，“破破圈法圈法”和和“避圈法避圈法”。破圈法破圈法：在原图中，任：在原图中，任选一
16、个圈，从圈中去掉选一个圈，从圈中去掉权最大权最大的一条边。在余的一条边。在余下的图中重复这个步骤，下的图中重复这个步骤，直到得到一不含圈的图直到得到一不含圈的图为止。为止。655172344v1v2v3v4v5v6总造价总造价=1+4+9+3+17+23=57=1+4+9+3+17+23=57v1v2v3v4v514231352 避圈法避圈法：开始选一条：开始选一条权最小权最小的边，以后每一步中，的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。边不构成圈的边。某六个城市之间的道路网如图某六个城市之间的道路网如图 所示，
17、要求沿着已知所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度的道路联结六个城市的电话线网，使电话线的总长度最短。长度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v61234最短路的一般提法为：设最短路的一般提法为：设 为连通图，为连通图，图中各边图中各边 有权有权 （表示表示 之间没之间没有边），有边），为图中任意两点，求一条路为图中任意两点，求一条路 ，使它，使它从从 到到 的所有路中总权最短。即：的所有路中总权最短。即：最最小。小。),(EVG j il jiltsvv,sv),(jivvjivv,tv ),()(jivvjilL(一一)、狄克
18、斯彻、狄克斯彻(DijkstraDijkstra)算法算法适用于适用于w wijij00，给出了从，给出了从v vs s到任意一个点到任意一个点v vj j的最短的最短路。路。三三 、最短路问题、最短路问题算法步骤：算法步骤：1.1.给始点给始点v vs s以以P P标号标号 ，这表示从，这表示从v vs s到到v vs s的最的最短距离为短距离为0 0，其余节点均给，其余节点均给T T标号，标号，。2.2.设节点设节点v vi i为刚得到为刚得到P P标号的点，考虑点标号的点，考虑点v vj j，其中其中 ，且，且v vj j为为T T标号。对标号。对v vj j的的T T标号进行如下修标号
19、进行如下修改：改：3.3.比较所有具有比较所有具有T T标号的节点，把最小者改为标号的节点，把最小者改为P P标标号，即：号，即：当存在两个以上最小者时，可同时改为当存在两个以上最小者时，可同时改为P P标号。若标号。若全部节点均为全部节点均为P P标号则停止，否则用标号则停止，否则用 代替代替v vi i，返返回步骤（回步骤（2 2）。）。0)(svP)(ivTEvvji),()(,)(min)(ijijjlvPvTvT )(min)(iivTvP iv例一：用例一：用DijkstraDijkstra算法求下图从算法求下图从v v1 1到到v v6 6的最短路。的最短路。v1v2v3v4v6
20、v5352242421 解：（解：（1 1）首先给）首先给v v1 1以以P P标号，给其余所有点标号，给其余所有点T T标号。标号。0)(1 vP)6,3,2()(ivTi（2 2）（3 3）330,min)(,)(min)(12122 lvPvTvT550,min)(,)(min)(13133 lvPvTvT3)(2 vP（4 4）413,5min)(,)(min)(23233 lvPvTvT523,min)(,)(min)(24244 lvPvTvT523,min)(,)(min)(25255 lvPvTvT4)(3 vP（5 5）（6 6）544,5min)(,)(min)(35355
21、lvPvTvT5)(4 vP5)(5 vP945,min)(,)(min)(46466 lvPvTvT725,min)(,)(min)(56566 lvPvTvT7)(6 vP（7 7）（8 8）（9 9）（1010）反向追踪得反向追踪得v v1 1到到v v6 6的最短路为：的最短路为：6521vvvvv1v2v3v4v6v5352242421（二）、逐次逼近法（二）、逐次逼近法首先设任一点首先设任一点v vi i到任一点到任一点v vj j都有一条弧。都有一条弧。显然，从显然，从v v1 1到到v vj j的最短路是从的最短路是从v v1 1出发，沿着这条路到出发，沿着这条路到某个点某个点
22、v vi i再沿弧再沿弧(v vi i,v vj j)到到v vj j。则则v v1 1到到v vi i的这条路必然的这条路必然也是也是v v1 1到到v vi i的所有路中的最短路。设的所有路中的最短路。设P P1j1j表示从表示从v v1 1到到v vj j的最短路长，的最短路长，P P1i1i表示从表示从v v1 1到到v vi i的最短路长，则有下列的最短路长，则有下列方程：方程：开始时，令开始时，令 即用即用v v1 1到到v vj j的直接距离做初始解。的直接距离做初始解。min11jiiijlPP ),2,1(1)1(1njlPjj 从第二步起，使用递推公式：从第二步起，使用递推
23、公式：求求 ，当进行到第，当进行到第t t步，若出现步，若出现则停止计算，则停止计算，即为即为v v1 1到各点的最短路到各点的最短路长。长。）（nklPPjikiikj,3,2min)1(1)(1 )(1kjP）（njPPtjtj,2,1)1(1)(1 ）（njPtj,2,1)(1 例二、例二、18v1v2v3v4v52635135211211v6v7v83766 0-5-3 v8-5-55 0 -1 v7-1-1-1 7101 v6-3-31 0 -1 v5-7-7-73 2 0 8v4-2-2-2-2 1-50-3 v3-5-5-5-1 2 06v20000 3-2-10v1P(4)P(
24、3)P(2)P(1)v8v7v6v5v4v3v2v1求图中求图中v v1 1到到各点的最短路各点的最短路 18v1v2v3v4v52635135211211v6v7v837（0，0）（v3，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）例、求：例、求：5 5年内，哪些年初购置新设备，使年内，哪些年初购置新设备，使5 5年内的总费用最年内的总费用最小。小。第第i i年度年度 1 2 3 4 5购置费购置费 11 11 12 12 13设备役龄设备役龄0-1 1-2 2-3 3-4 4-5维修费用维修费用 5 6 8 11 18解：（解：（1）分析：可行的
25、购置方案（更新计划）是）分析：可行的购置方案（更新计划）是很多的，很多的，如：如：1）每年购置一台新的，则对应的费用为：每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=84 2)第一年购置新的，一直用到第五年年底，第一年购置新的，一直用到第五年年底，则总费用为：则总费用为：11+5+6+8+11+18=59 显然不同的方案对应不同的费用显然不同的方案对应不同的费用。（2 2）方法：将此问题用一个赋权有向图来描述，然后求）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。这个赋权有向图的最短路。求解步骤：求解步骤：1 1）画赋权有向图：）画赋
26、权有向图：设设 V Vi i 表示第表示第i i年初，年初，(V Vi i,V Vj j)表示第表示第i i 年初购买新年初购买新设备用到第设备用到第j j年初（年初（j-1j-1年底），而年底），而W Wi i j j 表示相应费用，表示相应费用，则则5 5年的一个更新计划相当于从年的一个更新计划相当于从V V1 1 到到V V6 6的一条路。的一条路。2 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=59 W23=11+5=16 W24=11+5+6
27、=22W25=11+5+6+8=30 W26=11+5+6+8+11=41 W45=12+5=17 W46=12+5+6=23W56=13+5=18 W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31 四、四、最大流问题最大流问题（一）（一）基本概念基本概念1、设一个赋权有向图、设一个赋权有向图G=（V,E）,在在V中指定一个发点中指定一个发点vs和一个收点和一个收点vt,其它的点叫做中间点。对于其它的点叫做中间点。对于D中的每一个中的每一个弧（弧（vi,vj）E,都有一个非负数都有一个非负数cij,叫做弧的容量。我们叫做弧的容量。我们把这样的图把这样的图G叫做容量
28、网络，简称网络，记做叫做容量网络，简称网络，记做G=（V，E，C）。）。网络网络G上的流，是指定义在弧集合上的流，是指定义在弧集合E上的一个函数上的一个函数其中其中f(vi,vj)=fij 叫做弧叫做弧(vi，vj)上的流量。上的流量。),(jijifvvff 2、称满足下列条件的流为可行流：、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（）容量条件：对于每一个弧（vi,vj）E有有 0 fij cij。（2）平衡条件：平衡条件：对于发点对于发点vs，有有对于收点对于收点vt，有有对于中间点，有对于中间点，有 EvvjsjsWf),(WfEvvt jtj ),(EvvEvvi jj
29、ijiijff),(),(可行流中可行流中 fijcij 的弧叫做饱和弧，的弧叫做饱和弧，fijcij的的弧叫做非饱和弧。弧叫做非饱和弧。vsv1v2v4v3vt374556378S),(2vvSs),(431tvvvvS ),(),(,),(,),(),(4232211vvvvvvvvSSs 18567),(23241 lllSSCs 3、容量网络、容量网络G=（V，E，C），），vs为始点，为始点，vt为终点。如果把为终点。如果把V分成两个非空集合分成两个非空集合 使使 ，则所有一点属于，则所有一点属于 ，而而另一点属于另一点属于 的弧的集合，称为由的弧的集合，称为由 决定的割决定的割集集
30、,记作记作 。割集。割集 中所有始点在中所有始点在 ，终点在终点在 的弧的容量之和，称为这个割集的的弧的容量之和，称为这个割集的容量，记为容量，记为 。SS,SvSvts,S),(SS),(SS),(SSCSSSS关于最大流问题的定理：关于最大流问题的定理：最大流最小割定理：任一网络中，最最大流最小割定理：任一网络中，最大流的流量等于最小割集的容量。大流的流量等于最小割集的容量。4、容量网络、容量网络G，若若 为网络中从为网络中从vs到到vt的的一条链，给一条链，给 定向为从定向为从vs到到vt，上的弧凡与上的弧凡与 方向相同的称为前向弧，凡与方向相同的称为前向弧，凡与 方向相反的方向相反的称
31、为后向弧，其集合分别用称为后向弧，其集合分别用 和和 表示。表示。f 是一个可行流，如果满足：是一个可行流，如果满足：则称则称 为从为从vs到到vt 的关于的关于f 的一条增广链。的一条增广链。),(0),(0jijijijijijivvcfvvcf 推论推论 可行流可行流f 是最大流的充分必要条件是不存是最大流的充分必要条件是不存在从在从vs到到vt 的关于的关于f 的一条可增广链。的一条可增广链。2v1v3v4v5v6v7v 13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)7766633232211),(,),(,),(,),(,vvvv
32、vvvvvvvvv ),(),(),(766321vvvvvv ),(23vv 是一个增广链是一个增广链显然图中增广链不止一条显然图中增广链不止一条（二）求最大流的标号法（二）求最大流的标号法 标号过程：标号过程：1 给发点给发点vs 标号（标号（0，+）。）。2 取一个已标号的点取一个已标号的点vi，对于对于vi一切未标号的邻一切未标号的邻接点接点vj 按下列规则处理：按下列规则处理：（1）如果边）如果边 ，且，且 ，那么给，那么给vj 标标号号 ，其中：，其中：（2）如果边）如果边 ，且，且 ，那么给，那么给vj 标标号号 ，其中：，其中：3重复步骤重复步骤2，直到，直到vt被标号或标号过
33、程无法进被标号或标号过程无法进行下去，则标号结束。若行下去，则标号结束。若vt被标号，则存在一条增被标号，则存在一条增广链，转调整过程；若广链，转调整过程；若vt未被标号，而标号过程无未被标号，而标号过程无法进行下去，这时的可行流就是最大流。法进行下去，这时的可行流就是最大流。Evvij),(0 i jf),(jiv ),min(ii jjf Evvji),(ijijcf ),(jiv ),min(ijijijfc 调整过程：调整过程：1令令 2去掉所有标号，回到第一步，对可行流去掉所有标号，回到第一步，对可行流重新标号。重新标号。),(),(),(jijijitjijitjijivvfvvf
34、vvff 求下图所示网络中的最大流，弧旁数为求下图所示网络中的最大流，弧旁数为),(jijifc(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(,+)(vs,4)(-v1,1)(-v2,1)(v2,1)(v3,1)得增广链，标号结得增广链，标号结束，进入调整过程束，进入调整过程(3,3)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)vsv2v1v3v4vt(vs,3)(,+)无增广链，标号结束，得无增广链，标号结束，得最大流。同时得最小割。最大流。同时得最小割。
