七桥问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
及其证明七桥问题对很多人来说并不是陌生的名词，尤其当它已经被写进了小学数学课本……不过，此处还是再来啰嗦地介绍一下七桥问题到底是怎样的一个命题。传说在18世纪普鲁士的哥尼斯堡城，有一条叫做普雷格尔的河，河中间有两个岛，有七座桥把这两个岛与河岸相连，就像下面这个示意图里左图给出的一样。市民们饭后茶余就在讨论，能不能不重复的经过每一座桥而回到出发点呢。这个问题也可以被简化成右图是否能够被一笔画的问题。大数学家欧拉思考过后认为，市民们一直在找寻的那条路径是不存在的，把每座桥看成图的一个边（右图），想要不重复的经过每一条边而回到原点，则每个顶点必须有偶数条边与之相连，才能满足从一条边来从另一条边出。用图论的语言来说，一个非空连通图是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相连的边的数量）细心而学究的人会发现，上面仅仅是对命题的必要性证明，那么，充分性的证明呢？当一个非空连通图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闭迹后，剩下的节点度之和还是偶数，说明还有闭迹……最后可知整个图便只有整个一个最大的闭迹就是Euler闭迹了~
浙公网安备 33021202002483