《图与网络分析》PPT课件

1 第六章图与网络分析 例1 哥尼斯堡七桥问题 2 一 图的概念 1 图 点和线所组成的图形 记为G V E 其中V是点的集合 E是边的集合 2 端点 关联边 联结点vi vj的边记作e vi vj 称vi vj为e的端点 也称e为vi vj的关联边 相邻点 相邻边 具有同一条关联边的点为相邻点 具有公共端点的边为相邻边 4 环 一条边的两个端点相同 则称该边为环 自回路 6 1图与网络的基本概念 3 5 多重边 若两端之间有多于一条边相关联 称这些边为多重边 6 简单图与多重图 不含环和多重边的图称为简单图 无环但含有多重边的图称为多重图 7 次 点v的关联边个数称为点v的次 记作d v 8 悬挂点 悬挂边 称次为1的点为悬挂点 悬挂点所关联的边为悬挂边 4 定理 图G V E 中 所有点的次数之和等于边数的两倍 二 连通图1 链 圈 在无向图G V E 称一个点和边交替的序列 vi1 ei1 vi2 ei2 vit 1 vit 为连接vi1和vit的一条链 简记为 vi1 vi2 vit 其中eik vik vik 1 k 1 2 t 1 点边序列中没有重复的点称为初级链 若链首尾两端点重合 则称为圈 S1 v6 v5 v1 v5 v4 v3 S2 v6 v5 v1 v4 v3 5 2 连通图 如果图 中任意两点间至少有一条链相连 则称此图为连通图 任何一个连通图都可以分为若干个连通子图 每个连通子图称为由原图的分图 6 例2 有5名运动员参加游泳比赛 问如何安排比赛 才能使每位运动员都不连续地参加比赛 7 三 子图 e4 8 四 有向图 1 弧 有向图 带有方向的边称为弧 记作a vi vj 由一些点和弧组成的集合称为有向图 记作D V A A表示G中弧的集合 路 在有向图D V A 中 称链 vi1 vi2 vit 为一条从vi1到vit的路 若vi1 vit 则称之为回路 S1 v6 v5 v1 v5 v4 v3 S2 v1 v5 v1 9 6 2树与最小生成树 一 树的概念 树 无圈的连通图 二 树的性质 1 树枝数等于顶点数减1 2 树的任意两个顶点之间有且仅有一条初级链 3 去掉树的任一树枝 便得到一个非连通图 4 在树中任意两个顶点间添上一条边 恰好得到一个初级圈 5 在所有连通的生成子图中 生成树的边数最少 10 三 根树 有向树 D V A 中 v到D的任一顶点都有路 则v称为D的根 D称为以v为根的根树或有向树 四 图的生成树 11 定理2 图G有生成树的充要条件是图G是连通图 寻找生成树的方法 破圈法 在连通图 中任取一个圈 去掉圈上的任意一条边 对余下的图重复这个步骤 直至无圈为止 避圈法 每次增加一条边 且与已有边不构成圈 直至恰有p 1条边为止 12 例 下图是某建筑物的平面图 要求在其内部从每一房间都能走到别的所有的房间 问至少要在墙上开多少门 试给出一个开门的方案 13 6 3最小树问题 一 赋权图 与点或边有关的某些数量指标 通常称之为 权 定义 图G中 如果每条边 弧 vi vj 都被赋予一个权数wij 则称G为赋权图 权可以表示为 距离 费用 通过能力 数量 等 与无向图和有向图相对应 赋权图可分为无向赋权图和有向赋权图 分别记为G V E W 和D V A W 14 二 最小生成树 最小树 定义 在给定连通赋权图G V E W 中 求G的生成树T V E 使E 各边权Wij 0 的总和最小的问题称为最小树问题 其数学模型为 其中T 称为最小树 许多网络问题都可归结为最小树问题 如设计长度最小的公路网把若干城市联通 设计用料最省的电话线网把有关单位联系起来 15 求最小树的方法 破圈法 管梅谷算法 先从图G任取一个圈 并从圈中去掉一条权最大的边 若在同一圈中有几条都是权最大边 则任选其中一边去掉 在余下的子圈中 重复上述步骤 直至没有圈止 避圈法 Kruskal算法 开始选一条权最小的边 以后每步从未选的边中选取一条权最小的边 使它与已选边不构成圈 直至选够q 1条边止 16 例 今要在七个城市之间修筑一个公路网 每个城市之间的公路修筑费用就是各条边上的权 试求总修筑费用最小的公路网 17 6 4最短路问题 最短路问题是网络理论中应用最广泛的问题之一 许多优化问题可以使用这个模型 如管道铺设 设备更新 线路安排等 给定D V A W 其中wij W 表示弧 vi vj 的权 可以是费用 时间 距离等 设vs和vt是D中任意两顶点 求一条路 使它是从vs到vt的所有路中总权最小的路 其数学模型为 18 求最短路的狄克斯特Dijkstra标号法 Wij 0 1 基于以下原理 若序列 vs vi1 vik vt 是从vs到vt的最短路 则序列 vs vi1 vik 必为从vs到vik的最短路 2 Dijkstra标号法的基本思想是采用两种标号 T标号与P标号 T标号为临时性标号 TemporaryLabel P标号为永久性标号 PermanentLabel 从vs开始 逐步向外探寻最短路 给vi点P标号时 表示从vs到vi点的最短路权 vi的标号不再改变 给vi点T标号时 表示从vs到vi点的最短路权上界的估计 凡没有得到P标号的点都有T标号 标号法每一步都是把某一T标号点改为P标号 当终点vt得到P标号时 计算全部结束 如果点vj不能由T标号变为P标号 则说明vs到vj不存在路 19 3 步骤 1 给vs以P标号 P vs 0 其余各点给T标号 且T vi 2 若vi点为刚得到P标号的点 考虑T标号点vj vi vj A 对vj的T标号进行如下的更改 T vj min T vj P vi wij 3 比较所有具有T标号点 把最小者改为P标号 即 P vjo min T vj vj为T标号若全部点均为P标号 则停止 否则以vjo代vi 返回 2 20 1 P v1 0 T vi i 2 3 4 5 6 7 8T v2 min 0 3 3 k v2 v1T v3 min 0 5 5 k v3 v1T v4 min 0 6 6 k v4 v1 2 P v2 3T v3 min 5 3 1 4 k v3 v2T v5 min 3 7 10 k v5 v2T v6 min 3 4 7 k v4 v2 21 3 P v3 4T v4 min 6 4 1 5 k v4 v3T v6 min 7 4 2 6 k v6 v3 4 P v4 5T v6 min 6 5 3 6 k v6 v3T v7 min 5 5 10 k v7 v4 5 P v6 6T v5 min 10 6 2 8 k v5 v6T v7 min 1