第三部分图与网络分析。
图与网络分析部分内容框架。
图与网络的基本概念。
图连通图。图的矩阵表示。
树与最小树。
最短路问题。
图论在网络分析的应用最大流问题。
最小费用最大流问题。
第四章图与网络分析。
§1. 图与网络的基本概念。
一、图及其分类。
本章研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有无线连接，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。下面介绍有关图的基本概念。
1.图，图是点和线所组成的图形，即图是一个有序二元组(v,e)，记为g=(v,e)，其中v=是p个点的集合，e=是q条边的集合。v中的元素vi称为顶点，e中的元素ek称为边。
如图1所示：
图1v=,e=
其中 e1=,e2=,e3=
e4=,e5=,e6=
对于边(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.图的同构。
v1v4v2v3
ab)上面图(a)与图(b)初看起来似乎是不同的两个图，如果我们正确的确定它们顶点之间的对应关系：
v1 vc,v2 vb,v3 vd,v4 va
那么，它们边与边间的对应关系就有：
v1,v2) (vc,vb),(v1,v3) (vc,vd)(v1,v4) (vc,va),v2,v3) (vb,vd),(v3,v4) (vd,va)。
从以上分析可以得出：图(a)和图(b)实质上是一个图，只不过表现的形式不同。
设图g=(v,e)与g=(v,e)，若它们的顶点存在一一对应，且保持同样相邻关系，则称g和g同构，记为。
5.顶点的次。以点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和vit的一条链。简记为。其中eik=(vik,vik+1),k=1,2,…t-1。
点边序列中只有重复的点而无重复边者称为简单链。
点边序列中没有重复的点和重复边者称为初等链。
v1v2v1v2
v5v4v5v4
图3图4如图3中：s1=是一条连结v6和v3简单链。
s2=是一条条连结v6和v3的初等链。
首尾相接的链称为圈。
2.路。在有向图d=(v,a)中，称链为一条从vi1到vit的路。若vi1=vit，则称之为回路。
在图4中 s1=是一条从v6和v3的路。
s2=是一条回路。
3.连通图。如果一个图中任意两点间至少有一条链相连，则称此图为连通图。
任何一个连通图都可以分为若干个连通子图，每个连通子图称为由原图的分图。图5中的(b)就是(a)的三个分图。
ab)图5图6
三、图的矩阵表示。
用矩阵表示图对于研究图的性质及应用常常是较方便的。图的矩阵表示方法有多种，这里介绍其中两种常用矩阵。
1.权矩阵。网络g=(v,e,w)，其边(vi,vj)的权重为wij，构造矩阵a=(aij)nxn，其中。
称矩阵a为网络g的权矩阵。其中主对角线上的元素aij均为零。
如图6的权矩阵为。
2.邻接矩阵。对于图g=(v,e)构造一个矩阵a=(aij)nxn，其中。
则称矩阵a为图g的邻接矩阵。当g为无向图时，邻接矩阵为对称的。
v2v4v3v5
图7如图7的邻接矩阵为。
给出了一个图的邻接矩阵就等于给出了图的全部信息，可以从邻接矩阵中得到图的很多重要性质。如。
1）a=(aij)中第i行中的1的数目等于vi点的出次d+(vi)，第j列中1的数目等于vi点的入次d-(vi)。
（2）路径问题。如果图7是路径图，则由邻接矩阵就可算出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，则以下关于树的说法是等价的。
是一棵树；无圈，且q=p－1；
连通，且q=p－1；
无圈，但每加一新边即得唯一的一个圈；
连通，但每舍去一边就不连通；
中任意两点，有唯一链相连。
二、图的生成树。
若图g的生成子图是一棵树，则称该树为g的生成树。ab)图8
图8中(b)就是(a)的生成树。
图g=(v,e)有生成树的充要条件是g为连通图。
三、最小树问题。
在给定连通赋权无向图g=(v,e,w)中，求g的生成树t=(v,e)，使e各边权wij(0)的总和最小的问题称为最小树问题。其数学模型为：
vi,vj)t
其中t*称为最小树。
许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若干城市联通；设计用料最省的**线网把有关单位联系起来。求最小树有以下两种方法：
1）用“避圈法”(kruskal算法)求最小树。其基本思想是：开始选一条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选边不构成圈，直至选够q－1条边止。
（2）用“破圈法”(管梅谷算法)求最小树。其方法步骤是：
1°先从图g任取一个圈，并从圈中去掉一条权最大的边。若在同一圈中有几条都是权最大边，则任选其中一边去掉。
2°在余下的子圈中，重复上述步骤，直至没有圈止。
例。§3. 最短路问题。
最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用这个模型，如管道铺设，设备更新，线路安排等。在第三章我们曾介绍了最短路问题的动态规划解法，但某些最短路的问题构造动态规划基本方程较困难，而图论方法则直观有效。
给定d=(v,a,w)，其中wijw，表示弧(vi,vj)的权（可以是费用、时间、距离等）。设vs和vt是d中任意两顶点，求一条路，使它是从vs到vt的所有路中总权最小的路。其数学模型为：
vi,vj)p
一、wij0情况下，求最短路的dijkstra标号法。
1.该法的基本思想是基于以下原理：若序列是从vs到vt的最短路，则序列必为从vs到vik的最短路。
标号法的基本思想是采用两种标号：t标号与p标号，t标号为临时性标号(temporary label)，p标号为永久性标号(permanent label)。从vs开始，逐步向外探寻最短路。
给vi点p标号时，表示从vs到vi点的最短路权，vi的标号不再改变。给vi点t标号时，表示从vs到vi点的最短路权上界的估计。凡没有得到p标号的点都有t标号。
标号法每一步都是把某一t标号点改为p标号，当终点vt得到p标号时，计算全部结束。如果点vj不能由t标号变为p标号，则说明vs到vj不存在路。
运筹学讲义
第六讲排队论。x y zx处填写表示相继到达间隔时间的分布 y处填写表示服务时间的分布 z处填写并列的服务台的数目c.c 1 单服务台，c 1 多服务台。表示相继到达间隔时间和服务时间的各种分布的符号 m 负指数分布。d 确定型。ek k阶爱尔朗分布。gi 一般相互独立的时间间隔的分布。g 一般服务...
运筹学讲义
第三讲整数规划。一 整数规划模型。12年，第一题，15分 一家公司打算在甲地 乙地或甲乙两地新建工厂，一地至多建一个工厂，并且在甲乙两地至多建一个仓库，仓库位置随工厂地点而定 即，如某地有工厂，该地可设仓库或不设仓库 但如该地不设工厂，则该地一定不设仓库 若总资本可用量为20 百万元 其他数据如下表...
管理运筹学 讲义 A
第二章对偶理论与灵敏度分析。duality theory and sensitivity analysis 第一节单纯形法的矩阵描述。用矩阵描述单纯形法求解过程比较简便，也有助于加深对单纯形法的理解。设有线性规划问题，用矩阵形式表示，在约束条件中加入松弛变量，将其化成标准型 式中i为m m的单位阵。...