《离散数学E图和H》PPT课件.ppt

2020 3 30 离散数学 1 第八章E图和H图 2020 3 30 离散数学 2 8 1七桥问题与E图 七桥问题 有四块陆地与连结它们的七座桥 问能否从这四块陆地中的任意一块出发 经过每一座桥恰好一次 最后回到原地 2020 3 30 离散数学 3 一笔画 该问题等价于 能否一笔画出下图 Euler证明了 七桥问题是无解的 图中 顶点表示陆地 边表示陆地之间的桥 2020 3 30 离散数学 4 E图 定义8 1 1 设G是一个图 经过G的每一条边的链称为E链 闭的E链称为E闭链 如果G中存在E链 称G为半E图 如果G中存在E闭链 称G为E图 下面的讨论中设G是非平凡的连通图 2020 3 30 离散数学 5 无奇点的连通图是E图 引理8 1 1 连通图G中无奇点 则G是E图 证明 设G是无奇点的连通图且G不是E图 在所有连通无奇点的非E图中 选一个边最少的图G 因G的每个顶点的度至少是2 从而G必含闭链 为什么 若G不含回路 则G是树 我们知道树中至少有两个悬挂点 奇点 矛盾 所以G中一定含有回路 而回路就是闭链 如果回路之间有重复出现的边 我们可以去掉重复者 使每条边仅出现一次 这样就得到了一条闭链 所以G中必含闭链 设C是G中最长的闭链 由假设C不是E闭链 于是G E C 中必含非平凡连通分支G 且G 中无奇点 显然q G q G 为什么 故G 必是E图 由G和C的选法 于是G 有一条E闭链C 因G连通 C 和C必有公共点v 以v作为C C的起 终点 于是C C是G的一条闭链且长度大于C的长度 这与C的假设矛盾 故G是E图 因G不是E图 G无奇点且C无奇点 2020 3 30 离散数学 6 C C G v G G中含闭链图示 C C 是一条闭链图示 2020 3 30 离散数学 7 E图是无奇点的连通图 引理8 1 1 E图是无奇点的连通图 证明 设G是E图 C是G的一条E闭链 由于G连通且C是含G的每边恰一次的闭链 因此 C中的每个点都既是起点也是终点 于是 从C上的任一点u出发 每经过一个顶点v 就有两条与v关联的边出现 一进一出 这样 C上的每个顶点 也即G的每个顶点的度均为偶数 故G中无奇点 由引理8 1 1和8 1 1 我们有 定理8 1 1 连通图G是E图当且仅当G中无奇点 2020 3 30 离散数学 8 半E图中最多有两个奇点 推论8 1 1 G是半E图当且仅当G中最多有两个奇点 证明 必要性 设G是半E图 C是G的一条E链 除起点与终点外 C中每个顶点的度均为偶数 又因G连通 故G最多有两个奇点 充分性 设G最多只有两个奇点 若G无奇点 则由定理8 1 1知 G为E图 亦为半E图 若G有两个奇点 设为u和v 则在G中加入e uv的边 使G中无奇点 由定理8 1 1知 G e为E图 即G e含E闭链C 于是C e构成G的一条E链 所以G是半E图 2020 3 30 离散数学 9 哥尼斯城堡桥不是E图 半E图 2020 3 30 离散数学 10 8 2周游世界问题与H图 周游世界问题 用一个正十二面体的二十个顶点来代表二十个城市 要求从其中任一顶点出发 沿着这个正十二面体的棱走遍这二十个顶点 且每个城市只经过一次 最后回到起点 该问题等价于 能否从下图找一条含所有顶点的回路 2020 3 30 离散数学 11 H图 定义8 2 1 设G是一个图 含G的每个顶点的通路称为H通路 起点与终点重合的H通路称为H回路 如果G中存在H回路 称G为H图 若G中存在H通路 称G为半H图 说明 H图必是半H图 反之不然 2020 3 30 离散数学 12 Herschel图 该图是半H图 因为它是一个具有奇数个顶点的二分图 所以不可能有H回路 因为二分图中的回路一定是偶数条边 定理5 5 2 2020 3 30 离散数学 13 H图的一个必要条件 定理8 2 1如果G是一个H图 则对V G 的任何非空真子集S 均成立 G S S 8 1 证明 设C是G的H回路 G的所有顶点都在C上 则显然有 C S S 成立 其中 S V G 由于C S是G S的生成子图 C S的连通分支数不比G S的少 因此 G S C S S 故 8 1 式成立 2020 3 30 离散数学 14 G H图 C H回路 定理8 2 1证明图示 2020 3 30 离散数学 15 一个非H图的判定 取S为红色点集 S 5 G S 6 S 根据定理8 2 1 此图不是H图 2020 3 30 离散数学 16 注意 这只是必要条件 注意定理8 2 1只是判断H图的必要条件 有的图虽然满足条件 却不是H图 如右边的Peterson图不是H图 可是它却满足定理8 2 1的条件 Peterson图 Peterson图是半H图而不是H图 2020 3 30 离散数学 17 H图的一个充分条件 定理8 2 2 设G是p 3 阶简单图 如果G中任何两个不邻接的顶点u和v均满足 d u d v p 8 2 则G是H图 证明 若满足 8 2 的简单图不是H图 令G p q 是其中边数最多的一个图 显然 G Kp 因为Kp一定是H图 设u v是G中不邻接的两个顶点 由G的假设可知 G uv是H图 且其中的H回路必含uv 于是 G中存在从u到v的H通路P v1v2 vp 其中u v1 v vp 2020 3 30 离散数学 18 H图的一个充分条件 证明 H通路P v1v2 vp 其中u v1 v vp 令S vi v1vi E G T vi vi 1vp E G S是邻接u的点的集合 T是位于邻接v的顶点的后面的顶点的集合 由G是简单图知 S d u T d v 又由v1与vp不邻接有S v2 vp 1 以及T v3 vp 从而S T v2 v3 vp S T p 2020 3 30 离散数学 19 H图的一个充分条件 证明 S T p 而S T 若不然 设vi S T 则存在v1v2 vi 1vpvp 1 viv1将是G的H回路 此与G不是H图的假设相矛盾 u v1 v2 vi 1 vi vi 1 vp 1 vp v G uv中的H回路 G中的H回路 2020 3 30 离散数学 20 H图的一个充分条件 定理8 2 2 设G是p 3 阶简单图 如果G中任何两个不邻接的顶点u和v均满足 d u d v p 8 2 则G是H图 证明 S d u T d v S T p S T 于是 p d v1 d vp S T S T p 此为矛盾 故结论成立 2020 3 30 离散数学 21 定理8 2 2的条件不是必要的 例如下图是H图但任意两顶点度之和为4 而P 5 2020 3 30 离散数学 22 H图的又一个充分条件 推论8 2 1设G是p 3 阶简单图 如果 G P 2 则G是H图 证明 任取u v V G 由题设均有d u d v p 2 p 2 p因此 由定理8 2 2知 G是H图 2020 3 30 离散数学 23 图的闭包 定义8 2 2 设A是p阶图 对A中满足 d u d v p 8 3 的顶点u v 若uv E A 则将边uv加入到A中 得到A uv 如此反复加边 直到所有满足 8 3 的点都邻接 最后所得的图称为A的闭包 记为 由于一个图的闭包是唯一的 所以求闭包时加边的顺序可以任意 2020 3 30 离散数学 24 求一个图的闭包 例 求右图的闭包 v1 v2 v3 v4 v5 v6 d v1 d v4 6 连接v1和v4 d v3 d v5 6 连接v3和v5 d v3 d v6 6 连接v3和v6 d v4 d v6 6 连接v4和v6 d v4 d v2 6 连接v4和v2 d v5 d v2 6 连接v5和v2 d v6 d v2 6 连接v6和v2 存在A 的情形 A Kp A中无满足条件的边可加 如图G G 2020 3 30 离散数学 25 H图的充要条件 引理8 2 1设G是p阶简单图 u与v是G中两个不邻接的顶点且满足 d u d v p于是 G是H图当且仅当G uv是H图 证明 设G是H图 则G uv显然也是H图 反之 假设G uv是H图 如果其中一条H回路不含uv 则G必是H图 如果G uv中所有H回路均含边uv 设其中有一条回路为C v1v2v3v4 vpv1 其中v1 u v2 v 2020 3 30 离散数学 26 H图的充要条件 证明 C v1v2 vpv1 其中v1 u v2 v 记 d u dG uv u dG u 1 d v dG uv v dG v 1 则有d u d v dG u dG v 2 p 2 8 4 假设在顶点v3 v4 vp 1中有r个顶点 vi1 vi2 vir与u邻接 则dG uv u r 2 u与v2 vp邻接 于是 顶点v必与r个顶点vi1 1 vi2 1 vir 1 8 5 中的某个顶点vij 1邻接 若p 4 且在G中u v分别只与vp和v3邻接 则dG u dG v 2 p 与条件矛盾 故要么u与 v3 vp 1 中的r个顶点邻接 要么v与 v4 vp 中的r个顶点邻接 且r p 2 2 dG u r 1 dG v r 1 dG u dG v 2r 2 p 故r p 2 2 2020 3 30 离散数学 27 H图的充要条件 证明 顶点v必与 8 5 中某顶点vij 1相邻接 如果v不与 8 5 中的任何顶点邻接 则有dG uv v p 1 r p 1 dG uv u 2 因此 dG uv v dG uv u p 1 此与 8 4 矛盾 因此 C v1vijvij 1 v3v2vij 1 vpv1就是G的一条H回路 C 恰不包含边uv 即G为H图 v2 v vp v1 vij 1 vij 1 vij v1 u G uv的H回路 G的H回路 P 1是G的最大度 2020 3 30 离散数学 28 A是H图当且仅当 是H图 定理8 2 3 p阶简单图A是H图当且仅当 是H图 证明 设图A是H图 则显然 也是H图 反之 设 是H图 若A 则A是H图 若A 则存在ei E A i 1 t t 1 使得A e1 e2 et 设ei uv 由闭包的定义知 d u d v p 且u与v在A中不邻接 因为 是H图 由引理8 2 1知 et仍是H图 反复应用该引理 可知A是H图 2020 3 30 离散数学 29 用顶点度序列判断H图 定理8 2 4 设p 3 阶简单图G的各顶点度数序列为d1 d2 dp 于是 若对任何mm 或者dp m p m 则G是H图 证明 我们将证明 Kp 从而由定理8 2 3有G是H图 由推论8 2 1知Kp是H图 假设 Kp 用d v 记 中v的度数 设u和v是 中不邻接且度数和为最大的两个点 不妨假设d u d v 由于uv E 因此由闭包的定义有d u d v p 于是d u p 2 取m d u p 2 2020 3 30 离散数学 30 用顶点度序列判断H图 证明 m d u p 2 设 为 中不与v邻接的顶点数 则d v p 1 即 p 1 d v 而p 1 d u d v 因此 d u m 即 中不与v邻接的顶点数至少为m 记为 vi1 vi2 vi m u vi 其中由u的最大性不妨设d vi1 d vi2 d vi m 由于V G V 因此G中也至少有m个顶点的度数不大于m 又因为G的度数序列以递增顺序排列 所以 dm m 2020 3 30 离散数学 31 用顶点度序列判断H图 证明 dm m 同样 设在 中不与u邻接的顶点数为 于是 p 1 d u p 1 m 设这些顶点分别为vj1 vj2 vj v vj 其中由v的假定可设d vj1 d vj2 d vj d v p m 又m p 2 所以 m m p 0 即d u p m 从而G中共有 p m 1 1 p m个顶点的度数均小于p m 即dp m p m 这说明存在m p 2使得dm m和dp m p m都成立 此与已知条件矛盾 于是 Kp 定理得证 d v d u p 且d u m 个顶点加上顶点u 2020 3 30 离散数学 32 8 3应用 旅行推销员问题 设有n个城市C1 Cn 某推销员从C1出发推销产品 每个城市都要走到一次 最后回到C1 已知每两个城市之间的距离 问怎样安排行程才能使总路程最短 等价的图论语言描述 在赋权完全图中求权最小的H回路 简称为最优回路 2020 3 30 离散数学 33 求最优回路 最优回路是可解的 最简单的方法就是穷举法 即找出KP的所有H回路 然后从中选出最小者即可 可是对n 4 个顶点的完全图 所有权可能不等的H回路共有 n 1 种 其时间复杂度为O n 所以当N较大时 用穷举法求解是不可想象的 如何用较快的算法来求最优回路 是人们正在研究且尚未最终解决的问题 人们开始转而求其次 即寻找一种算法能较快地求出一种较优的但不一定是最优的解 2020 3 30 离散数学 34 逐次改进法 逐次改进法这是一种近似解法 先找赋权完全图G的一条H回路 记为C v1v2 vnv1 如果w vi 1vj 1 w vivj w vi 1vi w vj 1vj 8 6 则用H回路Cij v1v2 vi 1vj 1vj 2 vi 1vivjvj 1 vnv1代替C 反复应用 直到找不出满足 8 6 式的Cij为止 逐次改进法不一定得到最优回路 2020 3 30 离散数学 35 图示 逐次改进法 任意一条H回路C如图所示 v1 vj 1 vj 2 vi vi 1 vi 1 vj vj 1 v2 vn 现在找到w vi 1vj 1 w vivj w vi 1vi w vj 1vj 于是将C改进为Cij 显然改进后的回路仍然是H回路且权值较低 2020 3 30 离散数学 36 求下图的最优回路 首先选C v1v2v3v4v5v6v1w C 14 15 8 13 1 5 56 v5 v6 v1 v2 v3 v4 13 8 15 14 5 1 7 6 5 11 9 13 8 12 10 w v2v5 w v1v4 w v1v2 w v4v5 用C14 v1v4v3v2v5v6v1代替C 绕过v1v2和v4v5 w v2v4 w v1v3 w v1v4 w v2v3 用C13 v1v3v4v2v5v6v1代替C14 绕过v1v4和v2v3 w C14 45 w C13 35 2020 3 30 离散数学 37 推销员问题的解的评估 我们可用Kruskal算法给出一个关于旅行员推销问题的解的下界估计式 任选赋权完全图Kn的一个顶点v 用Kruskal算法求出Kn v的最优树T 设C是最优的H回路 显然C v也是Kn v的一个生成树 因此w T w C v 设e1和e2是Kn中与v关联的边中权最小的两条 于是 w T w e1 w e2 w C 这就是对w C 的下界估计式 2020 3 30 离散数学 38 对下图的解的评估 我们已经求出一个解w C13 35 即C13 v1v3v4v2v5v6v1 现在求G v2的最优树T v5 v6 v1 v2 v3 v4 13 8 15 14 5 1 7 6 5 11 9 13 8 12 10 G 可得w T 22 而与v2关联的边中权最小的两条为v2v5和v2v6 所以 33 22 5 6 w T w v2v5 w v2v6 w C 35 即C13是一个比较好的近似解