软件开发的家园,编程爱好者的天地.
&&|&&&&|&&
对一道面试题的总结与扩展思考（关于一笔画问题的数学分析）
来源:cnblogs
时间: 04:20
　　问题的提出
&&&&& 当时面试官给我出的问题是这样的：对于下面这个图形，让我一笔画出，要求每条边必须只走一次，并且画的过程中笔不能离开纸。
&&&&& 面试时我给出的回答是不可能做到，面试结束后我也从数学上证明了这个这个回答。当然有兴趣的朋友可以试着画画看。
&&&&& 这个问题其实就是我们小时候会玩到的一笔画游戏。这类问题看似简单直观，但是仔细研究下来却蕴含了很多东西，而且涉及了图论中一个非常重要的研究课题&&欧拉迹。而且这类问题可以扩展出很多东西，例如任意给一个图可不可以完成一笔画且最后回到起始点？再如到底什么样的图可以一笔画出来？什么样的图一笔画不出来？如果一个图可以一笔画出来，那么应该如何画？有没有对一切可一笔画图形的通用解法？
&&&&& 下面我们将这个问题抽象成一般问题，然后从图论角度寻找上述疑问的答案。
　　图论中的一些概念
&&&&& 因为在下文论述过程中需要用到一些图论的基本概念，为了照顾在这方面不熟悉的朋友，我先将要用到的定义和概念列出来，如果您对图论的基本内容已经了然于胸，可以跳过这一节。另外如不做特殊说明，下文所有的&图&都默认指&无向图&，本文的讨论不涉及&有向图&。
　　简单图&&一个简单图可表示为G=(V, E)，其中V是顶点集合，其中每个元素是图的一个顶点；E是边集合，其中每一个的元素是一个顶点对(a, b)，其中a和b均属于V，这个顶点对表示顶点a和b间有一条边相连。
　　多重图&&简单图不允许同一组顶点对在E中出现两次，即一对顶点间最多只有一条边。如果在简单图的基础上允许任一组顶点对间有任意条边，则简单图变为多重图。
　　一般图&&如果在多重图的基础上允许自关联边，即允许(a, a)这样的顶点对出现在E中，则这种图叫一般图。（我们后续所有讨论的对象都是一般图，如不做特殊说明，下文所有的&图&均指一般图）
　　顶点的度&&一个顶点的度是这个顶点所连接的边的条数。
　　连通图&&如果一个图任意两个顶点之间都存在由边组成的通路，则这种图叫连通图。（我们后续所有讨论的对象都是连通图，如不做特殊说明，下文所有的&图&均指无向一般连通图）
&&&&& 途径&&在一个图G中，{x1, x2}, {x2, x3}, &, {xm-1, xm}叫做G的一个途径，如果x1和xm为同一顶点，则说这个途径是闭的，否则说这个途径是开的。
&&&&& 迹&&如果一个途径中没有重复的边，则这个途径叫做&迹&。
&&&&& 欧拉迹&&如果图G的一个迹包含了G所有的边，则这个迹叫做&欧拉迹&。
　　一笔画问题的抽象
&&&&& 有了上面的定义，我们就可以用数学语言描述一笔画问题了：
&&&&& 所谓一笔画问题，就是给定一个无向一般连通图，这个图存在欧拉迹的充分必要条件是什么？如果存在欧拉迹，如何求欧拉迹？
&&&&& 这个问题很庞大，我们化整为零，分几步去讨论。另外，为了避免枯燥无味，我将不会从绝对严格的数理层面去做推理和证明，而是用一些直观的启发式方法，尽量让每位朋友都能读懂。
　　问题一：图G存在欧拉迹的必要条件是什么？
&&&&& 首先，我们来推导G存在欧拉迹的必要条件。虽然满足必要条件不能充分证明G一定存在欧拉迹，但是不满足必要条件就一定不存在欧拉迹。所以搞清这个问题，可以用来帮助我们判断出显然不能一笔画出的图。
&&&&& 欧拉迹分为开欧拉迹和闭欧拉迹，我们先讨论开欧拉迹的情况。
&&&&& 现已知图G存在开欧拉迹（等价于存在一笔画画法，并且这种画法在完成时不会回到起始顶点），那么可以推导出什么？
&&&&& 现在我们这样想：设{x1, x2}, {x2, x3}, &, {xm-1, xm}是G的一条开欧拉迹，那么{x1, x2, &, xm}是这条欧拉迹所经过的顶点的序列。需要注意，这里除了x1和xm一定不是同一顶点，其它很多顶点可能是相同的。因为欧拉迹只要求每个边出现且仅出现一次，但不限制同一顶点出现几次。例如下图：
&&&&& 其中{a, b}, {b, c}, {c, a}, {a, d}, {d, e}, {e, c}是一个开欧拉迹，顶点序列为{a, b, c, a,d, e, c}。
&&&&& 现在我们这么考虑这个问题，对于某一顶点x，I(x)表示欧拉迹中进入x的次数，即走整个欧拉迹过程中从x以外的顶点进入x顶点的次数，O(x)，表示离开x的次数，即当前在x顶点，然后离开x到其它顶点的次数。
&&&&& 我们顺着开欧拉迹走，对于所有顶点此时I(x)和O(x)均为0，当前笔触在x1处。
&&&&& 当从x1走到x2，O(x1)变为1，而I(x2)变为1。我们可以想象，除起始顶点和终止顶点外，其它顶点当走完这个欧拉迹时，I(x)一定等于O(x)，因为对于这些顶点，一次进入必然对应着一次离开。而起始顶点的不同在于，它多一次离开（第一步），所以I(x1)+1=O(x1)，同理，终止顶点多一次进入（最后一步），I(xm)=O(xm)+1。
&&&&& 我们还体会到这样一个事实：对于任意顶点，每一个进入和每一个离开都消耗此顶点的一个度。因为欧拉迹不允许重复边，所以每一次进入和离开一定是走以前没有走过的边，因此顶点x的度为I(x)+O(x)。这样可以得出结论：如果G存在一个开欧拉迹，那么起始顶点和终止顶点的度数为奇数，而其它顶点的度数为偶数。
对我有帮助
对我没帮助
以下留言只代表网友个人观点，不代表本站观点.您的位置： >
来源：　　作者：张素芬;王琳;
欧拉定理的应用——“一笔画”问题浅析　 “一笔画”,就是指能一笔画出的一个图,也就是说笔不离纸能一次把它画出来,图上的每条边都要画到而又不能重复。一、哪些图是一笔画?什么样的图能一笔画出呢?为了说明这个问题,我们先来看下图:(图1)在上图中,由于图(a)被分成了两部分,所以它是个不连通的图,显然不能一笔画出;图(b)虽然是个连通的图,但是我们经过反复试画后,会发现无论怎样画也无法把它一笔画出来;图(c)也是个连通图,但我们试画后会发现:只有从顶点h或b开始画起,才能把这个图一笔画出,并且终点一定是b或h,也就是说,这个一笔画的起点和终点是固定的,并且不重合。图(d)中,无论从它的哪个顶点开始画起,都能把它一笔画出,并且最终一定会回到开始画的那个点。以上四个图的顶点个数是相同的,但是,为什么有的是一笔画,有的不是一笔画?为什么有的一笔画起点受到限制,而有的一笔画起点就不受限制呢?仔细观察以上四个图,就会发现:一笔画和顶点的个数无关,而是和顶点的度数以及图的连通性有关。这主要应用了图论中的欧拉图知识。二、一笔画的理论基础“一笔画”不仅是个有趣的图画游戏,还是图论研究的重要内容之一。判断一个图是不是一笔画,用图论的语言来说,就是判(本文共计1页)　　　　　　　　　　
相关文章推荐
看看这些杂志对你有没有帮助...
单期定价：19.00元/期全年定价：15.20元/期　共182.40元
　　　　　　今天我们先简单介绍一个数学家，然后再玩几个有意思的游戏。主角是盲人欧拉（Leonhard Euler ），其实前面我们也多次提到过他。他是十八世纪的瑞士数学家、自然科学家。【生平和贡献】他出生于瑞士巴塞尔的一个牧师家庭。注意，下面是猛的：13岁时入读巴塞尔大学（……）15岁大学毕业（……）16岁获得硕士学位（……）&大概算算，16岁时我们在上高中吧？这位大哥已经硕士毕业了。大佬们都是开挂的节奏啊。欧拉是18世纪数学界最杰出的人物之一。他是数学史上最多产的数学家，平均每年写出八百多页的论文，还写了大量的力学、分析学、几何学、变分法等的课本。欧拉对数学的研究如此之广泛，在数学的各个分支中也可经常见到他的名字：初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法，数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式……此外他还涉足建筑、弹道、航海学等领域。他在俄国去世以后，彼得堡科学院为了整理他的著作，足足忙碌了四十七年。而且我觉得，他最牛之处在于，从28岁开始他右眼失明，后来左眼视力又衰退，最后完全失明。虽然生活在黑暗中，但他仍然以惊人的毅力，凭着记忆和心算进行研究，直到逝世，竟达17年之久，在这期间，他还是以惊人的速度产出了生平一半的著作……1783年，刚计算完气球上升定律的欧拉停止了呼吸，享年76岁。他生活、工作过的三个国家：瑞士、俄国、德国，都把他视为自己的数学家，为有他而感到骄傲。法国数学家拉普拉斯（Laplace，天体力学之父）说：“读读欧拉，他是所有人的老师”。19世纪伟大数学家高斯（Gauss，人称数学王子，10岁就发现了从1加到100的简便运算）曾说：&研究欧拉的著作永远是了解数学的最好方法。&&【七桥问题】教科书式的既视感结束，我们在欧拉的诸多贡献中，重点挑一个很好玩的谜题：哥尼斯堡的七桥问题是18世纪著名古典数学问题之一，它是说，在俄罗斯哥尼斯堡的一个公园，有七座桥将河中两个岛及两岸连接起来：请问，是否可能从任一点出发，恰好通过每座桥各一次，再回到起点？欧拉研究并解决了此问题，他把问题归结为一笔画问题，并证明了上述走法是不存在的。【一笔画】一笔画，老外叫做one touch drawing，顾名思义，下笔只能一次，中间笔尖不能离开纸面，同一线段不能重复，就要把整个图案画出来。这个游戏有两大类方向，一类是朝着美工方向发展的，解法很明显，主要厉害在图案的精美上：上图就是典型，大家一眼就能看出，它确实是一笔可以画出来的，只是我们可能画不到这么好看。第二类就是走谜题路线的，图片谈不上艺术美观，但这种图就不太容易一眼看出解法。要澄清的一个重要规则是，一笔画里的线段肯定不能重复画；但是同一个点可以多次经过。比如上图的正确解法之一是左下-&左上-&中-&右下-&右上-&中-&左下-&右下，好几个点都不止经历过一次，但是每条边都确实只过了一次。IOS上也有这种游戏的APP：图上这句英文的意思就是“一笔画万物”。有些图看似并不复杂，却无法一笔画出，比如上面的七桥问题就是无解的，还有更为简单的，“田”字也是无法一笔画出的。奥秘在哪里？【解法】解法其实并不复杂。首先，目标图一定要全部连通。学术名称叫连通图。这个好懂，一幅图中各个部分都没连在一块，怎么可能一笔画出来？所以这个前提是明显的。接下来，我们看图中的每一个节点。除起点和终点外，每个点都应该有“入”和“出”。一入一出，是2；再入再出，是4。总之都连着偶数条线段。所以，如果某一个点连着奇数条线段，它就很讨厌了，因为这时它的出入不平衡。比如一个点连着3条线段，那么一入，一出，再入，然后呢？还有出去的线吗？没有了。有小伙伴说，没事，那就不出了，就让它做终点，行吗？恭喜你，一笔画问题你已经基本解决了——连着奇数条线段的点只能做起点或者终点。总结：1、如果一幅连通图上所有的点都连着偶数条线段，那么它一定可以被一笔画出，而且从任意一点出发都可以做到。2、如果一幅连通图上有两个点连着奇数条线段，剩下的点都连着偶数条线段，那么它也一定可以被一笔画出来。但这时要注意，一定要以连着奇数条线段的其中一点为起点，以另一点为终点。3、如果一幅连通图上连着奇数条线段的点超过两个，这幅图一笔肯定画不出来。进一步说，这样的点的数量/2，可算出此图需几笔画成。现在回头看看七桥问题，ABCD四个点连接的线段数量都是奇数，这幅图一共有4个讨厌的点，当然无法一笔画出。汉字型“田”也是一样，四个角连接线段数都是2，中间点连接线段数为4，这都没问题；但四条边的中点，连接线段数都是3，所以讨厌的点也是4个，它也无法被一笔画出。而且用上面的结论3可知，他俩都至少需要两笔才能画出。再去看看刚刚说的这个APP，现在知道真相的你是不是顿时觉得对这个游戏兴趣缺缺：对每一幅图，去数数每个点连接的线段数，如果没有奇数的点，就随便试；有两个奇数的点，就从一个出发，另一个结束，很快就能试出来。补充一句，上面我们讨论的都是无向图，图里的线段都没有方向；有向图会稍微复杂一些。最后感慨一句，其实人生也是一笔画的游戏：从来没有回头路可走，我们谨而思，慎而行。觉得好玩请转发，也欢迎关注微信公众号“科学可以很好玩”。想了解爱因斯坦和引力波？更多精彩请点击左下角“阅读原文”：科学可以很好玩(gh_fb60b3b2f7d6)　
　文章为作者独立观点，不代表大不六文章网立场
的最新文章
这篇旧文飨新关注的小伙伴~老朋友们也别急，下一篇会很烧脑！说说朋友圈摄影大赛背后的故事中秋佳节话月亮美丽的分子，美丽的化学！说说星座的事情google还是googol，这是个问题。来找出那个异种！是2=1+1，不是1+1=2来看看数学的美！这一刻，我既死且活！说说对撞机的故事尺规作图的难题！来看阿基里斯追乌龟！你真的看懂水浒传了吗？你真的读懂西游记了么？怎样围出更多的地？聪明的你开动脑筋！系统地说说幻方的故事！地图投影小知识砸碎那些“伪悖论”！论制度的重要性这次大家满足了吧！——电脑是人发明的，人当然能控制住它。
——你确定电脑也这么想？来看看这个身残志坚的大佬！我们什么时候绕太阳转得更快？此情可待成追忆，只是当时已惘然。是一本正经开开玩笑的时候了！主动权到底在谁手上？春分秋分，昼夜平分；
横蛋竖蛋，停住鸡蛋！收钻石难命更难，似风无力似花残；
倘若洞悉他人意，亦逍遥兮亦钵满。日，机器人AlphaGo对九段棋手李世石：首战告捷3月9日
大家一起来看这场天昏地暗的第三者插足！January，July，October ：这些都是啥玩意？降准啦，降准啦，降准啦！重要的事情说三遍~
今天，我们就简单聊聊降准的事情！一壶浊酒喜相逢，古今多少事，都付笑谈中我告诉朋友，我电脑开机密码是：NoRLNoU。
他愣了一会，问来由，我作大师状缓缓念道：
不负如来不负卿。DNA和蛋白质的华山论剑：到底谁是真正的大佬？元宵佳节，观灯赏月：
明月几时有，把酒问青天。小碳和小肥的故事回归！我是蛋白质，轮到我出场了！人生岂不也是个一笔画的游戏？每逢佳节胖三斤：抓住让我们发胖的那些“罪魁祸首”本篇是应景地炒冷饭，看过的铁杆粉请无视哈：
相对论就是，如果你坐在女神旁边，你就会觉得时间过得好快——爱因斯坦看到这个图你就笑了，但是你确定你知道你在笑啥么？
注意区分科学概念，是多普勒，不是开普勒。多，很多，非常多。i对π说，你丫能不能讲理一点？
π对i说，你丫能不能实际一点？想知道高大上的罗马数字VIII为毛被屌丝的阿拉伯数字8取代了吗gh_fb60b3b2f7d6跟飞哥一起看看科学里面那些 严肃的，搞笑的，靠谱的，不靠谱的事情！热门文章最新文章gh_fb60b3b2f7d6跟飞哥一起看看科学里面那些 严肃的，搞笑的，靠谱的，不靠谱的事情！