第九章 图与网络优化
§9.1 重点、难点提要
一、图与网络的基本概念
1．无向图
设V是一个有n个顶点的非空集合：V?{v1,v2,?,vn}；E是一个有m条无向边的集合：E?{e1,e2,?,em}，则称V和E这两个集合构成了一个无向图，记为G?(V,E)。
，并称uE中任一条边e若连接顶点u和v，则记该边为e?[u,v]（或[v,u]）与v为无向边e的两个端点，且边e与顶点u及v相关联，顶点u和顶点v相邻。对于图G，顶点集V和无向边集E也可以分别表示为V(G)和E(G)。
一般用|V|和|E|表示图中顶点个数和边的条数。
无向图中有平行边、简单图、完备图、子图、生成子图、导出子图、链、初等链、回路、连通图、割边、赋权连通图和网络等基本概念。其中赋权连通图是网络优化考虑的一个重要对象。根据实际问题的需要，每条边的权重可以是时间、距离、成本等相应的数值。
2．有向图
设V是一个有n个顶点的非空集合：V?{v1,v2,?,vn}；E是一个有m条弧的集合：E?{e1,e2,?,em}，则称V和E这两个集合构成了一个有向图，记为
D?(V,E)。
有向图中有弧、入度、出度、平行边、孤立点、简单图、完备图、基本图、子图、导出子图、导出生成子图、同构图、链、初等链、路、路径、回路、赋权有向图和网络等基本概念。和赋权连通图一样，赋权有向图也是网络优化研究的一个重要对象。
3．图的矩阵表示
(1) 无向图的关联矩阵和邻接矩阵
设G?(V,E)为一个无向图，其中V??v1,v2,?,vn?，E??e1,e2,?,em?，图
G的关联矩阵为A?aij??n?m，其中
?1vi与ej关联aij???0vi与ej不关联
关联矩阵描述的是无向图顶点与边的关联状态。
1
图G的邻接矩阵为B??bij?n?n，其中
?1vi与vj间有边相连bij??
0v与v间没有边相连ij?邻接矩阵描述的是无向图顶点间的邻接状态。
无向图的关联矩阵和邻接矩阵有如下特点：
（i）无向图的关联矩阵A的第i行各元素之和为与顶点vi关联的边的数量，而A的任何一列元素之和总是2；
（ii）无向图的邻接矩阵B为一个对称矩阵。 (2) 有向图的关联矩阵和邻接矩阵
设D?(V,E)为一个有向图，其中V??v1,v2,?,vn?，E??e1,e2,?,em?，同样可以构造D的一个关联矩阵A??aij?n?m和邻接矩阵B??bij?n?n，其中
?0顶点vi和弧ej不关联?aij??1顶点vi为弧ej的起点，
??1顶点v为弧e的终点ij?bij为以顶点vi为起点，以顶点vj为终点的弧的数量,
有向图的关联矩阵和邻接矩阵有如下特点：
（i）有向图的关联矩阵A的第i行非零元素的个数为与顶点vi关联的弧的数量，而A的任何一列元素之和总是0；
（ii）有向图的邻接矩阵B不一定对称；
（iii）有向图的邻接矩阵B的第i行各元素之和为以顶点vi为起点的弧的数量，第j列各元素之和为以顶点vi为终点的弧的数量。 二、常见的网络优化问题
1、最小支撑树问题
树是图论中最简单但却十分重要的图。我们通常需要在一个网络中用最短的线路连通若干个固定顶点，例如铺设各种管道、规划交通网络、架设通讯线路等，这就是最小支撑树问题。最小支撑树在自然科学和管理科学中的许多领域有着广泛的应用。
(1)树和有向树
树是一种特殊的无向图，也称为无向树，要求图中无回路并且连通，树一般用T表示。
2
结论1：如果T?(V,E)是一棵树，且|V|?n,|E|?m，则下列命题等价。 （1）T连通且无回路；
（2）T无回路且只有n?1条边，即m?n?1； （3）T连通且只有n?1条边；
（4）T无回路，但在不相邻的任意两个顶点之间加上一条边，恰好得到一个回路；
（5）T连通，但去掉T的任何一条边，T将不再连通； （6）T的任意两个顶点之间有且仅有一条初等链。 (2)支撑树
支撑树——若T是无向图G的生成子图，并且T同时又是树，则称T是G的支撑树，也称为生成树。
结论2 图G?(V,E)有支撑树的充分必要条件是G为连通图。 (3)最小支撑树
给定一个网络G?(V,E,w)，设T?(V,E1)是G的支撑树，称T中所有边的权数之和为树T的权，记为w(G)，即
w(T)?e?E1?w(e)
如果G的支撑树T*?(V,E*)满足
w(T*)?minw(T)或?w(e)?min?w(e)
E1e?E*E1e?E1则称T*为G的最小支撑树，简称最小树。
对于一个连通的网络，如何寻找或构造一个最小支撑树，通常称为最小支撑树问题。
2、最短路问题
最短路问题是网络优化中十分常见的，可以解决许多诸如管道铺设、线路安排、运费最小、运输时间最短等实际问题。
对于一个赋权有向图D?(V,E)，V?{v1,v2,?,vn}，w(vi,vj)?wij。若Q为一条顶点u至v的有向路径，则称w(Q)??w(e)为路径Q的长度。由于顶点u至
e?Qv的有向路径不一定是唯一的，因此一定存在一条有向路径Q*，使得
3
w(Q*)?min{w(Q)|Q为u至v路径}
我们称Q*为顶点u至v的最短路径，w(Q*)为顶点u至v的最短路径的长度，并记为d(u,v)。
求一个赋权有向图中最短路径的问题称为最短路问题。根据不同的目的，求最短路通常使用Dijkstra算法、逐次逼近算法、Floyd算法等方法。
3、最大流问题
网络中的流量应用广泛，如交通系统中的车流、供水、供电系统中的水流、电流、经济中的现金流、供应链系统中的物流、控制系统中的信息流等问题都与网络中的流量有关。通常人们需要知道在一个既定网络中能通过的最大流量，这就构成了最大流问题。
(1) 基本概念
容量网络——设D?(V,E)为一个赋权有向连通图，每条弧的非负权重cij为该弧的最大流容量。如果D中仅有一个入度为0的顶点vS和一个出度为0的顶点vT，则称D为一个容量网络或运输网络。其中称vS为源，称vT为汇，称其余顶点为中间点。容量网络一般记为D?(V,E,C)，其中C为弧的最大流容量集合。
由于在一个容量网络中，每条弧都有容量限制，因此在整个网络中的流必然受到一定限制，如果假设fij表示弧(vi,vj)上的流量，则fij必须受到如下约束：
（1）容量限制条件：对D中的任意一条弧vij,0?fij?cij；
（2）平衡条件：对D中的任意一个中间点vi,要求?fij??fki,即中间点
jk的总流入量和总流出量相等,净流量(流出量与流入量之差)为零；
对源和汇,要求?fSj??fkT,即从源发出的流量必须与汇接受到的流量相
jk等。
可行流——满足以上两个条件的流量fij的集合称为一个可行流，记为
f?{fij}。显然可行流一定存在。最大流问题就是在一个容量网络中寻找流量最大的可行流。
4