图论 (7).ppt_第1页
图论 (7).ppt_第2页
图论 (7).ppt_第3页
图论 (7).ppt_第4页
图论 (7).ppt_第5页
已阅读5页,还剩20页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

杨春 Email yc517922 2020年2月7日星期五 离散数学 数学科学学院 2020 2 7 数学科学学院 37 2 第11章特殊图 11 2Euler图 哥尼斯堡七桥问题 2020 2 7 数学科学学院 37 3 欧拉图的定义 定义11 2 1设G是无孤立结点的图 若存在一 条通路 回路 经过图中每边一次且仅一次 则称此通路 回路 为该图的一条欧拉通路 回路 具有欧拉回路的图称为欧拉图 规定平凡图为欧拉图 2020 2 7 数学科学学院 37 4 例1 图a和图d是欧拉图 图b和图e不是欧拉图 但存在欧拉通路 图c和图f不存在欧拉通路 一笔画问题 2020 2 7 数学科学学院 37 5 判断无向欧拉通路的方法 定理11 2 1无向图G 具有一条欧拉通路当且仅当G是连通的 且仅有零个或者两个奇度数结点 若有两个奇度数结点 则它们是G中每条欧拉通路的端点 2020 2 7 数学科学学院 37 6 判断无向欧拉图的方法 推论11 2 2无向图G 是欧拉图当且仅当G是连通的 且G的所有结点的度数都为偶数 2020 2 7 数学科学学院 37 7 例2 由定理11 2 2容易看出 是欧拉图 不是欧拉图 但存在欧拉通路 即不是欧拉图 也不存在欧拉通路 2020 2 7 数学科学学院 37 8 一笔画问题 对于上图 有 图 a 能一笔画并且能回到出发点的 图 b 能一笔画但不能回到出发点的 2020 2 7 数学科学学院 37 9 判断有向欧拉通路 欧拉图的方法 定理11 2 3有向图G具有一条欧拉通路 当且仅当G是连通的 且除了两个结点以外 其余结点的入度等于出度 而这两个例外的结点中 一个结点的入度比出度大1 另一个结点的出度比入度大1 推论11 2 4有向图G具有一条欧拉回路 当且仅当G是连通的 且所有结点的入度等于出度 2020 2 7 数学科学学院 37 10 例3 图a 存在一条的欧拉通路 v3v1v2v3v4v1 图 b 中存在欧拉回路v1v2v3v4v1v3v1 因而 b 是欧拉图 图 c 中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而 c 是欧拉图 2020 2 7 数学科学学院 37 11 Fleury算法 任取v0 V 令P0 v0 设P0 v0e1v1e2 eivi 按下面的方法从E e1 e2 ei 中选取ei 1 ei 1与vi相关联 除非无别的边可选取 否则ei 1不应该为G G e1 e2 ei 中的桥 当2 不能再进行时 算法结束 2020 2 7 数学科学学院 37 12 例4 在右图所示的欧拉图中 求从v1出发的欧拉回路 如果P4 v1e1v2e2v3e3v4e7v7 再往下走 注意别走桥 就可以走出欧拉回路 P4 v1e1v2e2v3e3v4e7v7e6v6e5v5e4v4e8v2e9v7e10v1 2020 2 7 数学科学学院 37 13 13 2哈密尔顿图 周游世界问题 给定G是一个无孤立结点的无向图 若存在一条通路 回路 经过图中每个结点一次且仅仅一次 则称此通路 回路 为该图的一条哈密尔顿通路 回路 具有哈密尔顿回路的图称为哈密尔顿图 2020 2 7 数学科学学院 37 14 11 3哈密尔顿图的定义 定义11 3 1经过图中每个结点一次且仅一次的通路 回路 称为哈密尔顿通路 回路 存在哈密尔顿回路的图称为哈密尔顿图 规定平凡图为哈密尔顿图 2020 2 7 数学科学学院 37 15 例5 既存在哈密尔顿通路 又存在哈密尔顿回路 即为哈密尔顿图 既不存在哈密尔顿通路 也不存在哈密尔顿回路 既存在哈密尔顿通路 又存在哈密尔顿回路 即为哈密尔顿图 存在哈密尔顿通路 但不存在哈密尔顿回路 2020 2 7 数学科学学院 37 16 定理11 3 1 设无向图G 是哈密尔顿图 V1是V的任意非空子集 则p G V1 V1 其中p G V1 是从G中删除V1后所得到图的连通分支数 2020 2 7 数学科学学院 37 17 证明 设C是G中的一条哈密尔顿回路 V1是V的任意非空子集 下面分两种情况讨论 V1中结点在C中均相邻 删除C上V1中各结点及关联的边后 C V1仍是连通的 但已非回路 因此p C V1 1 V1 V1中结点在C上存在r 2 r V1 个互不相邻 删除C上V1中各结点及关联的边后 将C分为互不相连的r段 即p C V1 r V1 一般情况下 V1中的结点在C中即有相邻的 又有不相邻的 因此总有p C V1 V1 又因C是G的生成子图 从而C V1也是G V1的生成子图 故有p G V1 p C V1 V1 2020 2 7 数学科学学院 37 18 推论13 3 1 设无向图G 中存在哈密尔顿通路 则对V的任意非空子集V1 都有p G V1 V1 1 2020 2 7 数学科学学院 37 19 定理在应用中它本身用处不大 但它的逆否命题却非常有用 我们经常利用定理的逆否命题来判断某些图不是哈密尔顿图 即 若存在V的某个非空子集V1使得p G V1 V1 则G不是哈密尔顿图 例如在上图中取V1 v1 v2 则p G V1 4 V1 2 因而该图不是哈密尔顿图 注意 定理给出的是哈密尔顿图的必要条件 而不是充分条件 下图所示的彼得森图 对V的任意非空子集V1 均满足p G V1 V1 但它不是哈密尔顿图 2020 2 7 数学科学学院 37 20 定理11 3 2 设G 是具有n个结点的简单无向图 如果对任意两个不相邻的结点u v V 均有deg u deg v n 1则G中存在哈密尔顿通路 2020 2 7 数学科学学院 37 21 推论 推论11 3 2设G 是具有n个结点的简单无向图 如果对任意两个不相邻的结点u v V 均有deg u deg v n则G中存在哈密尔顿回路 推论11 3 3设G 是具有n个结点的简单无向图 n 3 如果对任意v V 均有deg v n 2 则G是哈密尔顿图 2020 2 7 数学科学学院 37 22 例6 某地有5个风景点 若每个风景点均有两条道路与其他点相通 问游人可否经过每个风景点恰好一次而游完这5处 解将5个风景点看成是有5个结点的无向图 两风景点间的道路看成是无向图的边 因为每处均有两条道路与其他结点相通 故每个结点的度数均为2 从而任意两个不相邻的结点的度数之和等于4 正好为总结点数减1 故此图中存在一条哈密尔顿通路 因此本题有解 2020 2 7 数学科学学院 37 23 例7 证明下图 a 所示的图中 不存在哈密尔顿回路 证明 在图 a 中 删除结点子集V1 a b c 得到图 b 在图 b 中 它的连通分支为4 显然有 p G V1 4 V1 3 由定理13 3可知 图 a 所示的图中不会存在哈密尔顿回路 即不是哈密尔顿图 2020 2 7 数学科学学院 37 24 例7 判断右图所示的图是否存在哈密尔顿回路 解若该图中存在哈密尔顿回路 则该回路组成的图中任何结点的度数均为 2 因而结点1 2 3 4 5所关联的边均在回路中 于是在结点a b c d e处均应将不与1 2 3 4 5关联的边删除 而要删除与结点a b c d e关联的其他边 这样一来 图就不连通了 因而图中不存在哈密尔顿回路 2020 2 7 数学科学学院

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论