第8章_一些特殊的图_[离散数学离散数学(第四版)清华出版社].ppt

1 21 20208 39PM 第四部分 图论 授课教师 向胜军 1 第八章一些特殊的图 1二部图 2欧拉图 3哈密尔顿图 4平面图 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 2 1二部图 二部图 偶图 G 完全二部图 完全偶图 Kn m 其中 V1 n V2 m 无向图G是二部图当且仅当G中无奇数长度的回路 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 3 匹配设G 是简单无向图 E E 若E 中任意两边均不相邻 则称E 为G中的匹配 或边独立集 若在E 上再加任意一条边 就不再是匹配 则称E 为极大匹配 边数最多的极大匹配称为最大匹配 其边数称为匹配数 或边独立数 记为 1 G 简记为 1 若M是图G中的一个匹配 对任意v VG 若存在M中的边与v关联 则称v为M饱和点 否则称v为M非饱和点 若G中每个点都是M饱和点 则称M是G中的完美匹配 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 4 完备匹配设G 是二部图 若G中的匹配M饱和V1或V2中所有顶点 则称M为完备匹配 注意 完备匹配一定是最大匹配 但仅当 V1 V2 才是完美匹配 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 5 存在完备匹配的充分必要条件 Hall定理 二部图G V1 V2 G中存在V1到V2的完备匹配当且仅当V1中任意k个顶点 k 1 2 V1 至少邻接V2中k个顶点 存在完备匹配的一个充分条件 二部图G 若V1中每个顶点至少关联t条边 而V2中每个顶点至多关联t条边 则G中存在V1到V2的完备匹配 证明 任取V1中的k k 1 2 V1 个顶点 他们关联的边至少为kt条 但V2中每个顶点至多为t度 所以这kt条边至少关联V2中的k个顶点 这满足Hall定理要求的前提 所以 G中存在V1到V2的完备匹配 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 6 求最大匹配的一个例子 已知5个职员x1 x2 x3 x4 x5和5项工作y1 y2 y3 y4 y5的匹配如图所示 求其最大匹配 求解过程 1 取一初始匹配M 2 分析M非饱和顶点 调整匹配方案 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 7 LeonhardEuler 1707 1783 Swissmathematician whostudiedattheUniv ofBaselundertheSwissmathematicianJohannBernoulli obtaininghismaster sdegreeattheageof16 HeworkedasamemberofthefacultyoftheAcademyofScienceinSaintPertersburg Russiaformorethan30years 欧拉计算毫不费力 就象人呼吸 或者鹰在风中保持平衡一样 阿拉戈语 这不是对欧拉无与伦比的数学才能的夸大 欧拉是历史上著作最多的数学家 被他的同代人称为 分析的化身 甚至在他生命的最后十年中的完全失明 也没有妨碍他的无与伦比的多产 事实上 失去视力有什么影响的话 那就是使欧拉对他想象中的内部世界的洞察力更加敏锐 摘自贝尔 数学精英 2欧拉图 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 8 K nigsberg七桥问题 问题的抽象 用顶点表示对象 地块 用边表示对象之间的关系 有桥相连 能否从河岸或小岛出发 通过每一座桥 而且仅仅通过一次回到原地 Euler 欧拉 1736年对这个问题 给出了否定的回答 将河岸和小岛作为图的顶点 七座桥为边 构成一个无向重图 问题化为图论中简单通路的问题 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 9 欧拉通路和欧拉回路 包含图中每条边的简单通路称为欧拉通路 包含图中每条边的简单回路称为欧拉回路 如果图G中含欧拉回路 则图G称为欧拉图 如果图G中有欧拉通路 但没有欧拉回路 则图G称为半欧拉图 欧拉图 半欧拉图 无欧拉通路 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 10 欧拉图的判定 连通无向图G是欧拉图当且仅当G中每个顶点的度均为偶数 连通无向图G具有欧拉通路当且仅当G有零个或两个奇度顶点 连通有向图D是欧拉图当且仅当D中每个顶点的入度等于出度 连通有向图D具有欧拉通路当且仅当D中除了两个顶点外 其余顶点的入度均等于出度 这两个特殊的顶点中 一个顶点的入度比出度大1 另一个顶点的入度比出度小1 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 11 中国邮递员问题 欧拉通路的应用 加权图 问题 邮递员从邮局出发 走遍投递区域的所有街道 送完邮件后回到邮局 怎样使所走的路线全程最短 若街道图 街道的交叉口为顶点 存在欧拉通路 显然此路是全程最短 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 12 每转一个触点 信号 1 2 3 4变成 2 3 4 5 前者后三位决定了后者的前三位 因此 可把所有三位二进制数作顶点 从每一个顶点 1 2 3到 2 3 4引一条有向边表示 1 2 3 4这个4位二进制数 做出表示所有可能的码变换的有向图 于是问题转化为在这个有向图上求一条欧拉回路 该图中的8个顶点的次数都为出度 入度均为2 由定理知 欧拉回路存在 求出一条欧拉回路对应的布鲁英序列是 0111100101101000 有向欧拉图的例子 一个模数转换中的应用举例 旋转鼓设计 只需要16个物理触点便可以表示0 15总共16个不同的状态 如何安排这16个触点使每转过一个触点都得到一个不同的二进制信号 求布鲁英序列 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 13 3哈密尔顿图 1859年英国数学家哈密尔顿提出了一种名为 周游世界 的游戏 用一个正十二面体的二十个顶点代表二十个大城市 要求游戏者从某一城市出发 遍历各城市一次 最后回到原地 这就是 绕行世界 问题 即找一条经过所有顶点 城市 的基本通路 回路 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 14 SirWilliamHamilton 1805 1865 爱尔兰历史上最伟大的科学家 关于哈密尔顿早期的才能的传说 读起来象一篇拙劣的虚构的故事 但它是真实的 例如 在十岁时 他差不多掌握了大多数主要东方语言 哈密尔顿在进大学以前从未上过学 他 轻而易举地取得第一名 进入三一学院 大学生涯的结束 比它开始还要更令人惊奇 都柏林大学理事会一致选举当时22岁的大学生哈密尔顿为教授 在23岁时 他发表了他还是一个17岁的孩子时作出的 奇怪的发现 即 光线系统理论 第一部分 这是一篇伟大的杰作 它对于光学 就象拉格朗日的 分析力学 之于力学 哈密尔顿最深刻的悲剧既不是酒精 也不是他的婚姻 而是他顽固地相信 四元数是解决物质宇宙的数学关键 从来没有一个伟大的数学家这样毫无希望地错误过 摘自贝尔 数学精英 我长期以来欣赏托勒密对他伟大的天文学大师希巴克斯的描绘 一个热爱劳动和热爱真理的人 但愿我的墓志铭也如此 威廉 哈密尔顿 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 15 哈密尔顿回路和哈密尔顿通路 经过图G中所有顶点的基本回路称为哈密尔顿回路 若G中含哈密尔顿回路 则称G为哈密尔顿图 经过图G中所有顶点的基本通路称为哈密尔顿通路 若G中含哈密尔顿通路 但不含哈密尔顿回路 则称G为半哈密尔顿图 半哈密尔顿图 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 16 哈密尔顿图的必要条件 注意 任何一个哈密尔顿图都可以看成是一个基本回路再加上连接该回路上顶点对的其他若干条边 从一个基本回路上删除k个顶点 最多形成k个连通分支 向一个图中已有的顶点之间加边不会增加连通分支 因此 若G是哈密尔顿图 则对VG的任意非空真子集V1 p G V1 V1 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 17 必要条件的应用 必要条件一般只能判定一个图不是哈密尔顿图 如右图 Petersen图 满足上述必要条件 但Petersen图不是哈密尔顿图 均不满足必要条件 所以都不是哈密尔顿图 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 18 半哈密尔顿图的充分条件 设G是n n 3 阶无向简单图 若G中任意不相邻的顶点对u v均满足 d u d v n 1则G是半哈密尔顿图 注意 此定理条件显然不是必要条件 如n 6的n边形 对于任意不相邻的顶点u v d u d v 4 4 n 1 而n边形显然有哈密尔顿通路 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 19 哈密尔顿图的充分条件 设G是n n 3 阶无向简单图 若G中任意不相邻的顶点对u v均满足 d u d v n则G是哈密尔顿图 n n 3 阶完全图是哈密尔顿图 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 20 判定定理的盲区 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 21 在平面上画出一个图G的图形 若该图形中任意两边均不在当中相交 则称该图形是G的一个平面嵌入 又称为平面 Planar 若图G存在平面嵌入 则G称为平面图 图G是否平面图 与其某一个图形表示无关 注意 无回路的图一定是平面图 若G的某个子图是非平面图 G也是 非连通图可以对连通分支分别讨论 4平面图 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 22 一个平面图的例子 同构变换 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 23 典型的非平面图 Jordan定理 平面上一条封闭曲线J将平面分为 内部 和 外部 两部分 分别位于内部和外部的两个顶点之间的连线必然与J相交 K5 K3 3 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 24 定义 面 face 被平面图中回路分割成互不重叠的连通块 这些块称为面 face 或区域 Region 1 如果不存在回路 整个平面只有一个面 如图 分为四个面 2 有限面与无限面 面积有限的区域称为有限面 或内部面 否则为无限面 或外部面 上图中 面4是无限面 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 25 3 面的次数等于面边界的边数 注意 悬挂边算2次 记为deg R 4 平面图中面的次数之和等于边数m的两倍 即其中 r为面数 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 26 平面图的一个必要条件 欧拉公式 若G是连通平面图 则有n m r 2 其中 n为G中顶点数 m为边数 r为面数 包括无限面 证明 对m进行归纳 初始化 当m 0 G是平凡图 n 1 r 1 当m 1 必为下列两中情况之一 G K2 n 2 r 1 G是一个环 n 1 r 2 假设当m k 1时结论成立 当m k时 I 若G中含1次顶点v 令G G v 显然 n n 1 m m 1 r r 因此 n m r n 1 m 1 r n m 1 1 r n m r 2 II 若G中无1次顶点 G中必含回路 设e是回路上任一边 令G G e 显然 n n m m 1 r r 1 因此 n m r n r 1 m 1 n m 1 r 1 n m r 2 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 27 简单连通平面图的必要条件 实际上 当平面图画不出时 欧拉公式很难直接使用 欧拉公式的推论 若G是简单连通平面图 n 3 则m 3n 6 证明 至少3个顶点的简单图G中 面的最小度数是3 所以面的总次数至少为3r 而根据定理 面的总次数等于2m 3r 2m 即r 2m 3 根据欧拉公式 2 n m r n m 2m 3 6 3n 3m 2m 即 m 3n 6 K5不是平面图 在K5中 n 5 m 10 3n 6 9 另一个推论 若G是简单连通平面图 n 3 且G是二部图 则m 2n 4 证明 与上面类似 只需注意 简单连通二部图 n 3 中 最小面次数是4 K3 3不是平面图 在K3 3中 n 6 m 9 2n 4 8 注意 K3 3满足m 3n 6 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 28 极大平面图 定义 设G是简单平面图 若在G中任意不相邻顶点之间加一条边 所得图是非平面图 则G称为极大平面图 极大平面图的连通性极大平面图是连通图 显然两个连通分支之间加一条边不影响原来图的可平面性 n 3的极大平面图不含割点和割边 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 29 极大平面图的特征 设G是n 3的简单连通平面图 则G是极大平面图当且仅当G的每个面均为3次 假设G是极大平面图 显然G中不可能有小于3次的面 假设存在一个面Ri 满足d Ri 3 设该面的边界上顶点依次是v1 v2 v3 v4 vt t 4 必有v1v3 EG v2v4 EG 且v1v3 v2v4只能在Ri以外 否则在该面内部加一条边 仍旧是平面图 与G的极大性矛盾 而此时这两边必相交 与G是平面图矛盾 不存在次数大于3的面 假设G中每个面均是3次 则2m 3r 这里m是G中边数 r是面数 G连通 可以将上述等式代入欧拉公式n m r 2 n是G中顶点数 得 m 3n 6 假设G不是极大平面图 一定可以找到一对不相邻的顶点u v 使得G G uv仍是简单平面图 但在G 中 m 3n 6 这与欧拉公式的推论矛盾 G是极大平面图 1 21 20208 39PM 第四部分 图论 授课教师 向胜军 30 同胚图 基本动作 二次顶点的插入和消去如果图G1和G2经过反复的插入和消去二次顶点 可达到同构 则G1和G2是同胚图 homeomorphicGraph 1 21 20208 39PM 第四部分 图论 授课教