运筹学课件 第一节 图与网络的基本知识.ppt

1 图的基本概念图论是专门研究图的理论的一门数学分支 主要研究点和边之间的几何关系 复习第一节图与网络的基本知识 2 图的基本概念 G V E 子图 矩阵表示 含元素的个数 点的次 边 图 点边关系 简单图 多重图 连通图 树 生成子图 3 第二节树 主要内容一 树的概念以及性质二 图的生成树 深探法 广探法和破圈法三 最小生成树 避圈法和破圈法四 根树及其应用 4 树是一类极其简单而很有用的图 多级辐射制的电信网络 家谱 分类学 管理组织结构等都是典型的树图 某企业的组织结构图 一 树的概念以及性质 5 树实际上是连通图 但没有圈 由所有节点 n 和相应的边 n 1 组成 定义14 树 一个无圈的连通无向图称为树 树中次为1的点为树叶 次大于1的点为分枝点 b f e d v1 v2 v3 v4 v5 d v1 1 v1树叶 d v2 1 v2树叶 d v5 1 v5树叶 d v4 4 v4分枝点 d v3 1 v3树叶 6 例 判断下列图形是否为树 树 7 树 8 树 树 9 树 树 10 树的性质 1 在图中任意两点之间必有一条而且只有一条链 2 在图中划去一条边 则图不连通 3 在图中不相邻的两个顶点之间加一条边 可得一个且仅得一个圈 4 图中边数有m n 1 n为顶点数 11 定理6 图T V E 点数 n 边数 m 下列关于树的说法等价 1 T是一棵树 2 T无圈 且m n 1 3 T连通 且m n 1 4 T无圈 但任加一新边得到唯一一个圈 5 T连通 但任舍去一边就不连通 6 T任意两点 有唯一链相连 12 b c f e d h g a b c h 图3 图4 图5 图6 图7 图8 a 13 二 图的生成树 定义15如果图T是G的一个生成子图 而且T又是一棵树 则称图T为一棵生成树 支撑树 子图定义 设G V E 和G1 V1 E1 如果V1 V E1 E 且E1边仅与V1中的顶点相关联 则称G1为G的子图 生成子图定义 如果G1 V1 E1 是G V E 子图 并且V1 V 则称G1为G的生成子图 14 生成树与子图 生成子图的关系 一个子图与生成树的区别是 子图与原图相比少边又少点 生成树与原图相比少边不少点 一个生成子图与生成树的区别是 生成子图可能含有圈 生成树无圈 图中属于生成树的边为树枝 不在生成树中的边为弦 15 子图 练习1 找出图G的子图 生成子图 生成树 图1 e8 图G 16 生成子图 e1 e8 e6 e4 e3 e2 v5 v3 v4 v2 v1 图2 图G 17 生成子图 生成树 树枝e2 e3 e5 e6 弦e1 e4 e7 e8 e5 e2 e6 图3 图G e3 e1 e8 e7 e6 e5 e4 e3 e2 v5 v3 v4 v2 v1 v3 v2 v1 v4 v5 18 定理7图G有生成树的充分必要条件为图G是连通图 生成树的求解方法 1 深探法步骤 a 在点集V中任取一点v 给v标号0 b 如果某点u已经得到标号i 检查一端点为u的各边 另一端是否已经标号 如果有 u w 边的w点未标号 则给w以标号i 1 记下边 u w 令w代替u 继续重复 如果有 u w 边的w已经标号 则退到标号i 1的r点 令r代替u 继续重复 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 u已经得到标号 检查一端点为u的各边 另一端w是否已经标号 有 u w 边的w已经标号 则退到标号i 1的r点 令r代替u 继续重复 r 5 1 r代替u 20 原则 不能成圈 原则 不能成圈 原则 不能成圈 0 1 2 3 4 5 6 7 8 9 10 11 12 13 21 2 广探法步骤 a 在点集V中任取一点v 给v标号0 b 令所有标号i的点集为Vi 检查 Vi V Vi 中的边端点是否已经标号 对所有的未标号的点均标号i 1 记下这些边 c 对标号i 1的点继续重复步骤b 直至全部点得到标号 22 0 1 1 1 2 2 2 2 3 3 3 4 1 2 A B 23 图的生成树不唯一 0 24 3 破圈法 深探法和广探法核心是避免成圈 步骤 从图G任取一个圈 从圈中任舍弃一条边 将此圈破掉 重复以上步骤直至无圈为止 圈1 圈2 圈3 圈4 圈5 圈6 v1 v2 v3 v4 v5 v6 v7 25 练习2 分别使用深探法 广探法 破圈法找出下图的一个生成树 26 0 1 2 3 4 使用深探法找出下图的一个生成树 27 使用广探法找出下图的一个生成树 28 使用破圈法找出下图的一个生成树 圈1 圈 圈 圈 29 求最小树的方法有避圈法和破圈法 三 最小生成树 定义16 在赋权图G中 一棵生成树所有树枝上权的和 称为生成树的权 具有最小权的生成树 称为最小生成树或最小树或最小支撑树 最小树的应用 设计长度最小的公路网把若干城市联系起来 设计用料最省的电话线网把有关单位联系起来 30 例一个乡有9个村 道路及其道路长度如图 如何拉电线才能使电线总长度最短 1 避圈法 krusakal 步骤 每步从未选的边中选取边e 使它与已经选的边不构成圈 且e是未选边中的最小权边 直到选够n 1条边 解 1 先将图中边按照大小顺序由小到大排列 v0 v2 1 v3 v2 1 v3 v4 1 v1 v8 1 v0 v1 2 v0 v6 2 v5 v6 2 v0 v3 3 v6 v7 3 v0 v4 4 v0 v5 4 v0 v8 4 v1 v2 4 v0 v7 5 v7 v8 5 v4 v5 5 31 32 定理8 用避圈法 kruskal 算法得到的子图为一棵最小树 V1 V0 V8 V2 V3 V4 V5 V6 V7 1 3 2 1 1 2 1 2 使用电话线最小长度L 1 1 1 1 2 2 2 3 13 33 2 破圈法步骤 1 从图G中任选一棵树T1 2 加上一条弦e1 T1 e1中立即生成一个圈 去掉此圈中的最大权边 得到新树T2 以T2代替T1 继续重复检查剩余的弦 直到全部弦检查完毕 定理9 图G的生成树T为最小树 当且仅当对任一弦e来讲 e是T e中与之对应的圈ue中的最大权边 34 35 例 先求出一棵树T1 加以弦 v1 v2 得到圈 v1v2v0v1 去掉最大权边 v1 v2 再加上弦 v2 v3 得到圈 v2v3v0v2 去掉最大权边 v0 v3 全部弦 2 1 3 4 1 4 2 5 4 4 1 5 2 3 5 1 V1 V0 V7 V6 V8 V2 V3 V4 V5 使用电话线最小长度L 1 1 1 1 2 2 2 3 13 36 另一种破圈法 找圈 擦除最大边以破圈 赋权图G 生成最小树T 1 2 3 1 2 1 1 2 圈1 圈2 圈3 圈4 圈5 圈6 圈7 圈8 使用电话线最小长度L 1 1 1 1 2 2 2 3 13 37 V1 V6 V3 V4 V5 V2 V7 4 3 2 3 2 4 5 1 7 2 6 7 4 练习3 破圈法求下图的最小树 最小树的权 3 3 2 2 1 2 13 38 9 3 17 4 1 23 练习4 避圈法求下图的最小树 最小树的权 1 4 9 3 17 23 57 v2 v3 v4 v5 v6 v7 v1 39 根 根树入次 0的点 叶 根树出次 0的点 其他的顶点为分枝点 层次 由根到某一顶点的道路长度 假设每边的长度为1 称为点的层次 四 根树及其应用 1 根树对有向图而言 根树在计算机科学 决策论有重要应用 定义17 如果一个有向图在不考虑边的方向时是一棵树 此有向图为有向树 定义18 有向树T 恰好有一个结点入次 0 其余各点入次 1 树T为根树 外向树 40 V1 根 V1 V4 V9 V8 V7 V6 V5 V2 V10 V3 例 V5 V6 V4 V7 V9 V10 叶 V1 V2 V3 V8 分枝点 V2 V3 V4的层次 1V5 V6 V7 V8 V9的层次 2V10层次 3 v1入次 0 其它点入次 1 T 根树 v5 v6出次 0 v4出次 0 v7 v9出次 0 v10出次 0 根树应用 系统的传递关系 指挥系统的上下级关系 计算机科学的应用 有向树 41 定义19 在根树中 如果每个顶点的出次等于m或零 称此树为完全m叉树 如每个顶点的出次小于或等于m称此树为m叉树 当m 2时 为完全二叉树 二叉树 完全三叉树 四叉树 出次 3 出次 3 出次 0 出次 3 出次 2 出次 4 出次 1 出次 0 42 算法步骤 1 将s个叶子按照权大小排序 2 将二个具有最小权的叶子合并成一个分枝点 其权p1 p2 将新得到的分枝点作为一个叶子 令s s 1 如果s 1 停止 否则转 1 实际问题中经常讨论叶子上带权的二叉树 有s个叶子的二叉树T各个叶子的权分别为pi 根到叶子的层次为Li i 1 2 s 这样叶子的二叉树的总权数m T 满足总权最小的二叉树为最优二叉树或霍夫曼树 43 例 S 6 其权分别为4 3 3 2 2 1 求最优二叉树 1 2 2 3 4 3 3 5 6 44 9 15 总权为m T 4 2 1 4 2 4 2 3 3 2 3 2 38绿色为叶子 黑色为层次 45 例 使用计算机进行图书分类 现有5类图书共100万册 其中有A类50万册 有B类20万册 有C类5万册 有D类10万册 有E类15万册 问如何安排分拣过程 可使总的运算 比较 次数最小 2 最优二叉树的应用 解 先构造一棵具有5个叶子的最优二叉树 令其叶子的权分别为50 20 5 10 15 然后构造最优二叉树 46 5 10 15 20 50 15 30 50 CDEBA 100 A B A N Y E B N Y D E N Y D N Y C m T 5 4 10 4 15 3 20 2 50 1 195 47 思考题 如何将实际应用与最小生成树的算法联系起来 48 小结 1 树的概念以及性质 2 图的生成树 深探法 广探法和破圈法 3 最小生成树 避圈法和破圈法 4 根树及其应用 49 50 51 证明 1 T是一棵树 由于T是一棵树 根据定义 T是连通且无圈 现在需要证明边数m n 1 用归纳法 当n 2 由于T是一棵树 所以两点之间只有1条边 满足m n 1 假设当n k 1时命题成立 有k 1个顶点 有k 2条边 b f e d u v T 2 T无圈 且m n 1 T1 e u 52 证明 1 T是一棵树 当n k时 T是连通且无圈 k个顶点至少有1个点次为1 设点u 为悬挂点 边e u v 从T中去掉边e和点u不会影响T的连通 得到T1 T1为树只有k 1个顶点 有k 2条边 再把e u v 点u加上去 可知当T有k个顶点时有k 1条边 b f e d u v T 2 T无圈 且m n 1 T1 e u 53 证明 2 T无圈 且m n 1 3 T连通 且m n 1 只需要T证明是连通的 反证法 假设T不是连通的 可以分为L个连通子图 L 2 设第i个子图有ni个顶点 因为第i个连通子图是树 所以有ni 1条边 L个子图共有边数为 与已知矛盾 所以T是连通图 54 先证明T无圈 假设T中有圈 设为C 可以去掉C中的一条边 并不影响T的连通性 如果剩余图中仍有圈 可继续去掉一条边 像这样去掉p条边 p 1 后得到一个没有圈的连通图T1 T1显然有n 1 p 5 1 2 2 条边 但T1为树 顶点个数又与T相同为n个 所以T1应该有n 1 5 1 4 条边 矛盾 所以T中无圈 由于T连通且无圈 两点之间必有一条唯一的链 否则会出现圈 所以 T u v 出现唯一的一个圈 证明 3 T连通 且m n 1 4 T无圈 但任加一新边得到唯一一个圈 T 圈c T1 55 证明 4 T无圈 但任加一新边得到唯一一个圈 5 T连通 但任舍去一边就不连通 先证明T连通 如果T不连通 由定义至少存在2点u w之间无路可通 则加上一边 u w 也不会形成圈 与已知T无圈矛盾 再证明每舍