一笔画问题
数学定理
传统意义上的几何学是研究图形的形状大小等性质,而存在一些几何问题,它们所研究的对象与图形的形状和线段的长短没关系,而只和线段的数目和它们之间的连接关系有关,比如一笔画问题就是如此。即平面上由曲线段构成的一个图形能不能一笔画成,使得在每条线段上都不重复。例如汉字“日”和“中”字都可一笔画,而“田”和“目”则不能。两两相连区域可一笔画,例如,平面4个区域两两相连区域可一笔划;轮胎状上7个两两相连区域可一笔画;我们可以构造一个多维空间的无穷个两两相连区域一笔划。
定义
也就是“一笔画”。一笔画图形的必要条件是:奇点数目是0或者2。概述图⑴的“七桥问题”A,B,C,D都是奇节点,数目是4,所以不能够“一笔画”。 我们把节点转换回来,成为“节面”(区域),来考虑“一笔画”。
例子
在平面中,4个或者4个以下的区域可以构成两两相连的区域,可以一笔画。概述图⑵。每个区域必须是单连通的,就是一个区域不能够是分成2块或者2块以上。概述图⑶就不是单连通的。这是著名的四色猜想。大家知道,平面上不可能有两两相通的5个区域。紧致封闭平面,在一个轮胎状的表面,7个或者7个以下的区域可以构成两两相连的区域。可以“一笔划”。把图(A)上下对折以后,再左右对折,形成一个轮胎状,7个区域两两相连。
两两相连的区域可以不经过其它区域到达任何一个区域。P。J希伍德以毕生精力研究四色定理,并且证明了5色定理,稀伍德考察了一般曲面着色问题提出一个推测:在有P>1个洞的封闭曲面上,足以为任何地图着色的最小数等于(左图上下对折再左右对折就是一个轮胎,7个区域两两相连,可以一笔画)。
一笔画的规律
数学家欧拉找到一笔画的规律是:
⒈凡是由偶点组成的连通图,一定可以一笔画成。画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。
⒉凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。画时必须把一个奇点为起点,另一个奇点终点。
⒊其他情况的图都不能一笔画出。(有偶数个奇点除以二可以算出此图至少需几笔画成。)
比如附图:(a)为⑴情况,因此可以一笔画成;(b)(c)(d)则没有符合以上两种情况,所以不能一笔画成。
相关名词含义
◎顶点与指数:设一个平面图形是由有限个点及有限条弧组成的,这些点称为图形的顶点,从任一顶点引出的该图形的弧的条数,称为这个顶点的指数
◎奇顶点:指数为奇数的顶点。
◎偶顶点:指数为偶数的顶点
欧拉图
先定义能一笔画出并回到起点的图为欧拉图,连通就是说任意两个节点之间可以找到一条连接它们的线。这个要求看来很重要,直观方法中与这一点对应的是说原图本身不能是分成多个的。
设G为一欧拉图,那么G显然是连通的。另一方面,由于G本身为一闭路径,它每经过一个顶点一次,便给这一顶点增加度数2,因而各顶点的度均为该路径经历此顶点的次数的两倍,从而均为偶数。反之,设G连通,且每个顶点的度均为偶数,欲证G为一欧拉图。为此,对G的边数归纳。当m = 1时,G必定为单结点的环,显然这时G为欧拉图。设边数少于m的连通图,在顶点度均为偶数时必为欧拉图,现考虑有m条边的图G。设想从G的任一点出发,沿着边构画,使笔不离开
图且不在构画过的边上重新构画。由于每个顶点都是偶数度,笔在进入一个结点后总能离开那个结点,除非笔回到了起点。在笔回到起点时,它构画出一条闭路径,记为H。从图G中删去H的所有边,所得图记为G’,G’未必连通,但其各顶点的度数仍均为偶数.考虑G的各连通分支,由于它们都连通,顶点度数均为偶数,而边数均小于m,因此据归纳假设,它们都是欧拉图。此外,由于G连通,它们都与H共有一个或若干个公共顶点,因此,它们与H一起构成一个闭路径。这就是说,G是一个欧拉图。
一笔画定理
1736年,欧拉证实:七桥问题的走法根本不存在。同时,他发表了“一笔画定理”:一个图形要能一笔画完成必须符合两个条件:
欧拉的研究开创了数学上的新分支――图形与几何拓扑。
参考资料
最新修订时间:2024-04-03 16:04
目录
概述
定义
例子
参考资料