----第六章 网络规划及网络分析.ppt

第六章 网络规划与网络分析 内 容 6.1 图与网络 例6-1由点及不带箭头的连线所组成的图形。 例 6-2 由点及带箭头的连线所组成的图形。 一、无向图 （2）简单图 次为 1 的点-----悬挂点，连接悬挂点的边------悬挂边。 次为0的点----孤立点。 次为奇数的点-----奇点，次为偶数的点------偶点。 定理 6-1 任何图G =（V,E）中，所有点的次数之和等于边数的2倍。即 证：由于每条边必有两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数之和等于边数的2倍。 定理 6-2 任何图G =（V,E）中，奇点的个数必为偶数。 证：设图 中奇点与偶点的集合分别为V1和V2， （4）链 链：对于无向图G =（V,E）, 称顶点和边交替的序列 二、有向图 （1）有向图 有向图是一个有序二元组（V,A），记为D（V,A），其中 （2）简单有向图 两个端点重合的弧称环。如图 6-4 中的a1 . （3）点的出次和入次 以点v为起点的弧数叫做点v的出次，记作 以点v为终点的弧数叫做点v的入次，记作 三、网络 图的矩阵表示方法： 权矩阵 ：在图G=(V,E) 中，V=(v1,v2,…,vp),E=(e1,e2 ,…,eq), 其边[vi,vj]有权wij。构造一个矩阵 ，其中 则称A为G的权矩阵。 6.2 树 6.2.1 树的基本概念与性质 定理 6-4 图G=(V,E)有生成树的充分必要条件为 G是连通图 。 6.2.2 最小支撑树及其算法 2）避圈法 避圈法思路：将不连通的无圈图通过边的增加，逐步变成连 通无圈图。 避圈法步骤： 为连通图。 步骤1 始取 ； 步骤 2 若Gk 连通，则Gk为支撑树；若Gk不连通，任选图G边集E中的一边e，使e的两个端点分属两个不同的连通分图，得 ， ； 步骤 3 若 ，则重复步骤 2；否则，Gk一定是支撑树。 将支撑树的构造与边权的选择结合，产生最小树的概念。 （2）最小支撑树定义 设有一个连通图G=(V,E),每一边e=[vi,vj]有一个权w(e)=wij，如果是的一个支撑树，称中所有边的权之和为支撑树的权，记为： 如果支撑树T*的权W(T*)是G的所有支撑树中权数最小的，则称T*是G的最小支撑树（也称最小树），即 （3）寻找最小支撑树的算法 寻找最小支撑树也可以用上面介绍的破圈法和避圈法，但要在舍边和增边时，增加一些边的权数的限制。 1）破圈法 步骤：从图G中任取一圈，去掉这个圈中权数最大的一条边，得一支撑子图G1。在G1中再任取一圈，再去掉圈中权数最大的一条边，得G2 。如此继续下去，一直到剩下的子图中不再含圈为止。该子图G1就是的最小支撑树T* 。 2）Kruskal算法（避圈法） 1956年 基本思想---每次将一条权最小的弧加入子图T 中，并保证不形成圈。即按照边长由小到大排序，如果当前弧加入后不形成圈，则加入这条弧。当弧有n-1条 时，即为最小树。 例6-4 用Kruskal算法求解下图(6-8)所示网络的最小树，每 条边上的数表示该边的权值。 3）Prim算法(边割法) 1957年 Prim算法： 步骤0 从图中任选一点vi，让vi∈S，图中其余点均包含在 中； 步骤2 从S和 之间的连线中找出最小边，这条边一定包含在 最小支撑树内，不妨设最小边为[vi, vj]，将[vi, vj]标记成 最小支撑树内的边； 步骤3 令 ， ； 步骤4 重复步骤2、步骤3，一直到图中所有点均包含在S中 为止。 例题6-5 用Prim算法求解图6－9（a）中的最小树。 解：求解结果见图6－9（b） 例6-６在一个地区有一个公共服务机构，如飞机场、医院等，图6－1