发新话题
打印【有8个人次参与评价】

[数学] 火车数学俱乐部(148#注意力训练软件)

回复 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点出发一笔画。

这样,第二个问题就被证明成立。.

TOP

回复 97楼火车是运茶的 的帖子

你问的是我的以下这个判断吗?
“因为该图形是联通的(即没有和其他所有的点都不相连的点),那么从任意一个点出发都可以不经过某一点2次到达其他任意一个点(可用数学归纳法简单地证明)。”
我想了一下,似乎数学归纳法有点难,但可以用构造法简单证明。午休时多写几句,请指正。

一,判断一个有限的点集是否通过连接点和点之间的线段“联通”的,可以定义以下识别方法:
       首先,从该点集中任选某点pi,对pi考察其余所有点和它的联通关系。存在三种情况(1)其余所有的点都和pi直接相连,出现这种情况即识别为“联通”;(2)其余部分点(其集合记为Ci)和pi直接相连,部分(记为Ui)不和Pi直接相连,(3)其余全部点与pi均不直接相连,直接判定为“非联通”。  
       其次,在(2)的情况下,再对Ci考察Ui与Ci中每个点的关系,存在三种情况(1)Ui中的每个点都和至少一个Ci中的点直接相连,出现这种情况即识别为“联通”;(2)存在部分Ui中的点(Ci2)和至少一个Ci中的点直接相连,其余部分Ui中的点(Ui2)与任何Ci中的点都不直接联通。(3)所有Ui中的点都不和任何Ci中的点直接相连,则直接判定为“非联通”。
       每重复一次判断,不出现(1)和(3)的判断结果的话,Uin所包含的点的数量必然减少至少1个,所以在有限次步骤后,必然会得出“联通”或“非联通”的判定结果。
       注意到每次判断步骤中的Cin集合中的点和点之间是否相连不影响最终的判定结果,并且待判定部分的点和已联通部分的点集中一个点相连还是多个点相连不影响最终判定结果。

二,构造法证明“因为该图形是联通的(即没有和其他所有的点都不相连的点),那么从任意一个点出发都可以不经过某一点2次到达其他任意一个点。”

      从某点a开始,可以通过如下方法找到至少一条不经过某一点2次到达其他任意一个点的路径。
      首先,选出所有和a直接相连的点Ca1,这些点显然和A之间存在我们要找的路径。
      其次,擦去Ca1中的点和点相互直接相连的线段。根据之前的判定方法,我们知道擦掉这些线段不会改变联通性。
      根据定义,在除去a点和Ca1中的点的其余点Z里,必然有部分点和Ca1中的至少一个点直接相连。于是,我们将Ca1和Z中的哪些点直接相连。考察完毕后,擦去Z中的点和点直接相连的线。如果Z中某个点和Ca1中1个以上的点直接相连的,只保留一条直接相连的线段,其他擦掉(根据判断方法,这不会改变联通性)。
      重复以上步骤,可以把一个联通的图转换为一个顶点为a点的树状图。任何一个其余的点都有一条唯一的路径,“从下往上” 地,不经过某一点2次到达a点。.

TOP

发新话题