一笔画问题及解决策略.doc

一笔画问题及解决策略一、问题提出一笔画是一个大问题，为了更好的解决这个问题，我们从生活提出一笔画问题。我们先看一个公路检查员的问题：他为了检查几个城市之间的若干公路，希望在这些城市和公路组成的公路系统中找出一条路线，使他能不重复地恰好通过每条公路一次，而经过每个城市的次数不限。这就是拓扑学中的数学问题。二、问题解决（一） 数学化我们把这问题数学化，以点表示城市，以弧表示公路，这样构成的网络图就表示某个简单公路系统。（二） 点线图用点线图表示四个不同的公路系统。如图所示：（三） 一笔画的含义一个图形由一笔构成叫一笔画。对于平面图形的一笔画与多笔画问题，通常的几何方法是无能为力的，因为一个图形能否一笔画，与图形的大小、形状等几何概念都没有关系，而是与图形中线段的数目及连接关系有关，我们可以随意地将图形拉伸、压缩或弯曲，甚至在保持端点不动的前提下，还可以将某些线段“搬家”，只要图形的整体结构不变，能否一笔画的性质也就不会改变。（四） 一笔画图形的判别著名的哥尼斯堡七桥问题实质上就是一个一笔画问题。欧拉最终证明了这个图形是不能一笔画成的，并在关于七桥问题的报告中得到了任一网络图能否一笔画的判别法则。1.必要条件一个网络图是由有限个点和有限条曲线组成的平面图形，这些点和线分别称为网络的顶点和弧。如果从网络的一个顶点出发，一条弧连着一条弧地把所有的弧都画出，且每条弧都只画一次，而经过每个顶点的次数不限，就称该网络能一笔画。当一个网络能一笔画时，只有两种情形：一是开放图形，只有起点和终点的指数为奇数，其余顶点的指数均为偶数；二是封闭图形，所有顶点的指数均为偶数。我们称指数为奇数的顶点为奇顶点，指数为偶数的顶点为偶顶点，那么当一个网络能一笔画时，奇顶点个数必为0或2，所以，连通且奇顶点的个数是0或2，是一个网络图能一笔画的必要条件。（1）.凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。（2）.凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。 （3）.其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)2.充分条件在讨论一笔画问题的判别的充分条件前，先要证明一个引理：在任一网络图中决不能只有一个奇顶点。由于任一顶点的指数是指相交于这一顶点处的弧数，所以网络中所有顶点的指数之和等于相交于每个顶点处的弧数的总和，从而等于网络图总数的2倍，故任一网络图中所有顶点的指数之和一定是偶数。而若某个网络中只有一个奇顶点，那么除该顶点的指数是奇数外，其余任一顶点的指数均为偶数，所以该网络中所有顶点的指数之和就是奇数。矛盾。所以任一网络中都不可能只有一个奇顶点。设一个连通网络中奇顶点个数是2或0，那么该网络图可以一笔画。分两种情形来讨论：、（1） 若连通网络的奇顶点个数是0个，则该网络中每个顶点都是偶顶点。如图，取任一顶点A和以为起点的一条弧AB。在网络中去掉弧AB,于是减少1，顶点数不变，A和B变为奇顶点，其余顶点仍然是偶顶点。此时，剩下的网络图仍然是连通的，这是因为，如果去掉弧AB后网络分离为没有联系的两个连通分支，那么顶点A和B就分别在两个不同的分支中，其中任一连通分支都只有一个奇顶点，这由引理可知是绝不可能的。所以，该网络去掉弧AB后剩下的网络一定是奇顶点个数为2的连通图，且比原网络减少一条弧。（2） 若连通网络的奇顶点个数为2，如图，设网络中只有A和D两个奇顶点，其余顶点都是偶顶点，考察A的两种情形：网络中存在于顶点A相邻的偶顶点，如图（a）中的顶点B。去掉弧AB后剩下的网络会有两种可能现象：若剩下的仍然是联通连通网络，则顶点A变为偶顶点，B变为奇顶点，故网络中只有B和D两个奇顶点，弧数比原网络减少了1；若剩下的分离为两个网络，中间无联系，则有引理可知，奇顶点B和D必然在同一连通分支中，而顶点A必在另一个连通分支中，此时我们将弧AB补上去，而去掉AC如图(b),就得到一个只有C和D两个奇顶点的连通网络，且弧数比原网络减少1。.网络中不存在与顶点A相邻的偶顶点，如图，那么网络中与A相邻的就只有奇顶点D，此时去掉弧AD，就会去掉顶点A或使A变为偶顶点，顶点也变为偶顶点，所以剩下的是一个个无奇顶点的连通网络，且弧数比原来的少1。3.充分必要条件一个网络能一笔画的充要条件是它是连通的，且奇顶点的个数为0或2.（五）实际应用1.一辆洒水车要给某城市的街道洒水，街道地图如下：你能否设计一条洒水车洒水的路线，使洒水车不重复地走过所有的街道，再回到出发点2、下图是一个公园的平面图，能不能 使游人走遍每一条路不重复？入口和出口 又应设在哪儿3、甲乙两个邮递员去送信，两人同时出发以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？三、揭示的意义一笔画问题的成功解决，其中蕴含的数学思想和策略，仍有着重要而现实的教育意义。品味一笔画问题鼓励学生大胆猜想，提高抽象分析能力，重视符号处理技巧，培养数学建模能力，树立正确数学观念。解决“ 七桥问题”的困难之处何在呢？显然最困难之处在于把它简化成网络图。在欧拉之前解这道题的人之所以未能成功，主要在于他们或者没有想到要简化问题，或者作不出欧拉的网络图。不难看出，如果网络图已经有了，再来研究它能否一笔画，难度就小多了，相信在那批首先研究这个问题的人中，肯定有人能解决它。而现实的数学问题当然是类似“