图与网络.docx
《图与网络.docx》由会员分享，可在线阅读，更多相关《图与网络.docx（14页珍藏版）》请在冰点文库上搜索。
图与网络
第二讲图与网络分析
图与网络分析部分内容框架
图与网络的基本概念
图与网络分析
图连通图
图的矩阵表示
树与最小树
最短路问题
图论在网络分析的应用最大流问题
最小费用最大流问题
第四章图与网络分析
§1.图与网络的基本概念
一、图及其分类
本章研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有无线连接，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。
下面介绍有关图的基本概念。
1.图，图是点和线所组成的图形，即图是一个有序二元组（V,E），记为G=（V,E），其中V={v1,v2,…vp}是p个点的集合，E={e1,e2,…eq}是q条边的集合。
V中的元素vi称为顶点，E中的元素ek称为边。
如图1所示：
V4
e1
V1
e3
e4
e5
e6
V3
V5
V2
e2
图1
V={v1,v2,v3,v4,v5},E={e1,e2,e3,e4,e5,e6}
其中e1={v1,v1},e2={v1,v2},e3={v1,v3}
e4={v3,v4},e5={v3,v4},e6={v1,v4}
对于边（vi,vj），则称vi,vj两点相邻，也称vi,vj为边（vi,vj）的端点。
若两条边有一个公共端点u，则称这两边是相邻的，也称这两边为点u的关联边。
若两端之间多于一条边的，称为多重边。
如图1中的e4、e5。
若一条边的两个端点相同，则称此为环（自回路）。
如图1中的e1。
2.简单图与多重图，不含环和多重边的图称为简单图，含有多重边的图称为多重图。
上图就是一个多重图。
3.无向图与有向图。
G=（V,E）中，若所有的边均有ek=（vi,vj）=（vj,vi）,k=1,2,…q，则称G为无向图，记为G=（V,E）。
若图中边（vi,vj）的端点是有序的，即表示以vi为始点vj为终点。
则称该图为有向图，记为D=（V,A）。
在有向图中，把边称为弧。
因此，A表示G中弧的集合。
4.顶点的次。
以点v为端点的边数称为点v的次，记为d（v）。
图1中，d（v2）=1,d（v3）=3,d（v1）=5。
次数为1的点称为悬挂点，连结悬挂点的边称为悬挂边。
次数为0的点称为孤立点，如图1中的点v5。
次为奇数的点称为奇点，次为偶数的点称为偶点。
在任何图中，顶点的次数与边数有如下性质：
（1）
（其中p为G中顶点数，q为边数）
（2）次为奇数的顶点必为偶数个。
在有向图D=（V,A）中，以vi为始点的边数称为点vi的出次，记为d+（vi）,以vi为终点的边数称为点vi的入次，记为d-（vi）。
显然d（vi）=d+（vi）+d-（vi）。
且
。
5.网络。
在实际问题中，只用图来描述所研究对象之间的关系往往是不够的。
与图联系在一起的，通常还有与点或边有关的某些数量指标，通常称之为“权”。
权可以表示为：
距离、费用、通过能力（数量）等。
称含有数量指标的赋权图为网络。
与无向图和有向图相对应，网络可分为无向网络和有向网络，分别记为G=（V,E,W）和D=（V,A,W）。
二、连通图
1.链。
在无向图G=（V,E），称一个点和边交替的序列{vi1,ei1,vi2,ei2,…vit-1,eit-1,vit}为连接vi1和vit的一条链。
简记为{vi1,vi2,…vit}。
其中eik=（vik,vik+1）,k=1,2,…t-1。
点边序列中只有重复的点而无重复边者称为简单链。
点边序列中没有重复的点和重复边者称为初等链。
e3
e2
e1
e3
e2
e1
v1v2v1v2
v3
e11
e10
e7
e9
v3
e10
e9
e7
v6
e6
e4
e8
v6
e6
e8
e4
e5
e5
v5v4v5v4
图2图3
如图2中：
S1={v6,v5,v1,v5,v4,v3}是一条连结v6和v3简单链。
S2={v6,v5,v1,v4,v3}是一条条连结v6和v3的初等链。
首尾相接的链称为圈,例如S3={v6,v5,v4,v1,v6}
2.路。
在有向图D=（V,A）中，称链{vi1,vi2,…vit}为一条从vi1到vit的路。
若vi1=vit，则称之为回路。
在图3中S1={v6,v5,v1,v5,v4,v3}是一条从v6和v3的路。
S2={v1,v2,v4,v5,v1}是一条回路。
3.连通图。
如果一个图中任意两点间至少有一条链相连，则称此图为连通图，如图4
4
9
8
7
6
5
v5
v4
v1
3
4
2
v3
v2
图4
三、图的矩阵表示
用矩阵表示图对于研究图的性质及应用常常是较方便的。
图的矩阵表示方法有多种，这里介绍其中两种常用矩阵。
1.权矩阵。
网络G=（V,E,W），其边（vi,vj）的权重为Wij，构造矩阵A=（aij）nxn，其中
称矩阵A为网络G的权矩阵。
其中主对角线上的元素aij均为零。
如图4的权矩阵为
2.邻接矩阵。
对于图G=（V,E）构造一个矩阵A=（aij）nxn，
其中
则称矩阵A为图G的邻接矩阵。
当G为无向图时,邻接矩阵为对称的。
v2v4
v6
v1
v3v5
图5
如图5的邻接矩阵为
给出了一个图的邻接矩阵就等于给出了图的全部信息，我们可以从邻接矩阵中得到图的很多重要性质。
如
（1）A=（aij）中第i行中的1的数目等于vi点的出次d+（vi），第j列中1的数目等于vi点的入次d-（vi）。
（2）路径问题。
如果图5是路径图，则由邻接矩阵就可算出G中任一点与其它点之间是否有路可通？
若有路，走几步可以达到该点？
下面通过邻接矩阵的计算来求解v1v5和v1v6有无路可能。
先求A2
其中
。
可以理解ai1a1j=1时，当且仅当ai1和a1j同时等于1，所以ai1a1j=1表示从vi到vj有一条路，而A2=aij
（2）则表示从vi到vj可两步到达。
a15
（2）=1，说明v1到v5有一条路，可两步到达。
a16
（2）=0，表明v1到v6两步不能到达。
继续计算A3
由于a16（3）=1，表明从v1三步可达v6，若要了解这条路沿途经过哪些顶点到达v6，只要回溯前面计算过程中的a16（3）这个数是怎样产生的，就可知道。
因为a16（3）是由A2中的第一行与A中的第六列相应各数乘加而得，即是由a15
（2）=1和a56=1相乘而得。
同理a15
（2）=1是由a13=1与a35=1相乘而得。
因此有v1v3v5v6。
§2.树与最小树
一、树及其性质
连通且不含圈的无向图称为树，记为T（V,E）。
设图T=（V,E），顶点数为P，边数为q，则以下关于树的说法是等价的。
1.T是一棵树；
2.T无圈，且q=p－1；
3.T连通，且q=p－1；
4.T无圈，但每加一新边即得唯一的一个圈；
5.T连通，但每舍去一边就不连通；
6.T中任意两点，有唯一链相连。
二、图的生成树
子图：
设
是图，若
，且
是图，则称图
是G的生成子图，简称子图。
支撑子图：
若
是
的子图，且
（即点相同），则称G1为G的支撑子图。
若图G的生成子图是一棵树，则称该树为子图G的生成树。
l1
e1
°
°
l6
e6
°
l7
e7
°
°
l2
e4
e2
°
e3
°
°
°
（a）（b）
图6
图6中（b）就是（a）的生成树。
图G=（V,E）有生成树的充要条件是G为连通图。
三、最小树问题
在给定连通赋权无向图G=（V,E,W）中，求G的生成树T=（V,E），使E各边权Wij（0）的总和最小的问题称为最小树问题。
其数学模型为：
（vi,vj）T
其中T*称为最小树。
许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若干城市联通；设计用料最省的电话线网把有关单位联系起来。
求最小树有以下两种方法：
（1）用Prim算法求最小树。
其基本思想是：
开始选一条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选边不构成圈，直至选够q－1条边止。
（2）用Kruskal算法求最小树。
其方法步骤是：
Step1）开始将G的所有各边按权由小到大的次序都排列出来，然后逐边检查。
（注：
对于权相同的边，其先后次序是任意的）；
Step2）首先留下最短的一条边，然后再检查每一条边，若它不与已留下的边形成圈，就留下来，否则就去掉；
Step3）重复Step2），直到所有被留下来的边形成支撑树时，就终止计算。
例求下图中的最小生成树
应用实例：
通信网络的优化设计问题
§3.最短路问题
最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用这个模型，如管道铺设，设备更新，线路安排等。
在第三章我们曾介绍了最短路问题的动态规划解法，但某些最短路的问题构造动态规划基本方程较困难，而图论方法则直观有效。
给定D=（V,A,W），其中wijW，表示弧（vi,vj）的权（可以是费用、时间、距离等）。
设vs和vt是D中任意两顶点，求一条路，使它是从vs到vt的所有路中总权最小的路。
其数学模型为：
一、Wij0情况下，求最短路的Dijkstra标号法
1.该法的基本思想是基于以下原理：
若序列{vs,vi1,…vik,…vt}是从vs到vt的最短路，则序列{vs,vi1,…vik}必为从vs到vik的最短路。
2.Dijkstra标号法的基本思想是采用两种标号：
T标号与P标号，T标号为临时性标号（TemporaryLabel），P标号为永久性标号（PermanentLabel）。
从vs开始，逐步向外探寻最短路。
给vi点P标号时，表示从vs到vi点的最短路权，vi的标号不再改变。
给vi点T标号时，表示从vs到vi点的最短路权上界的估计。
凡没有得到P标号的点都有T标号。
标号法每一步都是把某一T标号点改为P标号，当终点vt得到P标号时，计算全部结束。
如果点vj不能由T标号变为P标号，则说明vs到vj不存在路。
例，用Dijkstra标号法求下图7由v1到各顶点的最短路。
°
2
°
v2v5
3
3
2
1
°
1
1
2
4
°
v1
°
°
2
v3v6
图7
D氏标号法只适用于全部权为非负情况。
如果网络中含有负权的弧，则算法失效，应改用其它算法。
二、求网络中任意两点意最短路的Floyd算法
对求网络中任意两点间的最短路，当然可用改变起始点的办法，采用D氏标号法达到目的，但显然较繁。
Floyd算法却可直接求出网络中任意两点间的最短路，且wij的正负不受限制。
v2
例用Floyd方法求图8中各顶点间的最短路，其中弧（边）旁的数字表示弧（边）长。
3
-4
v3
2
3
3
4
v5
v1
°
-1
9
v4
图8
升级会员 