《数学建模与数据学实验》课件第6章.ppt

1)中心问题

公共服务设施的选址需要距网络中最远的被服务点距离尽可能小，如应急服务设施、消防中心等。

【例6.15】某城市要建一个急救中心，为城市所属的7个区服务，如图6.24所示,需要建在哪个区才能使它距最远的区的路径最短？图6.24急救中心图图6.25采矿绕路图图6.26欧拉图6.4网络最大流、最小流问题

6.4.1基本概念及定理

定义6.14D=(V，E)是一有向图，D中给定两点，一个点称为源或出发点，记为s，另一点称为汇或者收点，记为t。边e上的权c(e)≥0，称为边e的容量，并称该有向

加权图为容量网络，可记为D=(V，E，c(e))。6.4.2解最大流问题的方法：Ford和Fulkerson标记法

标记法的基本思路：从已知的可行流f（如零流）开始，寻求f可增长路径，若不存在，则现行流即最大流，否则可以按照定理6.12证明中的必要性方法对f进行改进，得到新的流量更大的流f，再重复上述过程。N中的f非饱和树T是满足如下两条件的树：（1）s∈V(T)；（2）对T中的每个顶点v，在T中s到v的唯一路径P(s，v)是一条f非饱和路径。寻求f可增长路径的过程就是在N中生长f非饱和树的过程，而非饱和树的生长和记录，由一个标号过程来实现，标号点的扩展可采用广探法。非饱和树每增加一个顶点v，就给v三个标记：（1）v的父亲点（可以记录树）；（2）连接v与v的父亲的边在非饱和路径P（s，v）中是正向弧（用“+”）或反向弧（用

“－”）；（3）这条边上能增加（或减少）的流值l(v)=

l［P(s，v)］。6.4.3最小费用流及相关解法

前面讨论的网络流仅限于可行流的条件下，如何确定流的路径，使从发点s到收点t的流量达到最大。本节所探讨的问题不仅保证网上的流达到预定效果（最大或者一定程度），而且要使运输流的费用达到最小，这就是最小费用流问题，即最大流问题的扩展。此时网络上任何一个边上都有两个参数：允许流量通过的最大值（边的容量）和通过单位流量时需要的费用。图6.28例6.18图(3)度数约束生成树问题。

生成树在计算机和通信网络中有许多应用，其中的大多数问题对于某些定点的度数有限制。如一个顶点可以表示一个中央计算设备，其他顶点表示连接在中央计算设备上面的各个终端，它们通过电缆与中央设备连接，如何设计才能使中央计算设备与终端连接起来，使用电缆尽可能少的问题，可以利用以上的两种算法进行解决（若只有一个顶点受约束，则容易得到时间多项式算法）。(4)最佳通信生成树。

已知一个n个顶点的图和顶点间的需求r(x，y)，这些可代表电话呼叫。设计一个生成树，使得在所有生成树中通信费用最少。通信费用C(T)的定义为



其中d(x，y)为树T中x与y之间的长度。6.3最短路径问题

在所有图类问题的最优化中，路径问题是得到最广泛研究且有了一定成果的问题之一，这类问题经常在交通、通信、工程规划和决策等方面中遇到，一般的最短路径问题会在赋权图中进行讨论，本节仅将传统的典型算法及相关应用作为这方面的基础,一一向大家说明。6.3.1解最短路径问题的基本方法

在赋权图G=(V，E)中指定的一对顶点vi、vj间众多的路中寻找一条权和最小的路，这样的路称为从vi到vj的最短路。常见的最短路径问题有以下几个类型：①两指定点间的最短路径；②图中各顶点间的最短路径；③某指定点到其他所有顶点间的最短路径；④两个指定顶点之间通过某指定点的最短路径；⑤第2条、第3条、…、第k条最短路径等等问题。1.固定起点的最短路径问题

此问题的解决有一个较好的方法——1959年由Dijkstra提出的算法。该算法不仅可以求出v1到vn的最短路径，实际也求出了v1到其余各顶点的最短路径。

Dijkstra算法的基本思想是生长一棵以v1为根的最短树，在这棵树上每一顶点与根之间的路径皆为最短路径。最短路径的生长过程中各顶点将按照距v0的远近以及顶点的相邻关系，依次加入树中，先近后远，直到所有的顶点均在树中。Dijkstra算法是一种标号法：给赋权图的每一个顶点记一个数，称为顶点的标号（临时标号，简称T标号）或固定标号（简称P标号）。T标号表示从始顶点到这个顶点的最短路长的上界；P标号表示从始顶点到这个顶点的最短路长。图6.19赋权图G解（1）给顶点v1标P标号0，并用方框把0框起来，给与顶点v1相邻的顶