第4章(三稿)图与网络.docVIP

第4章 图与网络 在我们的日常生活与工程实践中，网络随处可见。电力网把光明和动力送到千家万户和车间；电话网使得我们可以几乎毫不费力地相互交流；高速公路网、铁路网以及航空服务网络使我们能够方便快捷地跨越地理空间去做各种各样的事情；在现代，计算机网络更是对我们的生活和工作产生了深刻的影响；制造与物流网络使我们能够方便地将生活与生产资料运往我们需要的地方。 另一方面，在科学、社会、经济等领域中的很多问题，原本与图或网络无关，但我们可以用网络将其表示出来，并用网络的方法对其求解，比如设施规划、设备更新问题等。 人们总是希望借助已有的网络，以尽可能低的成本将传递物（电力、货物、人员、信息等）从一地（点）运送到另一地（点），或者想知道对于既定的网络，其最大通过能力是多大，或者想知道从一点要到达另外一点，如何选择路线，使总路程最短，所有这些问题都涉及到网络优化问题。 我们通过一个实例来了解一下什么是网络优化。 图4－1为某旅游景区的游览示意图。 图中，点1为景区入口，点6为景区出口，其它节点表示景点，各点之间的连线表示观光车的交通道路，连线旁边的数值为路段的长度。游客从入口进入景区，然后从出口离开，自带车辆不得进入景区，游客在景区内乘坐景区提供的观光车到达各景点。现在有三个问题需要考虑： （1）观光车将游客自入口送到各景点，那么如何选择行车路线，使行程最短？这便是网络优化中的最短路问题。 （2）各景点的计算机自动检票系统是相互连通的，通信光缆沿行车道路铺设，显然并不需要在所有的路段都铺设光缆，而只需在部分路段，比如在（1，2）、（1、3）（2、4）、（2、5）及（4，6）或者在（1，2）、（2，3）、（2，4）、（3，5）及（4，6）铺设光缆即可保持所有景点（包括出、入口）的计算机相互联通。这样便产生一个问题———沿哪些路段铺设光缆，可使光缆总长度最短呢？这便是网络优化中的最小生成树问题。 （3）如果进入景区游客过多，则会对景区的生太系统造成影响，甚至造成游客拥挤而存在安全隐窜。因此在游客高峰时期，景区对每天通过各路段的车辆总数规定了限额（各路段的限额不一定相同），问题是：不突破各路段的限额，每天最多可允许多少车辆从入口运行到出口？这便是网络优化中的最大流问题。 本章中我们除讨论上述三个问题外，还将讨论最小费用流问题。 4.1　图与网络的基本概念 所谓网络，就是边或点上带有权重的图。因此，图是研究网络问题的基础。这一节我们将介绍图与网络的一些基本概念。 定义4.1.1　图 图是由点及连接这些点的边构成的集合。这些点通常称为节点或顶点，节点构成的集合称为图的点集，连接节点的边通常称为边或弧，一般用(i,j)来表示节点i、j间的边。边构成的集合，称为图的边集。通常将图记为，其中，N是点集，A是边集。节点及边的个数分别用及 表示。 图4－2中，，。 这样定义的图，是自然界中各种事物间的关系的一种抽象。图中的节点，很多时候并不表示空间意义上的点，而是表示某种事物；而图中的边，也不只是表示两节点间物理意义上的连接，而更多时候是表示节点所表示的两事物之间的某种关系。如，在体育比赛中，有若干个代表队，有些队之间有比赛，而有些队之间不发生比赛，这样一个比赛程序就可以用图来表示：用节点代表各个队，如果某两队之间有比赛，则在表示这两个队的节点间就有边相连。 定义4.1.2 有向图 在一个图中，如果边是有方向的，则称为有向边。如果图的所有边均为有向边，则称这个图为有向图。相应地，如果一个图的所有边都是无向边，则称该图为无向图。图4－3为一有向图。 有向图中的边一般用带有箭头的线表示，有向边的数学表示中，i表示箭尾，j表示箭头。注意，在有向图中和表示的是不同的边，但对无向边，和表示的是同一条边。 有向图中的有向边，其实反应了事物间关系的一种有序性，或称不可逆性。例如，体育比赛的结果就可以用有向图来表示，如i队胜j队，则在节点i，j间用有向边来表示这种胜负关系。 如，则称节点j与i相邻，并称节点i，j与边关联，或称边与节点i，j关联。 定义4.1.3 节点的次 对于有向边，进入节点i的边的个数称为节点i的入次，记为，离开节点i的关联边的个数称为i的出次，记为。入次与出次之和称为节点i的次，记为。对于无向边，节点的次等于与其关联的边的个数。 图4－3中，节点1的入次为0，出次为2，它的次为2；节点2的入次为2，出次为2，次为4。图4－2中，节点4的次为3。 定义4.1.4 多重边与环 在同一对节点之间有多于一条（同方向）的边，称为多重边；如果一条边的起点与终点为同一节点，则称这样的边为环。 图4－4中，节点2、3之间有同方向的两条边，即为重边，边（7，7）为环。注意，节点3、5之间的两条边不是重边，它们是两条不同的边（3，5）和（5，3）。 含有多重边或环的图称为多