引用:
原帖由 火车是运茶的 于 2013-4-23 21:00 发表
1、我们已经知道能够一笔画成的图必定有零个或两个奇数点。那么反过来,是否具有零个或两个奇数点的图(连通的)一定能够一笔画成。
2、如果已经知道一张图能够一笔画成并且没有奇数点,请问这张图是否从任意一个点开始都可以一笔画成。
第一个问题,百度百科上有一个采用数学归纳法的证明:
http://baike.baidu.com/view/429465.htm
反之,设G连通,且每个顶点的度均为偶数,欲证G为一欧拉图。为此,对G的边数归纳。当m = 1时,G必定为单结点的环,显然这时G为欧拉图。设边数少于m的连通图,在顶点度均为偶数时必为欧拉图,现考虑有m条边的图G。设想从G的任一点出发,沿着边构画,使笔不离开图且不在构画过的边上重新构画。由于每个顶点都是偶数度,笔在进入一个结点后总能离开那个结点,除非笔回到了起点。在笔回到起点时,它构画出一条闭路径,记为H。从图G中删去H的所有边,所得图记为G’,G’未必连通,但其各顶点的度数仍均为偶数.考虑G的各连通分支,由于它们都连通,顶点度数均为偶数,而边数均小于m,因此据归纳假设,它们都是欧拉图。此外,由于G连通,它们都与H共有一个或若干个公共顶点,因此,它们与H一起构成一个闭路径。这就是说,G是一个欧拉图。
这个证明是错误的。在递推过程中,它假设笔肯定能回到起点。但是递推假设仅仅假设边数少于m方能回到起点。
设想两个结点A和B,从A到B引一条边,从B到A再引另一条边,这样得到的图有两个结点两条边。这个图无法从“当m = 1时,G必定为单结点的环”递推而得。在递推过程中,两条边的情形是需要证明的;但是除非经过两条边,笔无法回到起点。因此其“在笔回到起点时,它构画出一条闭路径”不能成立。
[
本帖最后由 火车是运茶的 于 2014-3-26 19:48 编辑 ].