一笔画问题

一笔画问题与图论所谓—笔画问题就是使笔尖不离开纸面而又不重复地画出一个图形、这个问题起源于十八世纪所谓“哥尼斯堡桥”的难题：在一条河流中有两个小岛，岛与岸之间用七座桥相连(图一)，怎样才能不重复地走遍七座桥而回到出发地点?如果我们把岛A、B分别以点v l、v2表示，岸C，D分别以点v3、v4表示，而各桥用连接各点的线表示，就可以得到下面的示意图(图二)、上面的问题就是问是否能一笔画成这样的图、不少人曾为此花费了大量时间，直到1736年大数学家欧拉才解决了这一问题、然而由此引起的对图形的研究却开创了一个新的数学分支，这就是在近代发展很快而且颇受重视的图论、图2我们首先介绍一些图论中最基本的术语，然后看看与上面一笔画问题的有关结论，最后简略地说明一下图论的其它应用、1、图我们把一些点和连接这些点之间的线称为一个图，其中的点叫做顶点，线叫做边、交于同一个顶点的两条边以及同一条边所连接的两个顶点都叫做相邻，而顶点与以它为端点的边之间叫做相关、如图二中与v l相邻的顶点有v2、v3、v4，而与v l相关的边有e l、e2、e3、e4、e6与e5相邻的边有e l、e2、e6、e7，而与e5相关的顶点有v2、v3、只有假设干个顶点而没有边的图叫做空图，而任何两个顶点之间都恰有一条边相连的图叫做完全图、有n个顶点的完全图常记为K n，例如K2就是一条线段，K就是有三个顶点三条边的图，按通常习惯仍叫三角形、32、子图在一个图中，由一部分顶点以及只与这些顶点相关的边所组成的图叫做导出子图，图中一部分边及其端点所组成的图叫做边导出子图，假设边导出子图与原图有完全相同的顶点，就叫做伸延子图、一个图的两个子图假设无公共顶点就叫做不相连的，假设无公共边(可能有公共顶点)就称为边不相连的、图三是一个具体例子、子图是一个相对的概念，假设H是G的子图，那么G可称为H的上图、通过子图来研究较复杂的图是图论中一个基本方法、3、顶点的度在一个图中与任一顶点v有关的边的数目，叫做这个顶点的度，记作d(v)，如图三中的G，d(v l)=2，d(v2)=5，d(v3)=4，d(v4)=2，d(v5)=3、这样一来，我们就看到在计算各个顶点的度时，实际上就是计算了边的数目，但每一条边在它的两个顶点处各计算一次，从而我们可以得到：定理一任一个图中各顶点的度数之总和等于其边数的二倍、由此事实，我们知道图中顶点度数之和为偶数，从而奇数度顶点的个数必为偶数、4、连通性在一个图中，我们从任一顶点v0出发，经过与之相关的一条边el到达另一个顶点v l，再经过与v l相关的一条边e2到达v2，……，如此继续下去，便得到一个顶点和边交替出现的序列v0e l v l e2v2……e k v k、当其中所经过的边彼此皆不相同时，我们就叫做一条迹，这时其中诸顶点有可能相同，假设连顶点也都彼此不同，这种迹就叫做路，起点与终点闭合的路又叫做圈、这些都是一些特殊的边导出子图，如图三中的G，假设取v l av2cv3dv2f v5gv3就是—条迹，而v l av2f v5gv3就是—条路，假设取v l av2f v5gv3bv l就得到一个圈、一条迹可以删去一段而成为路、图3一个图中的任意两点都存在一条连接这两点的路，那么称这个图是连通的、对于一个不连通的图，我们可以把它分成假设干个连通的分支、有了这些概念以后，我们就来看看上面的一笔画问题、为了表达方便起见，我们把包含图中所有的边的迹叫做欧拉迹，首尾闭合的欧拉迹叫做欧拉途、如果一个图含有一个欧拉途就说明从任一顶点山发，可以经过每一条边恰好一次并且回到出发点，换言之，它可以一笔画成、这种含有欧拉途的图就叫做欧拉图、不难证明下面两个定理：定理二 一个连通图是欧拉图的充分必要条件是它不含奇数度顶点、定理三 一个连通图含有欧拉迹的充分必要条件是最多有两个奇数度顶点、 由这两个定理可知，一个图可以一笔画成的充分必要条件是，或者不含奇数度顶，或者恰含有两个奇数度顶点、即使复杂的图，也不消一分钟就可以看出它是否能够一笔画成、在我们上面提到的七桥问题中，相应的图的四个顶点皆是奇数度的，所以无法—笔画成，即使不要求回到原出发点，也无法—笔画成、 一笔画问题只是图论中一个很小的侧面、事实上，我们在画出—个图的时候，可以赋予图中的顶点和边以各种不同的含义，从而也就可以用来研究五花八门的问题、下面举几个简单的例子、例— 在世界各国中，必能找到这样两个国家，它们与同样数目的国家有外交关系、我们用顶点表示国家，两国间有外交关系的就用边相连，这样一来就只须证明在任意—个这种图中必有两个顶点有相同的度数，事实上，设诸顶点以v l ，v 2，……v n 表示，假设各顶点的度数皆不相同，那么它们分别是0，1，2，…，(n -1)这n 个数、但这是不可能的，因为既然有0度的顶点就不可能再有n -1度的顶点，故必有两个顶点具有相同的度数、可见与之相应的两国与同样数目的国家有外交关系、例二 平面上有n 个点，其任意两点之间的距离不小于1，试证至多存在3n 对点，其距离恰是l 、以v l ，v 2，…，v n 表示平面上这n 个点，我们规定某两点v i 与v j 的距离恰是1时才用边相连，在如此所得到的图中，边的数日就是距离恰是1的顶点的对数、与任一顶点v 相邻的顶点必在以v 为圆心，1为半径的圆周上，但题设这些点之间的距离又不小于1，所以至多只能有六个顶点与v 相邻，换言之，对于任意1≤i ≤n 皆d 〔v i 〕≤6，于是，1()6ni i d v n =≤∑由定理一，左边就是图中边数的二倍，所以边数≤3n ，即至多有3n 对点距离恰是1、例三 在随意凑集的六个人中，一定能找列三个人，他们或者彼此认识，或者彼此不认识、这是一个Ramsey 问题，曾经是著名的难解问题之一，现在用图论方法很齐易解决、我们用六个点表示六个人，两个人认识就将扪应的两点用线连起来、于是这个问题就转化成下述形式：在任何一个六个顶点的图中，必有三个顶点存在，它们或者连成—个三角形，或者彼此不相邻、设v 是某一顶点，那么其余五个顶点中与v 相邻的顶点数和与v 不相邻的顶点数中必有一个是超过3的、不妨设u 1，u 2，u 3，是与v 相邻的，假设u l ，u 2，u 3中有某两点是相邻的，那么它们与v 将构成——个三角形，假设u 1，u 2，u 3中任意两点都不相邻，那么它们就是题中所要求的三点、下面我们再来看看图论中所研究的其它—些问题、邮路：利用欧拉途的概念可以解决所谓邮递路线问题、我们知道，邮递员总想从邮局出发以最短的路程走遍每一条街道，最后回到邮局，如果这位邮递员所负责的街道可以画成一个欧拉图，那么只须求出其欧拉途就一定是最理想的邮路了、而对于欧拉图要求出其中的欧拉途是不成问题的、但当街道画出一个非欧拉图时，情形就比较复杂了、这时须引入“重量”的概念而转化成求欧拉途的问题、当合理地规定图中的每一条边的重量以后，我们就得到一个所谓“赋重图”、这里的重量可以表示路程的长短，也可以表示运费的多少，也可以表示造价的高低，如此等等，于是有许多实际问题便可转化成求赋重图中的最轻通路问题、图论中已经建立了一些有效的方法、可靠性：要建立一个交通或通讯系统，就要设法使假设干个点之间皆有通路相连，并且还力求使总的造价是比较少的、这一类问题在图论中已通过对一种特殊的子图——“树”的研究得以解决、另一方面，如果在—种交通或通讯系统中任意两点之间都只有一条路相通，那么这种系统是很不可靠的，一旦有一处发生故障，就可能仗整个系统陷于瘫痪，于是图论中又进一步研究了连通的可靠性问题，这主要是将连通程度数量化、货郎担问题：我们把包含图中每一个顶点的路叫做哈密顿路，假设是闭的就叫做哈密顿圈，相应的图就叫做哈密顿图、与欧拉途不同的是哈密顿圈只要求走遍每一个顶点，并不要走遍每条边，著名的货郎担问题与此有关、这个问题是：寻找一条最短路线，使一个货郎不走回头路而走遍几个村镇，这是一个看起来简单却尚未得到解决的问题，没有一个有效方法可以用来判断一个图是否为哈密顿图、印刷电路：当我们设计一种印刷电路时，必须要求有关的电路图是一个平面图，由于我们在画出一个图的时候，其边的长短以及准确位置是无关紧要的，只是关心某条边是连接哪两个顶点而已、所以—个图是否为一个平面图并不是一眼就能看出来的、某些图乍看起来不是平面的，但可以重新画出使成平面图、这在图论中叫做平面嵌入，并且已经找到一些有效方法可以判断任意给出的图是否为平面图，以及如果是平面图怎样进行平面嵌入、四色问题：我们可以把图的顶点或边涂以各种颜色，并研究任意一个图最少要几种颜色)才能合理地进行上色(即使得相邻的顶点或边颜色不同)、著名的四色问题与此有关，四色问题是一种猜想：任一平面图只须四种颜色即可将顶点染色，使每每两相邻顶点皆有不同颜色、这与地图的染色是密切相关的、在图论中图论是一门比较新的学科，它当然可以尽量采取近代数学的概念及方法，诸如集合、映射、矩阵等等来处理其内容，还可以建立图与图之间的一些运算关系、用它可以解决的问题无法估量、图论的内容是丰富的，方法是新颖的，上面罗列的仅是其【一】二而已、。

2．凡是只有两个奇点的连通图（其余都为 偶点），一定可以一笔画成。画时必须把一 个奇点为起点，另一个奇点终点。例如下图 的线路是：①→②→③→①→④
下列图形中那几个可以一笔画出来？
（1）、（2）、（4）可以一笔画出；（3）、（5）不能一笔画 出
例1 下列哪几个图能一笔画出？如果能，给出画法。
哥尼斯堡是位于普累格河上的一座城市，它 包含两个岛屿及连接它们的七座桥．该河流 经城区的这两个岛．岛与河岸之间架有六座 桥，另一座桥则连接着两个岛．星期天散步 已成为当地居民的一种习惯，但试图走过这 样的七座桥，而且每桥只走过一次却从来没 有成功过．但直至引起瑞士数学家欧拉 (Leonhard Euler，1707—1783)注意之前， 没有人能够解决这个问题 ．
例3：再回到“七桥问题”，问：在 何处架设一座桥，可使游人一次走 遍所有各桥？
例4：某花园小径如图，问：你能否 从图中点1出发不重复地走过所有小 径？如果能，请标出所经过各点的 顺序；如果不能，请标出必须重复 走的小径。
练习：下面各图，能否一笔画出？ 若能，请画出走法；若不能，请说 明理由。
留一道作业：下面的五环标志可否一笔 画成？如何画？
能否一笔画是由图的奇、偶点的数目来决定的。那么什么 叫奇、偶点呢？与奇数（单数）条边相连的点叫做奇点； 与偶数（双数）条边相连的点叫做偶点。如下图中的①、 ④为奇点，②、③为偶点。
1．凡是由偶点组成的连通图，一定可ห้องสมุดไป่ตู้一笔画成。画时 可以把任一偶点为起点，最后一定能以这个点为终点画完 此图。例如下图都是偶点，画的线路可以是：①→③→⑤ →⑦→②→④→⑥→⑦→①
一笔画------七桥问题
一笔画----------七桥问题
请你做下面的游戏：一笔画出图中 的 图形来。 规则：笔不离开纸面，每根 线都只能画一次。这就是古老的民间 游戏——一笔画。 你能画出来吗？

专题7 一笔画问题[读一读]不走“冤枉”路出门旅游，面对众多的，分散的景点时，总想尽量走最少的路看最多的景，为了不让重复的冤枉路弄得疲惫不堪，就必须找到一条联接各景点而又不重复的路径，一次走下去，不再回来。

数学中，一笔画的游戏能让他你得心应手地解决这个问题，一笔画，就是从图形上某点出发，笔不离开纸，而且每条线都只画一次不重复。

任何图形都是由点和线组成的，图形中的点分为两大类：（1）从一点出发的线的条数是双数，这点称为双数点。

（2）从一点出发的线的条数是单数，这点称为单数点。

一个图形能否一笔画成，关键在于图中的单数点的多少。

图形中没有单数点的，一定可以一笔画成；图形中只有两个单数点的，也一定可以一笔画成；其他情况的图形，都不能一笔画成。

单数点在一笔画中只能作为起点或终点。

这可看成“一笔画”规则。

[想一想][例1]从图中给出的小黑点出发，不重复不遗漏，一笔描出这些图形，你能做到么？为什么？[剖析]先找到图中的黑点，再数清从这点出发的线有几条，再依据“一笔画规则”确定能不能一笔描出这些图形。

[解]观察图1中有3个双数点，图2中有5个双数点，图3中有2个单数点，其余是双数点，所以3幅图都可以一笔画成。

关键在于找准每个图形单数点的个数。

1、从图中小黑点出发，看能否一笔画成下列图形。

2、只用一笔描出下面的图，用箭头表示画的方向。

[解]1、可以一笔画成。

2、可以一笔画成。

[例2]看看下列图形能否一笔画成？并说说原因。

[剖析]观察图1中有2个双数点，图2中有6个双数点，都可以一笔画成。

图3中有5个双数点和4个单数点，所以不能一笔画成。

[解][练一练]1、下面的图形能一笔画出吗？为什么？①③2、下面的图形能一笔画出吗？说明理由。

[解] 1、①②因为图①和图②只有两个单数点，图③没有单数点，所以它们都可以一笔画。

2、因为图①有16个双数点，图②有8个双数点，所以这两个图形都能一笔画。

点拨：由多个图形重叠组成的新图形，数点时注意要别忘了数重叠产生的交点。

一笔画问题
1.瑞士大数学家欧拉在七桥问题的过程中，发现了一笔画原理，这一原理被命名为“欧拉定理”：
（1）能一笔画的图形必须是连通的。

（2）凡是只由偶顶点组成的连通图形，一定可以一笔画出，画时可以由任一偶顶点为起点，最后仍回到这点。

(3)凡是只有两个奇顶点的连通图形一定可以一笔画出，画时必须以一个奇顶点为起点，以另一个奇顶点为终点。

（4）奇顶点个数超过两个的图形不能一笔画出。

2.能一笔画出的图形的奇顶点数目是2或0，如果图形有奇顶点2N（n为正整数）个，那么图形最少要用N笔画出。