第八章一些特殊的图2ppt课件_第1页
第八章一些特殊的图2ppt课件_第2页
第八章一些特殊的图2ppt课件_第3页
第八章一些特殊的图2ppt课件_第4页
第八章一些特殊的图2ppt课件_第5页
已阅读5页，还剩39页未读， 继续免费阅读

下载本文档

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

文档简介

1、 8.2 8.2 欧拉图欧拉图1 111111010(a)(a)12129 92 28 83 34 47 75 56 6l 甲、乙两只蚂蚁分别位于右下图中的结点甲、乙两只蚂蚁分别位于右下图中的结点a a，b b处，并设图中的边长度是相等的。处，并设图中的边长度是相等的。l 甲、乙进行比赛：从它们所在的结点出发，甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点走过图中的所有边最后到达结点c c处。处。l 如果它们的速度相同，如果它们的速度相同，l 问谁先到达目的地？问谁先到达目的地？l 在图中，仅有两个度数在图中，仅有两个度数l 为奇数的结点为奇数的结点b b，c c，l 因而

2、存在从因而存在从b b到到c c的欧拉通路。的欧拉通路。c cb(b(乙乙) )a(a(甲甲) )l 在图中，存在从在图中，存在从b到到c的欧拉通路，的欧拉通路，l 且蚂蚁乙从且蚂蚁乙从b到到c只要走一条边数为只要走一条边数为9的欧拉通路；的欧拉通路；l 而蚂蚁甲要想走完所有的边到达而蚂蚁甲要想走完所有的边到达c，l 至少要先走一条边从至少要先走一条边从a到达到达b，再走一条欧拉通路，再走一条欧拉通路l 因此，它至少要走因此，它至少要走10条边，条边，l 才能到达才能到达c，l 所以乙必胜。所以乙必胜。c cb(b(乙乙) )a(a(甲甲) )V1V1V2V2V3V3V4V4(a)(a)V8V8V2V2V4V4V6V6(c)(c)V1V1V3V3V5V5V7V7),(42567310eeeeeeee（Leonhard Euler 公元公元1707-1783年）年） sincosiei 先走先走 P Pv1e1v2e2v3e3v4e7v7v1e1v2e2v3e3v4e7v7，再往下走，就可以走出欧拉回路再往下走，就可以走出欧拉回路P Pv1e1v2e2v3e3v4e7v7e6v6e5v5e4v4e8v2e9v7e10vv1e

人人文库> 全部分类> 应用文书 > 工作计划

温馨提示

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

最新文档

评论

0/150

提交评论