【浅谈】一笔画小游戏到底该怎么玩？

• 写在前面：因为能力和记忆有限，为方便以后查阅，特写看上去 “不太正经” 的随笔。随笔有 “三” 随：随便写写；随时看看；随意理解。

还是闲话的继续，正值春运期间，腾讯QQ上也推出了相关红包雨活动，其中有个叫做星运连连的游戏，就和一笔画没什么区别，就是下面这个：

一时兴起随便玩玩，结果一发不可收拾，也就成了写这篇水(sui)笔的主要原因。这里先提一嘴今天的主题——欧拉道路。

1.从“一笔画”的规则说起：

    一笔画要求玩家任选一个点作为起点，每条边只能经过一次（一笔的思想体现在这），但每个点可以不计次数地重复经过。

   这种走法画出来的路线就是所谓的欧拉道路，即在图的数据结构中，通过每条边一次且仅一次的道路。

   这里举一个简单且常见的例子：

  一笔画五角星★，我们把画每一条线条的过程理解为通过这条道路，不难理解欧拉道路的绘制过程。 

  还是赋一张图吧！（序号为划线顺序，方向看箭头）

2.关于一笔画游戏的通解：

1）这里先介绍顶点度数的概念，了解的可自行跳过。

一笔画游戏里的图可以都看作无向图 (即所有边没有通过方向的限定，就是边不带箭头，上图为了演示画图过程才加上的)，每个顶点的度数等于与该顶点有关的边的条数，就是数某个顶点周围延伸出了几条边，该点的度数就为几。

上图 五角星★ 的5个顶点度数都为2，因为每个顶点可以通过 2 条不同的边与除自身外的其他顶点相连。

由于度数英文是degree，顶点 v 的度数可用符号 deg(v) 表示。记图中1号顶点为 v1，则 deg(v1)=2 。

2）这里有一个快速通关的规则：优先找到奇数度数的点并从中随意选一个作为起点，全为偶数度随意选择起点即可。

因此我们只需抱着找奇度点的想法就行，为了熟悉一下顶点度数判断，这里我们多看几个例子(来自星运连连小游戏)，奇度点相应度数已在图上标出。

上述5个例子从任意一个奇度点开始都可以画出欧拉道路（当然画法不唯一）。

3）勉强来一个实操例子吧，不想看可以直接跳至可能情况说明：

起始点度为3

通关后停留时间太短没来得及最后一张。。。

4）可能存在的情况(以  第四个例子——关卡36  进行说明)：

如果按照红色编号顺序连接：

可以发现此时已经 game over了，不难想到第6步应该首先连接左下方或右下方的点。

因为至第5步结束，我们去除走过的边，若我们继续走6号边至最上方顶点，去除该边，此时找不到通往下方其他顶点的道路了，这时可称该边为桥 (起连接两岸的作用，去掉后两岸再无联系，定义中用图不再连通表述，这里为了方便理解)。

解决的方法是最后再走桥，仅此而已。

• 小插曲 

            一笔画中所有图奇数度顶点个数≤2，这样才能保证欧拉道路的存在！不信自己去试试，不会且不做证明。

            奇数度顶点数为2的，都是以奇度点开始奇度点收尾。

            最后一本正经地胡说八道：有进有出为偶度；单进单出只能首尾，故首尾为奇度，共两点。