1楼jyuntoku
(......)
发表于 2014-3-21 13:48
显示全部帖子
回复 11楼老猫 的帖子
第二个题目不难。
因为该图形是联通的(即没有和其他所有的点都不相连的点),那么从任意一个点出发都可以不经过某一点2次到达其他任意一个点(可用数学归纳法简单地证明)。我们可以把从任意A点到B点的不经过某一点2次的某种联通路径称为AB路径。AB路径的特征是,除AB两个点各有一条线段相连外,其他的点都有2条线段相连(一进一出)。我们可以证明或或简单看出AB路径可以从A点或B点开始一笔画。
假设从A点出发能一笔画,现在任选B点开始,可以把一笔画任务分解为,从B到A的AB路径的一笔画,及除去AB路径后的原图形从A开始的一笔画,这两个任务。从B到A的AB路径可以一笔画。除去AB路径后的原图形,是一个A点和B点为奇数点,其他点为偶数点的图形,可以从A点出发一笔画。
这样,第二个问题就被证明成立。.