一笔画问题是图论中一个著名的问题
- 格式:doc
- 大小:26.50 KB
- 文档页数:2
一笔画的由来可以追溯到1736年,当时大数学家欧拉研究解决了一笔画问题。
欧拉通过分析图中的偶数点和奇数点,以及线的连接方式,找出了能够一笔画出的图形规律。
一笔画的基本规律包括以下几点:
1. 欧拉回路:一个图形中,任意两个点之间都有且仅有一条路径,则该图形被称为欧拉回路。
一笔画问题就是要找到一个欧拉回路,使得该回路的起点和终点重合。
2. 奇偶性:对于任意一个图形,其顶点可以分为奇数顶点和偶数顶点两类。
如果一个图形有偶数个顶点,则该图形可以一笔画出;如果一个图形有奇数个顶点,则该图形需要两笔画出。
3. 欧拉函数:欧拉函数是指将一个图形分解为若干个不相交的子图,使得每个子图都是一笔画出的图形,且每个子图的顶点个数不超过4个。
欧拉函数可以帮助我们判断一个图形是否可以一笔画出。
在实际应用中,一笔画问题可以应用于很多领域,如地图着色、电路设计、物流规划等。
同时,一笔画问题也是图论中的一个重要研究方向,对于理解图的结构和性质具有重要的意义。
浅谈一笔画问题公司内部档案编码:[OPPTR-OPPT28-OPPTL98-OPPNN08]浅谈一笔画问题摘要:一笔画问题是一个几何问题,传统意义上的几何学是研究图形的形状大小等性质,而存在一些几何问题,它们所研究的对象与图形的形状和线段的长短没关系,而只和线段的数目和它们之间的连接关系有关,比如一笔画问题就是如此。
一笔画问题是一个简单的数学游戏,即平面上由曲线段构成的一个图形能不能一笔画成,使得在每条线段上都不重复例如汉字‘日’和‘中’字都可以一笔画的,而‘田’和‘目’则不能。
关键词:一笔画规律原理早在18世纪,瑞士的着名数学家欧拉就找到了一笔画的规律。
欧拉认为,能一笔画的图形必须是连通图。
连通图就是指一个图形各部分总是有边相连的.但是,不是所有的连通图都可以一笔画的。
能否一笔画是由图的奇、偶点的数目来决定的。
一笔画问题是图论中一个着名的问题。
一笔画问题起源于柯尼斯堡七桥问题。
数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题。
一般认为,欧拉的研究是图论的开端。
与一笔画问题相对应的一个图论问题是哈密顿问题。
一、一笔画规律数学家欧拉找到一笔画的规律是:(一)凡是由偶点组成的连通图,一定可以一笔画成。
画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。
(二)凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。
画时必须把一个奇点为起,,另一个奇点终点。
(三)其他情况的图都不能一笔画出。
(有偶数个奇点除以二便可算出此图需几笔画成)比如附图:(a)为(1)情况,因此可以一笔画成;(b)(c)(d)则没有符合以上两种情况,所以不能一笔画成。
补充:相关名词的含义◎顶点与指数:设一个平面图形是由有限个点及有限条弧组成的,这些点称为图形的顶点,从任一顶点引出的该图形的弧的条数,称为这个顶点的指数。
◎奇顶点:指数为奇数的顶点。
◎偶顶点:指数为偶数的顶点。
一笔画问题是图论中一个著名的问题。
一笔画问题起源于柯尼斯堡七桥问题。
数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题[1]。
一般认为,欧拉的研究是图论的开端。
与一笔画问题相对应的一个图论问题是哈密顿问题。
目录[隐藏]1 问题的提出2 一笔画定理2.1 定理一2.2 定理二3 例子3.1 七桥问题3.2 一个可以一笔画的例子4 一笔画问题与哈密顿问题5 参见6 参考来源[编辑] 问题的提出一笔画问题是柯尼斯堡问题经抽象化后的推广,是图遍历问题的一种。
在柯尼斯堡问题中,如果将桥所连接的地区视为点,将每座桥视为一条边,那么问题将变成:对于一个有着四个顶点和七条边的连通图G(S,E),能否找到一个恰好包含了所有的边,并且没有重复的路径。
欧拉将这个问题推广为:对于一个给定的连通图,怎样判断是否存在着一个恰好包含了所有的边,并且没有重复的路径?这就是一笔画问题。
用图论的术语来说,就是判断这个图是否是一个能够遍历完所有的边而没有重复。
这样的图现称为欧拉图。
这时遍历的路径称作欧拉路径(一个圈或者一条链),如果路径闭合(一个圈),则称为欧拉回路[1]。
一笔画问题的推广是多笔画问题,即对于不能一笔画的图,探讨最少能用多少笔来画成。
[编辑] 一笔画定理对于一笔画问题,有两个判断的准则,它们都由欧拉提出并证明[1]。
[编辑] 定理一有限图G 是链或圈的充要条件是:G为连通图,且其中奇顶点的数目等于0或者2。
有限连通图G 是圈当且仅当它没有奇顶点[2]。
证明[2][3]:必要性:如果一个图能一笔画成,那么对每一个顶点,要么路径中“进入”这个点的边数等于“离开”这个点的边数:这时点的度为偶数。
要么两者相差一:这时这个点必然是起点或终点之一。
注意到有起点就必然有终点,因此奇顶点的数目要么是0,要么是2。
充分性:如果图中没有奇顶点,那么随便选一个点出发,连一个圈C1。
浅谈一笔画问题摘要:一笔画问题是一个几何问题,传统意义上的几何学是研究图形的形状大小等性质,而存在一些几何问题,它们所研究的对象与图形的形状和线段的长短没关系,而只和线段的数目和它们之间的连接关系有关,比如一笔画问题就是如此。
一笔画问题是一个简单的数学游戏,即平面上由曲线段构成的一个图形能不能一笔画成,使得在每条线段上都不重复?例如汉字‘日’和‘中’字都可以一笔画的,而‘田’和‘目’则不能。
关键词:一笔画规律原理早在18世纪,瑞士的著名数学家欧拉就找到了一笔画的规律。
欧拉认为,能一笔画的图形必须是连通图。
连通图就是指一个图形各部分总是有边相连的.但是,不是所有的连通图都可以一笔画的。
能否一笔画是由图的奇、偶点的数目来决定的。
一笔画问题是图论中一个著名的问题。
一笔画问题起源于柯尼斯堡七桥问题。
数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题。
一般认为,欧拉的研究是图论的开端。
与一笔画问题相对应的一个图论问题是哈密顿问题。
一、一笔画规律数学家欧拉找到一笔画的规律是:(一)凡是由偶点组成的连通图,一定可以一笔画成。
画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。
(二)凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。
画时必须把一个奇点为起,,另一个奇点终点。
(三)其他情况的图都不能一笔画出。
(有偶数个奇点除以二便可算出此图需几笔画成)比如附图:(a)为(1)情况,因此可以一笔画成;(b)(c)(d)则没有符合以上两种情况,所以不能一笔画成。
补充:相关名词的含义◎顶点与指数:设一个平面图形是由有限个点及有限条弧组成的,这些点称为图形的顶点,从任一顶点引出的该图形的弧的条数,称为这个顶点的指数。
◎奇顶点:指数为奇数的顶点。
◎偶顶点:指数为偶数的顶点。
二、一笔画原理(一)一笔画必须是连通的(图形的各部分之间连接在一起);(二)没有奇点的连通图形是一笔画,画时可以以任一偶点为起点,最后仍回到这点;(三)只有两个奇点的连通图形是一笔画,画时必须以一个奇点为起点,以另一个奇点为终点;(四)奇点个数超过两个的图形不是一笔画利用一笔画原理,七桥问题很容易解决。
一笔画问题2014-7-15一笔画问题简单学习总结今天学的还是图论的内容——一笔画问题。
一笔画就是把一个无向图(或有向图)所有的边都遍历一遍且不重复走同样的边。
这个新知识的算法都是建立在几个数学性质上面的,分别如下:1、这个有向图(或无向图)必须是连通的。
这是最基本的条件。
2、每个点之间度的要求:无向图:满足①所有点的度数为偶数或者②有两个点度数为奇数,其他点度数为偶数,且这两个奇数点必须为一笔画中的开端和结尾。
有向图:满足①所有点出入度相等或者②有一个点出度比入度大1,另一个点入度比出度大1,其他点的出入度相等,且出度大的点为一笔画开端,入度大的点为一笔画结尾。
数学简单证明还是比较容易的,如果一个点度数为奇数,那么从该点出发,去到的无非就两种情况:偶点或奇点,偶点我们总可以绕一个圈回到该偶点重新出发。
奇点就到达终点了。
(圈套圈的思路)对于无向边,有一个特殊处理:无向边路过一条边后,要把它的反向边去掉。
这个过程可以用指针实现,用一个指针指向它的反向边。
或者,如果用数组来储存边时,因为反向边是同时申请的,所以它们的下标一定是相邻的,可以用异或操作得到。
下面介绍几种算法:1、圈套圈算法算法思想:每次在某个点随便找一条边,一直走,如果找到环,那么就相应地插入到一笔画的顺序中,环中若有嵌套环,那么同样地找下去。
算法实现:可以用链表实现插入之类的操作,但若用深搜回溯写的话,程序会非常简单。
就是从奇点(或任意点)出发,任意地深度遍历,如果当前点已经不能往下搜,那么就回溯看祖先节点是否有其他可以遍历的点,按回溯的顺序弹出的边,在无向图里面正反顺序都是一笔画正确解法,有向图里需要取反顺序。
算法优化:由于系统栈的空间局限性,在朴素的递归算法里面不能支持较大数据范围的题目,可以改成用stack栈模拟递归的操作,这样就不再会爆栈。
2、弗罗莱算法算法思想:首先在奇点出发,尽量先不走桥(若去掉该边图不连通,则该边为桥),先走环路。
一笔画问题知识要点:所谓图的一笔画,指的就是:从图的一点出发,笔不离纸,遍历每条边恰好一次,即每条边都只画一次,不准重复.从图中容易看出:能一笔画出的图首先必须是连通图.但是否所有的连通图都可以一笔画出呢?下面,我们就来探求解决这个问题的方法.什么样的图形能一笔画成呢?这就是一笔画问题,它是一种有名的数学游戏.我们把一个图形中与偶数条线相连接的点叫做偶点.相应的把与奇数条线相连接的点叫做奇点.笔画问题:(1)能一笔画出的图形必须是连通的图形;(2)凡是只由偶点组成的连通图形.一定可以一笔画出.画时可以由任一偶点作为起点.最后仍回到这点;(3)凡是只有两个奇点的连通图形一定可以一笔画出.画时必须以一个奇点作为起点,以另一个奇点为终点;(4)奇点个数超过两个的图形,一定不能一笔画.例1:我们把一个图形上与偶数条线相连的点叫做偶点,与奇数条线相连的点叫做奇点.下图中,哪些点是偶点?哪些点是奇点?奇点:E J G D例2:一条小虫沿长6分米,宽4分米,高5分米的长方体的棱爬行.如果它只能进不能退,并且同一条棱不能爬两次,那么它最多能爬多少分米?解析:8个定点都是奇点,所以至少需要4笔.多画长和高能保证总路程最长,为A-B-G-H-A-D-C-F-E-D总长为6×4+5×4 +4×1=48分米.知识点巩固:1. 判断下面的图形能不能一笔画?为什么?A B C D2. 下面的图形都是不能一笔画成的,你能不能去掉一条线,使他们变成一笔画?3. 下面是一座公园的道路设计图,问能不能一次不重复的把所有小路都走遍?要从哪里开始?4、小明要把四个三角形和一个正方形一次性从纸上剪下来,他能做到吗?5、平安小镇上有两个邮递员,甲邮递员喜欢从A 点出发开始送信,乙邮递员喜欢从B点出发开始送信,他们俩都选择最优路线,谁能更快的跑遍多有的街道呢?6. 幸福乡有四个村庄,幸福河从村庄间流过,村民们在河上一共建了5座桥,问来到幸福乡的人能不能一次不重复地走遍所有的桥。
欧拉回路性质与应用探究湖南师大附中 仇荣琦【摘要】欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。
本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。
然后通过几个实例,介绍了与欧拉回路相关的几类典型问题。
最后对欧拉回路的模型进行了总结,指出其特点和具备的优势。
【关键词】欧拉回路 欧拉路径【正文】一 引言欧拉回路问题是图论中最古老的问题之一。
它诞生于十八世纪的欧洲古城哥尼斯堡。
普瑞格尔河流经这座城市,人们在两岸以及河中间的两个小岛之间建了七座桥(如图1)。
市民们喜欢在这里散步,于是产生了这样一个问题:是否可以找到一种方案,使得人们从自己家里出发,不重复地走遍每一座桥,然后回到家中?这个问题如果用数学语言来描述,就是在图2中找出一条回路,使得它不重复地经过每一条边。
这便是著名的“哥尼斯堡七桥问题”。
无数热衷于此的人试图解决这个问题,但均以失败告终。
问题传到了欧拉(Leonhard图2图1Euler, 1707-1783)那里,立即引起了这位大数学家的重视。
经过悉心研究,欧拉终于在1736年发表了论文《哥尼斯堡的七座桥》,不但成功地证明了“七桥问题”无解,而且找到了对于一般图是否存在这类回路的充要条件。
后人为了纪念欧拉这位伟大的数学家,便将这类回路称为欧拉回路。
欧拉回路问题在信息学竞赛中有着广泛的应用,近年来在各类比赛中出现了许多与之相关的试题。
本文将介绍欧拉回路的相关理论知识,并通过几道例题分析欧拉回路的实际应用。
二 相关知识首先介绍相关概念和定理。
设),(E V G =是一个图。
欧拉回路 图G 中经过每条边一次并且仅一次的回路称作欧拉回路。
欧拉路径 图G 中经过每条边一次并且仅一次的路径称作欧拉路径。
欧拉图 存在欧拉回路的图称为欧拉图。
半欧拉图 存在欧拉路径但不存在欧拉回路的图称为半欧拉图。
在以下讨论中,假设图G 不存在孤立点1;否则,先将所有孤立点从图中删除。
显然,这样做并不会影响图G 中欧拉回路的存在性。
一笔画问题是图论中一个著名的问题。
一笔画问题起源于柯尼斯堡七桥问题。
数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题[1]。
一般认为,欧拉的研究是图论的开端。
与一笔画问题相对应的一个图论问题是哈密顿问题。
目录[隐藏]
1 问题的提出
2 一笔画定理
2.1 定理一
2.2 定理二
3 例子
3.1 七桥问题
3.2 一个可以一笔画的例子
4 一笔画问题与哈密顿问题
5 参见
6 参考来源
[编辑] 问题的提出
一笔画问题是柯尼斯堡问题经抽象化后的推广,是图遍历问题的一种。
在柯尼斯堡问题中,如果将桥所连接的地区视为点,将每座桥视为一条边,那么问题将变成:对于一个有着四个顶点和七条边的连通图G(S,E),能否找到一个恰好包含了所有的边,并且没有重复的路径。
欧拉将这个问题推广为:对于一个给定的连通图,怎样判断是否存在着一个恰好包含了所有的边,并且没有重复的路径?这就是一笔画问题。
用图论的术语来说,就是判断这个图是否是一个能够遍历完所有的边而没有重复。
这样的图现称为欧拉图。
这时遍历的路径称作欧拉路径(一个圈或者一条链),如果路径闭合(一个圈),则称为欧拉回路[1]。
一笔画问题的推广是多笔画问题,即对于不能一笔画的图,探讨最少能用多少笔来画成。
[编辑] 一笔画定理
对于一笔画问题,有两个判断的准则,它们都由欧拉提出并证明[1]。
[编辑] 定理一
有限图G是链或圈的充要条件是:G为连通图,且其中奇顶点的数目等于0或者2。
有限连通图G是圈当且仅当它没有奇顶点[2]。
证明[2][3]:
必要性:如果一个图能一笔画成,那么对每一个顶点,要么路径中“进入”这个点的边数等于“离开”这个点的边数:这时点的度为偶数。
要么两者相差一:这时这个点必然是起点或终点之一。
注意到有起点就必然有终点,因此奇顶点的数目要么是0,要么是2。
充分性:
如果图中没有奇顶点,那么随便选一个点出发,连一个圈C1。
如果这个圈就是原图,那么
结束。
如果不是,那么由于原图是连通的,C1 和原图的其它部分必然有公共顶点s1。
从这一点出发,在原图的剩余部分中重复上述步骤。
由于原图是有限图,经过若干步后,全图被分为一些圈。
由于两个相连的圈就是一个圈,原来的图也就是一个圈了。
如果图中有两个奇顶点u 和v,那么加多一条边将它们连上后得到一个无奇顶点的有限连通图。
由上知这个图是一个圈,因此去掉新加的边后成为一条链,起点和终点是u 和v。
[编辑] 定理二
如果有限连通图G有2k 个奇顶点,那么它可以用k 笔画成,并且至少要用k 笔画成[2]。
证明[2][3]:将这2k 个奇顶点分成k 对后分别连起,则得到一个无奇顶点的有限连通图。
由上知这个图是一个圈,因此去掉新加的边后至多成为k 条链,因此必然可以用k 笔画成。
但是假设全图可以分为q 条链,则由定理一知,每条链中只有两个奇顶点,于是。
因此必定要k 笔画成。
[编辑] 例子
图一:无法一笔画
图二:尽管按照中文书写习惯“串”字不止一笔,但它可以一笔写成。
[编辑] 七桥问题
右图一是七桥问题抽象化后得到的模型,由四个顶点和七条边组成。
注意到四个顶点全是奇顶点,由定理一可知无法一笔画成。
[编辑] 一个可以一笔画的例子
图二是中文“串”字抽象化后得到的模型。
由于只有最上方和最下方的顶点是奇顶点,由定理一知它可以一笔画成。
[编辑] 一笔画问题与哈密顿问题
一笔画问题讨论的是能否不重复地遍历一个图的所有边,至于其中有否顶点的遍历或重复经过则没有要求。
哈密顿问题讨论的则是顶点的遍历:能否不重复地遍历一个图的所有顶点?[4]哈密顿问题由哈密顿在1856年首次提出,至今尚未完全解决[2]。
[编辑] 参见
柯尼斯堡七桥问题
哈密尔顿问题
树(图论)
中国邮递员问题
[编辑] 参考来源
^ 1.0 1.1 1.2 Janet Heine Barnett, Early Writings on Graph Theory: Euler Circuits and The KÄonigsberg Bridge Problem
^ 2.0 2.1 2.2 2.3 2.4 熊斌,郑仲义,《图论》,第四章,38-46,华东师范大学出版社。
^ 3.0 3.1 详细的证明
^ 欧拉图和哈密顿图。