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

一笔画问题及解决策略 一、问题提出 一笔画是一个大问题， 为了更好的解决这个问题， 我们从生活提出一笔画问题。 我们先 看一个公路检查员的问题： 他为了检查几个城市之间的若干公路， 希望在这些城市和公路组 成的公路系统中找出一条路线， 使他能不重复地恰好通过每条公路一次， 而经过每个城市的 次数不限。这就是拓扑学中的数学问题。 二、问题解决 （一） 数学化 我们把这问题数学化， 以点表示城市， 以弧表示公路， 这样构成的网络图就表示某个简 单公路系统。 （二） 点线图 用点线图表示四个不同的公路系统。如图所示： （三） 一笔画的含义 一个图形由一笔构成叫一笔画。 对于平面图形的一笔画与多笔画问题， 通常的几何方法 是无能为力的， 因为一个图形能否一笔画，与图形的大小、形状等几何概念都没有关系，而 是与图形中线段的数目及连接关系有关， 我们可以随意地将图形拉伸、 压缩或弯曲， 甚至在 保持端点不动的前提下，还可以将某些线段“搬家” ，只要图形的整体结构不变，能否一笔 画的性质也就不会改变。 （四） 一笔画图形的判别 着名的哥尼斯堡七桥问题实质上就是一个一笔画问题。 欧拉最终证明了这个图形是不能 一笔画成的，并在关于七桥问题的报告中得到了任一网络图能否一笔画的判别法则。 1.必要条件 一个网络图是由有限个点和有限条曲线组成的平面图形， 这些点和线分别称为网络的顶 点和弧。 如果从网络的一个顶点出发， 一条弧连着一条弧地把所有的弧都画出， 且每条弧都 只画一次，而经过每个顶点的次数不限，就称该网络能一笔画。 当一个网络能一笔画时， 只有两种情形： 一是开放图形， 只有起点和终点的指数为奇数，其 余顶点的指数均为偶数； 二是封闭图形， 所有顶点的指数均为偶数。 我们称指数为奇数的顶 点为奇顶点，指数为偶数的顶点为偶顶点，那么当一个网络能一笔画时，奇顶点个数必为 0 或 2，所以，连通且奇顶点的个数是 0 或 2 ，是一个网络图能一笔画的必要条件。 （1）.凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一 定能以这个点为终点画完此图。 （2 ）.凡是只有两个奇点的连通图（其余都为偶点） ，一定可以一笔画成。画时必须把一个 奇点为起点，另一个奇点终点。 （3 ）.其他情况的图都不能一笔画出。 (奇点数除以二便可算出此图需几笔画成。 ) 2.充分条件 在讨论一笔画问题的判别的充分条件前， 先要证明一个引理： 在任一网络图中决不能只 有一个奇顶点。 由于任一顶点的指数是指相交于这一顶点处的弧数， 所以网络中所有顶点的 指数之和等于相交于每个顶点处的弧数的总和， 从而等于网络图总数的 2 倍，故任一网络图 中所有顶点的指数之和一定是偶数。 而若某个网络中只有一个奇顶点， 那么除该顶点的指数 是奇数外， 其余任一顶点的指数均为偶数， 所以该网络中所有顶点的指数之和就是奇数。 矛 盾。所以任一网络中都不可能只有一个奇顶点。 设一个连通网络中奇顶点个数是 2 或 0 ，那么该网络图可以一笔画。 分两种情形来讨论： 、 （1） 若连通网络的奇顶点个数是 0 个，则该网络中每