ppt16电子科大图论上课ppt及复习总结杨春.ppt

1 Email yc517922 图论及其应用 任课教师 杨春 数学科学学院 2 本次课主要内容 二 E图和H图的关系 超哈密尔顿图问题 一 超H图与超H迹 3 定义1若图G是非H图 但对于G中任意点v 都有G v是H图 则称G是超H图 一 超H图与超H迹 定理1彼得森图是超H图 证明 1 证明彼得森图是非H图 4 若不然 设C是G的H圈 又对于边28 23来说 在前面情况下 必有一条在C中 分两种情形讨论 对于边12 17 15来说 必然有两条边在C中 不失一般性 假定17 12在C中 那么 56 54也必然在C中 5 但这样得到圈 17 10 821 所以该情形不能存在 情形1 假如28在C中 则39 34在C中 从而7 10 8 10 在C中 6 但这样得到圈 123971 所以该情形也不能存在 情形2 假如23在C中 则86 8 10 在C中 从而39 79在C中 上面推理说明 G中不存在H圈 即彼得森图是非H图 7 由对称性 只需考虑下面两种情形 a G 1 b G 6 2 证明对任意点v G v是H图 a G 1中有H圈 54328 10 7965 b G 6中有H圈 54397 10 8215 由 1 与 2 G是超H图 8 定义2若G中没有H路 但是对G中任意点v G v存在H路 则称G是超可迹的 数学家加莱曾经猜想 不存在超可迹的图 但该猜想被Horton和Thomassen以构图的方式否定了 定理2Thomassen图是超可迹图 9 定理证明分为两部分 1 证明G中不存在H路 2 证明对G中任意点v 有G v存在H路 1 证明G中不存在H路 如图所示 将G用虚线分成对称的4部分 假设G有H路P 设该路的起点为 终点为 不失一般性 设 a 断言1 a 中不存在以a c d三点中任意两点为端点的H路 若不然 将推出彼得森图是H图 10 断言2 a b 中不存在以a为端点的H路 若不然 设Q是一条以a为起点的 a b 中的H路 那么 从a出发 沿着该路行走有两种可能 1 遍历了 中所有点之后 从c或d进入 但这形成了 a 中的以a c或a d为端点的H路 与断言1矛盾 2 没有遍历完 a 中的顶点 假若从c进入 那么 必须遍历完 b 的所有顶点后 才能从e进入 但这也会与断言1产生矛盾 11 情形1 a 所以 情形1不能成立 由前面假设 a 我们沿着P作如下的行进 1 假设是由a进入 要能够走完P 必须遍历 的所有顶点后由b进入 但这与断言2矛盾 2 假设是由a进入 要能够走完P 必须遍历 的所有顶点后由b进入 但这也与断言2矛盾 12 情形2 a 所以 情形2也不能成立 我们沿着P作如下的行进 1 假设是由 遍历了 b 所有顶点从a进入 这与断言2矛盾 同样 假设是由 遍历了 a 所有顶点从b进入 这也与断言2矛盾 2 假设是由 开始 没有遍历 a b 而从a或b进入 那么 要走完P 都必须遍历完 的所有顶点后 才能重新进入 但这要与断言2矛盾 13 综合上面的论述 得G中没有H路 2 证明对G中任意点v 有G v存在H路 由对称性 我们取b和 中顶点逐一分析即可 例如 综上所述 得Thomassen图是超可迹图 14 关于H图的一些猜想 1 加莱猜想 不存在超可迹的图 加莱猜想是错误的 Thomassen图否定了加莱猜想 加莱 1912 1992 匈牙利数学家 他和Erdos 托兰是当时匈牙利国家数学竞赛获胜者 后来成为一生的朋友 加莱深受哥尼的影响而对图论产生极大兴趣 以至于他对图论基础理论做出了重大贡献 推动了图论与组合数学的迅速发展 同时 他也是最早认识所谓的 极小 极大定理 重要性的数学家之一 加莱为人谦虚低调 很少在公开场合露面 常常在赞扬别人工作时低估自己的成绩 不喜欢发表自己研究成果 15 2 泰特猜想 任何3连通3正则可平面图是H图 泰特猜想也是错误的 托特1946年构图否定了泰特猜想 Lederberg等构造了最小的3连通3正则图非H图 有38个点 16 如果泰特猜想正确 4色定理可得到证明 托特 1917 2002 英国著名数学家 1935年 入剑桥三一学院学习化学 并攻读了化学研究生 撰写了2篇化学论文 但是 他的兴趣是数学 在剑桥 他结识了3位数学专业的本科学生并成为终身朋友 合作发表数学论文 二战后 托特回到剑桥攻读数学研究生 研究生期间 发表了关于图的因子分解论文 在他的数学博士论文中 复兴了拟阵理论 惠特尼引入的 1948年博士毕业后 受20世纪伟大的几何学家Coxeter邀请前往多伦多大学任教 成为组合数学杰出学者 5年后到滑铁卢大学工作直到1984年退休 托特是20世纪伟大的数学家之一 在近代数学史上占有一定的地位 主要功绩是提出并证明了图的完美匹配定理 17 托特还喜欢写诗 在1969年写了一首反映图论的诗 哥尼斯堡的一些市民 漫步在河畔 在普雷格尔河旁 有七座桥相伴 Euler 我们一起散步吧 那些市民在召唤 我们在这七座桥上漫步 经过每座桥仅一次 你们做不到 Euler大声吼道 结果就是这样 岛屿作为顶点 四个点有奇数度 从哥尼斯堡到哥尼的书 图论的传说正是如此 而且越来越精彩 绽放在密歇根和耶鲁 18 该猜想错误 Meredith构图对猜想进行了否定 3 纳什 威廉斯猜想 每个4连通4正则图是H图 Meredith图是由彼得森图的每个顶点嵌入一个K3 4作成 19 该猜想错误 Coxeter构图对猜想进行了否定 4 托特猜想 每个3连通3正则偶图是H图 20 该猜想是正确的 已经得到证明 5 普鲁默猜想 每个2连通图的平方是H图 定义 图G的平方G2是这样的图 值得一提的是 在H问题研究中 H图中H圈的计数问题也是一个研究方向 21 定理 每个3正则H图至少有3个生成圈 我院张先迪 李正良教授曾经也研究过H图中H圈的计数问题 90年在 系统科学与数学 学报上发表文章 有限循环群上Cayley有向图的H回路 得到了该类图的H圈的计数公式 二 E图和H图的关系 从表面上看 E图与H图间没有联系 因为我们可以不费力地找到 1 E图但非H图 2 E图且H图 3 H图但非E图 4 非E图且非H图 22 定义3设G是图 G的线图L G 定义为 特别地 定义G的n次迭线图Ln G 为 1 线图概念 23 1 线图L G 顶点数等于G的边数 若e uv是G的边 则e作为L G 的顶点度数为 d e d u d v 2 2 线图的性质 2 若G n m 则线图L G 边数为 证明 由线图的定义 L G 有m个顶点 对于G中任一顶点v 关联于该顶点的d v 条边将产生L G 中条边 所以L G 中的总边数为 24 3 一个图同构于它的线图 当且仅当它是圈 4 若图G和G1有同构的线图 则除了一个是K3而另一个是K1 3外 G和G1同构 证明比较复杂 3 从线图的角度考察E图与H图的关系 定义4称Sn是图G的n次细分图 是指将G的每条边中都插入n个2度顶点 又记 25 定理3 1 若G是E图 则L G 既是E图又是H图 2 若G是H图 则L G 是H图 注 该定理逆不成立 定理4一个图G是E图的充要条件是L3 G 为H图 26 定理5 Chartarand 若G是n个点的非平凡连通图 且不是一条路 则对所有m n 3 Lm G 是H图 27 作业 请总结本章内容 28 ThankYou