E图和H图.ppt

E图和H图 四川师范大学数学与软件科学学院周思波 七桥问题与Euler图 18世纪 在德国哥尼斯堡城的普雷格尔河上建有七座桥 这七座桥把河的两岸和河中的两个小岛连接起来 当地居民很自然地提出一个问题 能否接连走过每座桥一次且仅仅一次 许多人用尝试法来寻找这样一种走法都遭到了失败 1736年 欧拉 Euler 发表了图论的第一篇论文 哥尼斯堡的七座桥 提出了一个简单的法则 判定这个问题是无解的 一笔画问题 如果用A B C D四个顶点表示河的两岸及两个小岛这四个区域 那么连接这四个区域的七座桥就是连接四个顶点的七条边 这样七桥问题的求解就相当于一笔画出右下图而不能有重复的笔画 这就是所谓的一笔画问题 Euler链与Euler图 经过图G的每条边的链称为Euler链 闭的Euler链称为Euler闭链或Euler环游 若图G包含一条Euler环游 则G称为Euler图 E图 定理5 1非平凡连通图G是E图的充要条件是G没有奇顶点 证设G是E图 C是G的一条Euler环游 其起点 也是终点 记为u C的内部顶点v每出现一次 就有两条与它关联的边出现 又因G的Euler闭链包含G的每条边 所以对所有的v 都有d v 是偶数 而对起点 终点 u 当然有d u 是偶数 故G没有奇顶点 反之 如果G是至少有一条边的无奇顶点的连通图 假定G是非E图 选择这样一个图G 使其具有尽可能少的边 由于G没有奇顶点 所以G必含闭链 设C是G中长度最大的闭链 由假定知C不是G的Euler闭链 因此G E C 中必有至少含一条边的连通分文G 且G 无奇顶点 由于G 的边数少于G的边数 由G的选择 知G 有Euler闭链C 因为G是连通的 所以C与C 必有公共顶点v 不失一般性 可把v作为C与C 的起点和终点 于是C C 就是G中又一条闭链 且长度大于C的长度 与C的取法矛盾 故G图是E图 推论5 2连通图G具有Euler链的充要条件是G最多有两个奇顶点 证若G具有Euler链 则仿照上述定理的证明可知 这条链除起点与终点外 每个顶点都有偶度数 反之 设G是最多有两个奇顶点的非平凡连通图 若G无奇顶点 由定理5 1 G有闭Euler链 除此之外 由于图的奇顶点的个数必为偶数 所以G恰有两个奇顶点u和v 令uv e 则G e的每个顶点都有偶度数 由定理G e有Euler闭链C ueve1 esu 于是w ve1 esu就是G的一条Euler链 练习 下列各图哪些可以一笔画 练习 判断下列各图是否是E图 若是作出图中的一条欧拉链 练习 四间房子如下图所示 相邻两房子之间有门相通 并且每个房子有一门与院子相通 问能否每个门都恰好走过一次 既无重复也无遗漏 练习 如果可能 画出一个p为偶数而q为奇数的Euler型图 否则说明为什么不存在这样的图 Hamilton图 包含图G的每一个顶点的通路称为G的HamiIton通路 如果这条通路的起点与终点重合 则称为G的HamiIton回路 简称H圈 如果图G包含一条Hamilton回路 换句话说 图G有一个生成子图是圈 则G称为Hamilton图 简称H图 例如正十二面体是H图 而Herschel图是非H图 Hamilton图的必要条件 定理5 3若G是一个Hamilton图 则对于V G 的每一个非空真子集S 均成立 G S S 证设C是G的一条Hamilton回路 任何一个非空真子集S 均成立 C S S 同时 C S是G S的一个生成子图 因而 G S C S 于是 G S S Hamilton图的充分条件 定理5 4 Dirac 1952 设G是n n 3 阶简单图 是G的各顶点的最小度数如果 n 2 则G是Hamilton型的 证假定结论不成立 并设G是n 3和 n 2的边数最多的非Hamilton型的简单图 因此G是非完全图 故在G中存在非邻接顶点u和v 由于G的选择 G uv是Hamilton型的 由于G是非Hamilton型的 所以G uv的每一条Hamilton回路必然包含uv边 于是在G中存在一条以u v1为起点 v vn为终点的Hamilton通路v1v2 vn 令S vi uvi 1 E G T vi viv E G 因为vn不属于S T 所以 S T n假设S T包含某个顶点vi G将有Hamilton回路v1v2 vivnvn 1 vi 1v1 与假设矛盾 所以 S T 0 因此d u d v S T S T S T n这与 n 2矛盾 Hamilton图的充分条件 定理5 5设G是一个n阶简单图 u及v是G中非邻接的顶点且满足d u d v n 则G是Hamilton型的充要条件是G uv为Hamilton型的 证先证必要性 若G是Hamilton型的 则存在一条Hamilton回路 增加一条边uv 不影响该回路的性质 故G uv也是Hamilton型的 下面证充分性 假设G uv也是Hamilton型的 1 如果它所含的Hamilton回路不含uv 那么该回路也是G的Hamilton回路 从而G是Hamilton型的 2 如果G uv的Hamilton回路含有uv边 不妨设回路为uvv3v4 vnu 记d u d G uv u dG u 1 d v d G uv v dG v 1 故有d u d v n 2假设在顶点v3 v4 vn 1中有r个顶点vi1 vi2 vir与u邻接 那么d u r 2如果顶点v和r个顶点vi1 1 vi2 1 vir 1中的某一个vij 1邻接 那么C uvijvij 1 v3vvij 1 vnu显然是G的一个Hamilton回路 如果v和r个顶点vi1 1 vi2 1 vir 1都不邻接 则有d v n 1 r 所以d u d v n 1 导出矛盾 因此G中必定存在Hamilton回路 从而G是Hamilton型的 闭包 设G为n阶图 如果G有一对顶点u v 满足d u d v n 而且边 u v 不属于E G 则将 u v 加于图G 得到G u v 如此反复加边 直到不再有这样的顶点对为止 最终得到的图叫做G的闭包 记为 G C G 引理5 6图G的闭包是唯一的 证设G1和G2是用下述方法从G得到的两个图 把度数之和至少是n的非邻接顶点对递推地连接起来 直到不再有这样的顶点对存在时为止 用e1 e2 es和f1 f2 ft分别表示G1和G2中那些添加给G的边的序列 下面我们证明每个ei是G2的一条边 而每个fi是G1的一条边 不妨设ek 1 u v 是序列e1 e2 es中第一条不属于G2的边 令H G e1 e2 ek 从的作法知dH u dH v n根据ek 1的选择 H是G2的子图 因此dG2 u dG2 v n这与中u v是非邻接顶点矛盾 所以每个ei是G2的一条边 类似地可以证明 每个fi是G1的一条边 因此G1 G2 即G的闭包是唯一确定的 定理5 7简单图G是Hamilton图当且仅当 是Hamilton图 推论5 8设G是一个n 3的简单图 若 则G是Hamilton图 是完全图 定理5 9设n 3 阶简单图G的度序列为 d1 d2 dn 这里d1 d2 dn 假如对于任何mm或有dn m n m 那么G是Hamilton图 定理5 11设G是有n个顶点 q条边的简单图 如果 则G是Hamilton图 练习 一只老鼠吃3 3 3的乳酪 其方法是通过打洞挖通所有的27个1 1 1的小立方体 如果它在一个角上开始 然后依次挖向未吃过的小方体 试问它能在这个立方体的中心结束吗 练习 证明 a 若G不是2 连通图 则G是非Hamilton型的 b 若G是二分图 并且它的顶点二分划 X Y 有 X Y 则G是非Hamilton型的 证明 a G不是2 连通 则G不连通或存在割点v 有 G v 2 由定理5 2知G是非Hamilton型的 b 设G是二分图 其划分为 X Y 且 X Y 则有 G X Y X 由定理5 2知G是非Hamilton型的 练习 设n 3 个人中 任两个人合在一起都认识其余n 2个人 证明这n个人可以排成一队 使相邻者都互相认识 证明 每个人用一个点表示 相互认识则用边连接相应的点 于是得到简单图G 若G中有Hamilton道路 则问题得证 由已知条件 对任意两点u v 都有d u d v n 2 此时若u v相识 则d u d v n 若不相识 必存在w点 满足 u w v w E G 否则就出现w v合在一起不认识u 与题设矛盾 因此这时有d u d v n 1 因此必有Hamilton回路 中国邮递员问题 叙述方便起见就把边或途径的权称为它的长度 自然 我们可以提出这样的问题 在赋权连通图G中 找一条具有最小长度的闭途径 使它包含G的所有边 这个问题是管梅谷教授1960年在研究邮递员最优投递路线时 首先提出并解决的 1965年之后 国际上称之为 中国邮递员问题 如果图G是Euler型的 那么G的任何Euler闭链都是符合上述要求的最优途径 在这种情况下中国投递员问题是容易解决的 如果连通图G不是Euler型的 那么它有偶数个奇顶点 我们任选两个奇顶点u和v 在G中必有一条通路连接它们 将这条通路上的每一条边改为二重边 则u和v变为偶顶点 在这条道路上的其它点的度数均增加2 即奇偶性不变 于是G的奇顶点就减少了两个 重复这个过程 经若干次之后 可将G中所有奇顶点全部去掉 从而得到带有重复边的Euler图M M的一条EuIer闭链就相应于G的一条包含所有边的闭途径 这条闭途径的长度就等于G的所有边的长度加上每次连接奇顶点的通路的长度 怎样才能使闭途径的长度最短呢 下面的定理回答了这个问题 定理5 12设W是赋权图G的一条包含G的所有边的闭途径 则W具有最小长度的充要条件是 i 每条边最多重复一次 ii 在G的每个回路上 重复边的长度之和不超过该回路长度之半 奇偶点图上作业法 对任意赋权图G 首先把它的全部奇顶点两两配对 每对之间用加重复边的方法连接起来 奇顶点变成了偶顶点 这样G被变为一个带有重复边的Euler图 其次对于重复次数不小于2的边 其两端度数都减去2 得到的图仍为Euler图 然后 对每一个回路 分别检查重复边长度之和是否超过回路长度的一半 如果超过 则把重复边改为不重复边 把不重复边改为重复边 直到以上手续不能再进行为止 最后得到的带有重复边的Euler图在G上相应的闭途径就是最短闭途径 练习 证明在下图所示赋权图中xuywvzwyxuwvzyx是一条最优投递路线 旅行售货员问题 一个售货员要到若干有直通道路的城镇推销商品 然后回到出发地 他应如何计划旅行路线 才能使得对每个城镇都访问一次且仅仅一次 而且使总的行程最短 这就是所谓旅行售货员问题 也叫货郎担问题 用图论的语言说 这一问题的目的是在一个赋权完全图中 找出一条最小权Hamilton回路 直到目前为止 还没有求解这一问题的有效算法 所以人们希望找到一种简便易行而且能获得相当好 但不必最优 的结果的方法 下面我们介绍一种可以称为逐次改进法的方法 逐次改进法 在赋权完全图G上首先找出一条Hamilton回路C 然后适当修改C以使得到具有