七桥问题及其证明_第1页
七桥问题及其证明_第2页
七桥问题及其证明_第3页
全文预览已结束

下载本文档

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

文档简介

1、七桥问题及其证明七桥问题对很多人来说并不是陌生的名词，尤其当它已经被写进 了小学数学课本 不过，此处还是再来啰嗦地介绍一下七桥问题到 底是怎样的一个命题。传说在18世纪普鲁士的哥尼斯堡城，有一条叫做普雷格尔的河， 河中间有两个岛，有七座桥把这两个岛与河岸相连， 就像下面这个示 意图里左图给出的一样。市民们饭后茶余就在讨论，能不能不重复的 经过每一座桥而回到出发点呢。这个问题也可以被简化成右图是否能 够被一笔画的问题。大数学家欧拉思考过后认为，市民们一直在找寻的那条路径是不 存在的，把每座桥看成图的一个边（右图），想要不重复的经过每一 条边而回到原点，则每个顶点必须有偶数条边与之相连， 才能满足

2、从 一条边来从另一条边出。用图论的语言来说，一个非空连通图是Euler 图当且仅当它没有奇度顶点。这里Euler图指的是有Euler闭迹的图，而Euler闭迹是，经过图 G的每条边恰好一次的闭迹。有了这样的定义，上面的七桥问题一笔画是不可能的”论证过程可以这样表述：设图G是Euler图，C是G 中一个 Euler 闭迹。对 G 中任一个顶点 v ，v 必在 C 上出现。因 C 每 经过 v 一次，就有两条与 V 关联的边被使用。设 C 经过 v 共 k 次， 则C经过了 2k条与v关联的边，故v的度为2k （节点v的度指图G 中与 v 相连的边的数量）细心而学究的人会发现， 上面仅仅是对命题的

3、必要性证明， 那么， 充分性的证明呢？当一个非空连通图 G 的每个顶点都是偶度顶点， 那图 G 就有 Euler 闭迹吗？直接证明这个比较困难， 可以用反证法来 证明：无妨设图G的顶点个数n 1。因G连通，故至少有一条边。假设 图G无奇度顶点，但它不是 Euler图。令S = G | G是至少有一条边 的n阶连通图，无奇度顶点，且不是 Euler图，则S非空。取S中 边数最少的一个，记为GO。因G0无奇度顶点，故G0中顶点的度至 少为2,因此GO含有圈，从而含有闭迹。设C是中一条最长的闭迹。 由假设， C 不是 GO 的 Euler 闭迹。因此 GO 中将 C 的边去掉后必有 一个连通分支至少含有一条边。记这个连通分支为G1。由于C是闭迹，故G1中没有奇度顶点，且G1的边少于GO的边。由GO的选择 可知，G1必有Euler闭迹，记为C1。因此C+ C1是的一条闭迹，且 它比C更长，这与C的选取矛盾。证毕。是不是看的稀里糊涂呢？其实仔细想想不难理解，考虑所有节点 度之和为偶数，则除去一个 Euler

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

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

最新文档

评论

0/150

提交评论