分图、平面图和树王元元.ppt

1 第九章 二分图 平面图和树 2 重点 二分图及匈牙利算法 平面图 树 掌握二分图及匹配的概念 掌握求最大匹配的匈牙利算法 掌握平面图的概念 掌握平面图的欧拉定理 能够判断简单图是否平面图 掌握两个典型的非平面图 K5和K3 3 了解库拉托夫斯基定理 3 重点 二分图及匈牙利算法 平面图 树 掌握无向树的六个等价的定义 掌握无向图的生成树和最小生成树的概念 掌握求最小生成树的kruskal算法 掌握根树的概念 掌握n元树 完全n元树的概念 了解2元树的基本性质 4 9 1二分图 9 1 1二分图的基本概念定义9 1无向图G 称为二分图 bipartitegraph 如果有非空集合X Y使X Y V X Y 且对每一e E 都有e x y x X y Y 此时常用表示二分图G 若对X中任一x及Y中任一y恰有一边e E 使e x y 则称G为完全二分图 completebipartitegraph 当 X m Y n时 完全二分图G记为Km n 5 例9 1 简单无向图G是二分图 当且仅当G可二着色 6 判断二分图的定理 定理9 1无向图G为二分图的充分必要条件是 G至少有两个顶点 且其所有回路的长度均为偶数 推论任何无回路的图均是二分图 7 例 8 练习 六名间谍a b c d e f被我捕获 他们分别懂得的语言是a 汉语 法语 日语 b 德语 日语 俄语 c 英语 法语 d 汉语 西班牙语 e 英语 德语 f 俄语 西班牙语 问至少用几个房间监禁他们 才能使同一房间的人不能互相直接对话 9 判断二分图的定理 作为一种数学模型二分图是十分有用的 许多问题可以用它来刻划 例如 资源分配 工作安排 人员择偶 等等 但是 利用二分图分析解决这类问题时 还需要有关二分图的另一个概念 匹配 10 9 1 2匹配 定义9 2设G 为二分图 M E 称M为G的一个匹配 matching 如果M中任何两条边都没有公共端点 M 时称M为空匹配 G的所有匹配中边数最多的匹配称为最大匹配 maximalmatching 11 9 1 2匹配 定义9 2如果X中任一顶点均为匹配M中边的端点 那么称M为X 完全匹配 perfectmatching 如果Y中任一顶点均为匹配M中边的端点 那么称M为Y 完全匹配 perfectmatching 若M既是X 完全匹配又是Y 完全匹配 则称M为G的完全匹配 12 例9 2图9 2中各图的红线表示匹配中的边 简称匹配边 a b G c 13 9 1 2匹配 注意 最大匹配总是存在但未必唯一 X Y 完全匹配及G的完全匹配必定是最大的 但反之则不然 X Y 完全匹配未必存在 存在不唯一 14 有四名教师张征 王兴 李忠和赵华 分别派他们教四门课程 数学 物理 电工和计算机导论 张征懂物理和电工 王兴懂数学和计算机导论 李忠懂数学 物理和电工 赵华只懂电工 问应该如何分派 才不会使任何人去讲他不懂的课程而又不存在有的课程无人教 15 匹配的应用 安排工作 现有6个工人 x1 x2 x6 有6项工作 y1 y2 y6 假设在同一时间内 每人只能干一项工作 每项工作只需一个人干 每个工人能干的工作用边来表示 安排工作就是求二分图的一个匹配问题 求最大匹配就是一个工作最佳的安排问题 使尽可能多的人有工作干 尽可能多的工作被人干 16 术语介绍 定义9 3设G M为G的一个匹配 1 M中边的端点称为M 顶点 其它顶点称为非M 顶点 17 术语介绍 定义9 3 2 G中vk到vl的通路P称为交替链 如果P的起点vk和终点vl为非M 顶点 而其边的序列中非匹配边与匹配边交替出现 从而首尾两边必为非匹配边 除顶点vk vl以外各顶点均为M 顶点 特别地 当一边 v v 两端点均为非M 顶点 通路 v v 亦称为交替链 18 由交替链的定义可以推出下述三个结论 1 P的路径长度必定为奇数 第一条边和最后一条边都不属于M 2 P经过取反操作可以得到一个更大的匹配M 3 M为G的最大匹配当且仅当不存在相对于M的交替链 19 匈牙利算法 求最大匹配的一种显而易见的算法是 先找出全部匹配 然后保留匹配数最多的 但是这个算法的复杂度为边数的指数级函数 因此 需要寻求一种更加高效的算法 20 用交替链求最大匹配 称作匈牙利算法 匈牙利数学家Edmonds于1965年提出 算法轮廓 1 置M为空 2 找出一条交错链P 通过取反操作获得更大的匹配M 代替M 3 重复 2 操作直到找不出交错链为止 匈牙利算法 21 例9 3用匈牙利算法求图9 3的一个最大匹配 x1x2x3x4x5x6 y1y2y3y4y5y6y7 22 x1x2x3x4x5x6 y1y2y3y4y5y6y7 例9 3用匈牙利算法求图9 3的一个最大匹配 23 x1x2x3x4x5x6 y1y2y3y4y5y6y7 例9 3用匈牙利算法求图9 3的一个最大匹配 24 x1x2x3x4x5x6 y1y2y3y4y5y6y7 例9 3用匈牙利算法求图9 3的一个最大匹配 25 x1x2x3x4x5x6 y1y2y3y4y5y6y7 例9 3用匈牙利算法求图9 3的一个最大匹配 26 完全匹配的存在条件 定义图G 的顶点子集S V的相邻顶点集N S 所有与S中顶点相邻的顶点组成的集合 N S v v V u e u S e E e u v 或N S v u e u S e u v 27 完全匹配的存在条件 定理9 2设图G G有X 完全匹配的充分必要条件是 对每一S X有 N S S 霍尔婚姻定理 28 例 x1 x2 x3 y3 y2 y1 y4 29 应用 有六位未婚女子 L1 L2 L3 L4 L5 L6和六位未婚男子 G1 G2 G3 G4 G5 G6中六位女子分别对下列集合的男子中意 L1 G1 G2 G4 L2 G3 G5 L3 G1 G2 G4 L4 G2 G5 G6 L5 G3 G6 L6 G2 G5 G6 六位男子分别对下列集合的女子中意 G1 L1 L3 L6 G2 L2 L4 L6 G3 L2 L5 G4 L1 L3 G5 L2 L6 G6 L3 L4 L5 30 现需涉及一个有6个元件的电路 把6个元件分成两组 每组3个元件 设计要求每组中的任一个元件必须与另一组中的所有元件用导线连接 问能否设计电路使导线不交叉 如果能 画出设计方案 如果不能 说明理由 并画出一个导线交叉最少的设计方案 31 9 2平面图 9 2 1平面图的基本概念定义9 4无向图G称为平面图 planargraph 如果G可以在一个平面上图示出来 而使各边仅在顶点处相交 否则称G为非平面图 画出的没有边交叉出现的图称为G的一个平面嵌入或G的一个平面 32 例 33 K3 3与K5称为库拉托夫斯基 Kuratowski 图 共同点 1 它们都是正则图 2 去掉一条边时它们都是平面图 3 K3 3是边数最少的非平面简单图 K5是顶点数最少的非平面简单图 因而它们都是最基本的非平面图 34 9 2面的概念 定义9 5平面连通图中各边所界定的区域 不包含任何边和结点 称为平面图的面 regions 有界的区域称为有界面 无界的区域称为无界面 界定各面的闭的拟路径称为面的边界 boundary 它的长度称为面的度 degree 35 例9 6 36 平面简单图的所有有界面的度均不小于3 37 9 2平面图 定义9 6称平面简单图G是极大平面图 maximalplanargraph 如果在G中添加任一边 它不是环 也不是其他边的平行边 后所得的图均非平面图 38 9 2平面图 定理9 3极大平面图所有有界面都是三度的面 无界面也是三度的 即所有面的边界均为K3 39 例 Y N 40 9 2 2欧拉公式 定理9 5设G为一平面连通图 n为其顶点数 m为其边数 r为其面数 那么n m r 2 41 推论 定理9 6如果平面连通图G的每个面的边界都具有长度l l 3 那么m l n 2 l 2 其中m为G的边数 n为G的顶点数 42 推论 定理9 7设G为一平面连通简单图 其顶点数n 3 其边数为m 那么m 3n 6 43 例 K5K3 3 44 推论 定理9 8设G为一平面简单连通图 其顶点数n 4 边数为m 且G不以K3为其子图 那么m 2n 4 45 推论 定理9 9顶点数n不少于4的平面连通简单图G 至少有一个顶点的度数不大于5 46 证明 定理9 9的结论可加强为 至少有3个顶点的度数不大于5 证用反证法 假设度数不大于5的顶点数可以少于3个 但由于n不小于4且为连通图 所以每个顶点的度数最小为1 因此6 n 2 2 2m 由于m 3n 6 故6 n 2 2 2m 6n 12 即6n 10 6n 12矛盾 因而度数不大于5的顶点数至少有3个 47 应当指出 欧拉公式及其上述推论 都只是平面连通图或平面连通简单图的必要条件 而不是它们的充分条件 因此只能用它们判别非平面图 不能用它们来识别平面图 48 1 切割操作 1 对边e的切割操作 设G中有边e u v 对边e作切割操作是指 1 取消边e 2 增加顶点w 以及边e1 u w 边e2 w v 49 v 例9 9 a b 边e切割 e 50 2 贯通操作 2 对顶点v的贯通操作 设G中有二度顶点v 它是e1 u v e2 v w 的共同端点 对顶点v作贯通操作是指 1 取顶点v以及边e1 e2 2 增加边e u w 切割与贯通是互逆的 两者常被称为同胚运算 51 v 例9 9 a c 顶点v贯通 e 52 3库拉托夫斯基定理 定理9 10图G是平面图 当且仅当对G或G的子图作任何同胚操作后所得图均不以K5及K3 3为子图 53 例 a b c 54 9 3树 9 3 1树的基本概念定义9 9连通无回路的无向图称为无向树 简称为树 tree 树中的悬挂点又称为树叶 leave 其它结点称为分支点 branchednode 单一孤立结点称为空树 nulltree 诸连通分支均为树的图称为森林 forest 树也是森林 55 例9 13 a b c 56 性质 定理9 12树和森林都是可2 着色的 从而都是二分图 定理9 13树和森林都是平面图 其面数为1 57 性质 定理9 14设图T为一树 其顶点数 边数分别是n m 那么n m 1或m n 1 58 性质 定理9 15任何非平凡数树都至少有两片叶 59 树等价定义形式 T无回路且m n 1 T连通且m n 1 T无回路 但任意添加边时 T中产生唯一的一条回路 4 T连通 但删去任一边时便不再连通 T的每一边均为割边 5 任意两个不同顶点之间有且仅有一条通路 60 树是 最小的连通图 少一边便不连通 树又是 最大的无回路图 多一边便有回路 树是以 最经济 的方式把其中各顶点连接起来的图 树等价定义形式 61 9 3 2生成树 定义9 10图T称为无向图G的生成树 spanningtree 如果T为G的生成子图且T为树 62 9 3 2生成树 定理9 17任一连通图G都至少有一棵生成树 63 求生成树方法 对于连通图G我们可以通过依次从回路中删边的方法得到其生成树 此方法常称为破圈法 生成树通常是不唯一的 64 例9 4 65 设G 为连通的边赋权图 W为E到非负实数集的函数 设T为G的生成树 那么T中各边权之和W T 称为生成树T的权 权最小的生成树称为最小生成树 最小生成树 66 例 它们的权W T1 24 W T2 30 328 4 7 378 111 T1 T2 67 克鲁斯克尔 Kruskal 算法 设连通边赋权图G有n个顶点m条边 并设W e1 不包含回路 那么置A为A ek 3 当 A n 1时算法终止 否则置k为k 1 回到步骤 2 68 克鲁斯克尔 Kruskal 算法 算法的基本思想 依边权从小到大的次序 逐边将它们放回到所关联的顶点上 但删去会生成回路的边 直至产生一个n 1条边的无回路的子图 此法常形象称为避圈法 69 指出两点 1 对于有边权相同的赋权图 克鲁斯克尔算法依然成立 若两个边权相同 哪一条都可以 2 利用求生成树的破圈法也可求最小生成树 但其算法与避圈法相反 即依次从图的回路中删去边权最大的边 直至没有回路结束 若在某一回路中 两个边权相同且最大 这时可删去其中的任意一条 70 T G 111 3 8 3 4 9 10 6 7 2 1 2 3 例避圈法 4 7 71 G 1 3 8 3 4 9 10 6 7 2 例破圈法 11 72 克鲁斯克尔 Kruskal 算法正确性 1 算法产生的图无回路 且边数m n 1 据定理9 16 此图为树 由于它含有G的所有n个顶点 因而是G的生成树 73 克鲁斯克尔 Kruskal 算法正确性 2 设算法生成的树T不是最小生成树 另有最小生成树T 那么至少有一边e在T 中而它不在T中 考虑关于生成树T的弦e 回路 据算法实施过程知 e是该回路中权最大的边 于是由定理9 23 e不会在G的最小生成树T 中 矛盾 因此 算法生成的树是最小生成树 74 9 3 3根树 定义9 12树T称为根树 rootedtree 如果 1 T为一孤立结点v0 v0又被称为T的树根 2 T1 T2 Tk为以v1 v2 vk为树根的根树 T由T1 T2 Tk及与v1 v2 vk相邻的结点v0所组成 v0称为T的树根 75 9 3 3根树 定义9 13在定义9 12中 1 v1 v2 vk称为v0的儿子 v0称为它们的父亲 vi vj同为一顶点v的儿子时 称它们为兄弟 2 顶点间的父子关系的合成称为顶点间的祖孙关系 即当vi为vi 1 i 1 2 l 1 的父亲时 v1是vl的祖先 vl为v1的子孙 76 9 3 3根树 定义9 13在定义9 12中 3 根树T自身及以它的树根的子孙为根的根树 T的子图 均称为T的子树 subtree 后者又称为T的真子树 77 根树性质 根树的每个结点都是一棵子树的树根 除了树根 根树中每结点均为某一结点的儿子 除了树叶 根树中每一结点均为某些结点的父亲 树根到叶有唯一的通路 这样的通路中最长一条的长度称为树高 78 例9 16 v0v1v2v3v4v5v6v7v8v9v10v11v12 79 例9 18 甲乙两人进行乒乓球赛 规定一方连胜两局或胜局首先达到3局者为胜方 问甲乙至少 至多要进行多少局比赛 如果用分支结点表示一局比赛 用关联的两边表示胜负状况 标记甲的边表示甲胜 标记乙的边表示乙胜 80 1 甲 乙 2 2 3 3 乙 甲 乙 甲 终止 终止 4 4 甲 乙 甲 乙 终止 终止 终止 终止 终止 终止 终止 终止 甲 甲 甲 甲 乙 乙 乙 乙 5 5 81 完全2元树 定义9 14除了树叶外 每个结点都有两个儿子的根树称为完全2元树 binarytree 82 完全2元树性质 定理9 24完全2元树的顶点个数n必定是奇数 证完全2元树中除树根的度为2外 其它顶点的度均为3或1 因此完全2元树度数总和为n 1个奇数的和加2 若n为偶数 则n 1为奇数 从而树的度数的总和为奇数 但这是不可能的 因此n必为奇数 83 完全2元树性质 定理9 25完全二元树中叶的数目 其中n为树的顶点数 证设完全二元树T有n个顶点 l片叶和m条边 那么除根和叶以外它有n 1 l个分支结点 各为3度顶点 于是 解出 84 完全2元树性质 定理9 26完全二元树高h满足 这里n为二元树的顶点个数 a 表示a的取整运算 即小于等于a的最大整数 85 二元树 定义9 15每个结点都至多有两个儿子的根树称为二元树 quasibinarytree 类似地 每个结点都至多有n个儿子的根树称为n元树 对各分支结点的诸儿子规定了次序 例如左兄右弟 的n元树称为n元有序树 86 二元树 定义9 15若对各分支结点的已排序的诸儿子规定了在图示中的位置 例如左 中 右 那么该n元有序树又称n元位置树 2元位置树各分支结点的左右儿子分别称为左儿子和右儿子 87 例9 19 a b c 88 任何n元有序树都可以用2元位置树来表示 即可对任何一n元有序树作一系列的变换 使之成为一棵2元位置树 从这一2元位置树中可得到原n元有序树的有关性质 甚至恢复出这一n元有序树 这对计算机很重要 因为计算机处理二元树是最方便的 89 例 123456789101112 a 只要将每个分支结点的诸儿子中的大儿子 以左兄右弟为序 保留为其儿子 左儿子 而放弃其它儿子 令二儿子为大儿子的右儿子 三儿子为二儿子的右儿子 如此等等 90 在作出的2元位置树中检索原n元有序树或恢复原n元有序树 只要把每一分支结点的左儿子看作它的大儿子 而将其右儿子看作它的弟兄 删去该分支结点到其右儿子的边 添加该分支结点的父结点到该分支结点的右儿子结点的边 91 将森林中的每一棵n元有序树表示为2元位置树 将它们的树根以父子方式连接起来 左父右子 92 例 179238101112456131415 93 树的遍历 1 先根算法 前序遍历法 1 访问二元树树根r 2 如果r有左儿子 那么又以先根算法遍访r的左子树 3 如果r有右儿子 那么又以先根算法遍访r的右子树 94 树的遍历 2 中根算法 中序遍历法 1 如果二元树树根r有左儿子 那么又以中根算法遍访r的左子树 2 访问二元树树根r 3 如果二元树树根r有右儿子 那么又以中根算法遍访r的右子树 95 树的遍历 3 后根算法 后序遍历法 1 如果二元树树根r有左儿子 那么以中根算法遍访r的左子树 2 如果二元树树根r有右儿子 那么又以中根算法遍访r的右子树 3 访问二元树树根r 96 97