1、第七章 网络规划第七章 网络规划第七章 网络规划第一节：现实中的网络规划问题第二节：图的基本概念 第三节：树 第四节：最大流问题 第五节：最短路径问题 第六节：最小费用最大流问题第七节：网络规划的应用7.1现实中的网络规划问题 许多工程和管理的问题都可以用图与网络来描述，图与网络优化 问题是一类应用十分广泛的问题。图与网络优化是线性规划等理论和算法在具有图结构的问题中的应用。由于图与网络问题具有 特殊的结构，相应的优化算法 也不同于一般的单纯形算法，具有其独特的直观和简捷的特点。哥尼斯堡七桥问题 尼斯堡城有条河流，河中有两个小岛，河上共有七个桥，如图 71 。当地居民考虑这样一个问题：能否从某
2、个地点（任意点）出发经过七个桥，且每个桥只经过一次，最后回到出发地点。 图 7-1.哥尼斯堡七桥问题哥尼斯堡七桥问题 欧拉在 1736年发表了图论方面的第一篇论文，解决了哥尼斯堡的七桥问题。欧拉将此问题归结为图 72 所示的一笔画问题。也就是能否从某一点开始，不重复地一笔画出这个图形，最后回到原来出发点。 BAC D图 7-2.一笔画问题欧拉证明了这是不可能完成的。因为图形中的每个点都与奇数个线相关联，不可能将这样的图形不重复地一笔画出来，这是古典的图论中的一个著名问题。 7.2 图的基本概念 7.2.1图 : 由节点（ Node）和边（ Edge）组成。节点和边是图中最基本的概念，我们不对其
3、作出定义。图 7-3的图中，有 4个节点， 7条边，每一条边都与 2个节点对应。因此，一条边可以用它的两个节点来标记。图 7.3中的边，可以记为 v1， v2， v1， v3， v2， v3， v3， v2， v2， v4， v3， v4， v4， v1。 v3 v1 v4 v2 e1e2e3 e4e5e6图 7-3. 无向图图的定义 定义 设 V= v1， v2， ， vm表示节点的集合， E= e1， e2， ， en表示边的集合，若对任一 ekE，均有 vi， vjV与之对应，则称 VE为 图 ，记为 G=(V， E)。 称 vi为 G的 顶点 ， ek为 G的 边 ，记为 ek=vi，
4、 vj= vj， vi。称 vi， vj为 ek的 端点 ， ek为 vi， vj的 关联边 。称 vi， vj为 邻接点 。 将图 7.3用数学定义表示如下： G=(V， E) V= v1， v2， v3， v4 E= e1， e2， e3， e4， e5， e6， e1， e2， e3， e4， e5， e6， e7=v1， v2， v1， v3， v2，v3， v3， v2， v2， v4， v3， v4， v4， v1 相关定义 如果图中一个边的两个端点为同一个点，称这样的边为 环 。如果两个点之间存在两个以上的边，称为 多重边 。 一个没有环、也没有多重边的图，称为 简单图 。无环
5、,允许有多重边的图称为 多重图 。本章讨论的图主要是指简单图。 图中的边是对节点的关系描述，所以我们讨论的图如果关系表示的相同，不论图的形状如何，我们认为这样的图都是相同的。 次 : 以点 v为端点的边的个数称为 v的次， 表示为 : d(v)。 悬挂点 : 次为 1的点。 悬挂边 : 悬挂点的关联边。 孤立点 : 次为 0的点。 奇点 : 次为奇数的点。 偶点 : 次为偶数的点。两个定理 定理 7-1: 图 G=(V,E)中 ,所有点的次之和是边数的两倍 , 即 : 证明 :计算各端点的次时，每个边都用了两次，所以次数的总和必然为边数的两倍。 定理 7-2: 任意一图中 , 奇点的个数为偶数
6、。 证明 :设 V1表示奇点的集合， V2表示偶点的集合。由有： 因为偶点的次之和为偶数，总数为偶数，所以奇点的次之和必须是偶数，只有偶数个奇数之和才能是偶数。所以奇点的个数必然为偶数个。相关定义 链 ： 点边交错系列， 记为： 如果满足 ，一般简记为： 圈 ： 的链。 初等链 ： 点 均不相同。 初等圈 ：点 均不相同。 简单链 ：链中边均不相同。 简单圈 ：圈中边均不相同。 连通图 ： 任意两点之间至少有一条链。否则称为 不连通图。 连通分图 ： 对不连通图，每一连通的部分称为一个连通分图。 支撑子图 ： 对 G=（ V， E），若 G=(V,E), 使 V=V, E E, 则 G是 G的一个支撑子图（生成子图）
