【www.xushengjz.com--小学教案】

　　七桥问题及其证明_军事/政治_人文社科_专业资料。七桥问题对很多人来说并不是陌生的名词,尤其当它已经被写进了小学数学课本……不过,此处还是再来啰嗦地介绍一下七桥问题到底是怎样的一个命题。 传说在18世纪普鲁士的哥尼斯堡城,有一条叫做普雷格尔的河,河中间有两个岛,有七座桥把这两个岛与河岸相连,就像下面这个示意图里左图给出的一样。

　　七桥问题及其证明 七桥问题对很多人来说并不是陌生的名词，尤其当它已经被写进 了小学数学课本……不过， 此处还是再来啰嗦地介绍一下七桥问题到 底是怎样的一个命题。 传说在 18 世纪普鲁士的哥尼斯堡城，有一条叫做普雷格尔的河， 河中间有两个岛，有七座桥把这两个岛与河岸相连，就像下面这个示 意图里左图给出的一样。市民们饭后茶余就在讨论，能不能不重复的 经过每一座桥而回到出发点呢。 这个问题也可以被简化成右图是否能 够被一笔画的问题。 大数学家欧拉思考过后认为，市民们一直在找寻的那条路径是不 存在的，把每座桥看成图的一个边（右图） ，想要不重复的经过每一 条边而回到原点，则每个顶点必须有偶数条边与之相连，才能满足从 一条边来从另一条边出。 用图论的语言来说， 一个非空连通图是 Euler 图当且仅当它没有奇度顶点。 这里 Euler 图指的是有 Euler 闭迹的图，而 Euler 闭迹是，经过图 G 的每条边恰好一次的闭迹。有了这样的定义，上面的“七桥问题一 笔画是不可能的”论证过程可以这样表述： 设图 G 是 Euler 图， 是 G C 中一个 Euler 闭迹。对 G 中任一个顶点 v，v 必在 C 上出现。因 C 每 经过 v 一次，就有两条与 V 关联的边被使用。设 C 经过 v 共 k 次， 则 C 经过了 2k 条与 v 关联的边，故 v 的度为 2k（节点 v 的度指图 G 中与 v 相连的边的数量） 细心而学究的人会发现，上面仅仅是对命题的必要性证明，那么， 充分性的证明呢？当一个非空连通图 G 的每个顶点都是偶度顶点， 那图 G 就有 Euler 闭迹吗？直接证明这个比较困难， 可以用反证法来 证明： 无妨设图Ｇ的顶点个数 n 1。因 G 连通，故至少有一条边。假设 图 G 无奇度顶点，但它不是 Euler 图。令 S = {G G 是至少有一条边 的 n 阶连通图，无奇度顶点，且不是 Euler 图}，则 S 非空。取 S 中 边数最少的一个，记为 G0。因 G0 无奇度顶点，故 G0 中顶点的度至 少为 2，因此 G0 含有圈，从而含有闭迹。设 C 是中一条最长的闭迹。 由假设，C 不是 G0 的 Euler 闭迹。因此 G0 中将 C 的边去掉后必有 一个连通分支至少含有一条边。记这个连通分支为 G1。由于 C 是闭 迹，故 G1 中没有奇度顶点，且 G1 的边少于 G0 的边。由 G0 的选择 可知，G1 必有 Euler 闭迹，记为 C1。因此 C＋C1 是的一条闭迹，且 它比 C 更长，这与 C 的选取矛盾。证毕。 是不是看的稀里糊涂呢？其实仔细想想不难理解，考虑所有节点 度之和为偶数，则除去一个 Euler 闭迹后，剩下的节点度之和还是偶 数， 说明还有闭迹……最后可知整个图便只有整个一个最大的闭迹就 是 Euler 闭迹了~

本文来源：http://www.xushengjz.com/jiaoan/118053/