前言：因为被人发现了我手机的图形密码（然后我换成了16位长密码），所以对一笔画突然感兴趣了起来，毕竟太简单这种试试错就能解锁手机（其实是因为被看到了然后记下来了）。我们知道图论本身源自哥尼斯堡七桥问题（这是一笔画问题的起源，有不知道的读者请自行百度），所以讲一笔画之前我们先来了解一些图论知识。事实上，图论的知识的应用非常广泛,无论是在数学还是在物理，社会学等等其他领域。

本篇文章主要讨论无向图一笔画问题，下一篇文章里面我们会讨论多笔画问题。

点：图上若干个不相同的点，我们称之为顶点(vertex)，简称点。

边：如果图上有两个点 v_{1},v_{2} ，并且他们是由直线（段）或曲线（段）连接的话，我们就称这样的线（段）为v_{1},v_{2}的边。

特别的，如果一条线连接了点 v_{1} 与其本身，我们称之为环。

同时，一个点上引出边的条数我们称之为点的次数，记作： deg\ v 。（degree的缩写）特别的，一个环的次数为2。

如果一个点的次数是0，我们称其为孤立点。

次数为奇数的点我们很自然地称之为奇顶点，反之则是偶顶点。如下图所示，图中有三个偶顶点和两个奇顶点。（因为我懒得画图所以下面很多图都是我从Google上搬来的（光速逃

同构：什么是同构呢？就是两个图的结构是一样的。形象一点，如果我们只移动原来图中某些顶点的位置，而不改变点之间的连线，那么这两个图就是同构的。

用数学语言表述就是：如果两个图 G,G' 的顶点间可以构造这样的一一映射：当且仅当 G 中的顶点 v_{i},v_{j} 间有 k 条边相连时， G' 中的顶点 v_{i}',v_{j}' 间有 k 条边相连，则两图同构。我们将其记为：G\simeq G' 。下面就是一组图同构的例子：

我们常常用 G=(V,E) 来表示一个图，其中 V 代表所有顶点的集合， E 代表所有边的集合。若 |V|,|E| （就是集合中的元素个数）都是有限的，那么我们就说这是一个有限图。如果|V|\ or\ |E|有一个为无限，那么就说这是一个无限图。例如一个图中有无限多个孤立点，却只有有限条边，那么这是一个无限图。

简单图:如果一个图中没有环，并且每两个顶点间至多只有一条边的话，那么我们就说这样的图是一个简单图。

我们来看看一笔画的鼻祖问题：七桥问题：

我们可以把七桥问题化简成右图所示的样子：即是否可以用一笔画完右图中所有的边，且不重复画同一条边。

在解决以上问题的之前，我们还要介绍几个别的概念。

链：形象地说，链就是一系列没有环的边的集合。用数学语描述就是：

在图中，一个由不同边组成的序列 e_{1},e_{2},...,e_{q} ，如果其中 e_{i} 是连接两个顶点 v_{i},v_{i+1} 的边，那么我们就称这个序列为 v_{1} 到 v_{q+1} 的链， q 为该链的长。在简单图里可以记为 (v_{1},v_{2},...,v_{q+1}) 。例如我们选取下图中的一条长度为4的链：(9,8,5,6,7) （这条链中不包括连接7,9的线）。请读者想想，下面这张图中还可以有几条链？如果我们把6,8连上，那么新图中可以有几条链？

如果 v_{1}=v_{q+1} ，也就是说画了一圈回到原点（注意这不是环），那么我们就称其为圈。例如上图中的(8,5,6,7,8) 。

如果我们在简单图中新构造一个链，使得起点为 v_{1} ，终点为 v_{q+1} （这两个点叫这条链的端点）,且在这条链之外我们不添加任何新的边，那么我们可以发现，除了这条链的两个端点，剩下的点都是偶顶点（例如上图中的链（9,8,5,6,7,8），注意我们不能考察链（9,8,5,6,7），因为在这条链之外还有别的边）。这是因为对于每一个点 v_{j}(j\ne 1,q+1) ，有进去的一条边就必然有出去的一条边，同时进出边不能重复以前的边，所以这样计数一定是成双成对的。如果我们把v_{1}, v_{q+1}连起来构成一个圈的话，这两个点也将会是偶顶点。

有了链的概念我们再来解释一下连通的概念。如果对于图中任意两点 v_{i},v_{i}' 都有一条从 v_{i} 到 v_{i}' 的链，那么我们就说图是连通的，否则它就是不连通的。

一个图连不连通与他能不能一笔画成有很大的关系，例如看看下面这个图你就会发现，它显然不能一笔画

通俗一点讲就是，一个图如果是连通的，那么你将会看到一整块图（这个形容词好像有点不好），如果是不连通的话那么你就可以看到几块互相独立的图。

仅由一个顶点构成的图我们也说他是连通的（从连通性角度来看单身和情侣又有什么区别呢（逃），不连通的图 G 总可以分成几个连通的子图，例如我们上面那张图就有两个连通子图。如果这些连通子图间互相没有公共的顶点，那我们就说这些子图为图 G的连通分支。

好了我们现在引入完了这么多东西，这和一笔画有什么关系呢？当然有关系啦我草稿箱里面拖了八篇文章没写完要是跟正文无关我绝对懒得打这么多字（逃（（（（多带括号能带来一种残影的感觉

因为我们可以用图论的语言来改写我们的一笔画问题，i.e.一个图能否被一笔画完（并回到原点），等价于这个图是不是一个链（圈）。

为什么我们能得到这样的等价关系呢？首先我们要确定一点：链和圈都可以被一笔画成。反之，如果要画的对象不是链或圈，那么它肯定不可能被一笔画成。

有了上面的预备知识，我们提出两个非常重要的定理！

Theorem 1:对于任意的图G，奇顶点的个数一定是偶数

先放两张图感受一下：（讲图论没图讲个锤子）

证明：

我们来数一下边的条数，设次数为 i 的顶点有 n_{i} 个，边的总数为 m ，那么我们有： \sum_{i=0}^{k}i\cdot n_{i}=2m (这里涉及到一个算二次的问题，我们称之为握手引理）

那么我们将一部分式子挪到等号右边去，就有 \sum_{2\nmid i,i=1}^{k}i\cdot n_{i}=2m-\sum_{2\mid i,i=0}^{k}i\cdot n_{i}

很显然右边是偶数，所以左边为偶数个奇数相加才为偶数，因此奇顶点的个数一定为偶数. \square

然后我们由之前的探究我们知道一个链至多拥有2个奇顶点，所以能一笔画的一个必要条件就是奇顶点个数为0或者2.那么拥有这个条件就够了吗？当然不是，我们回到上面介绍连通性时的图：

很显然图中只有两个奇顶点，但是这个图显然不能一笔画，所以再次论证了我们之前的结论图的连通性与他能不能一笔画成有很大的关系，那么我们想，如果同时满足着两个条件是否就一定能一笔画呢？

Theorem 2:

有限图 G 是一条链或圈的充要条件是： G 是连通的，且奇顶点的个数为0或2.并且当且仅当奇顶点个数为0是，连通图 G 是一个圈。

证明（这个证明可以选读）：

我们仅须证明充分性，我们对边 m 进行数学归纳法.

设边数小于 m时，结论成立（即G 是连通的，且奇顶点的个数为0或2时G 是一条链或圈）.如果 G 有两个奇顶点 v 与 v' ，从v出发，沿着G得边前进，每条边至多经过一次，那么到任意一个不同于v'的点 v'' ,我们分以下两种情况考虑：

1. v'' \ne v ,那么由于v''是偶顶点，每次到v''用掉奇数条与v''相邻的边，那么当然可以从v''继续往下走

2. v''=v ,由于 v 是奇顶点，而每次到达 v 时用掉偶数条边，所以也可以从v''继续走下去

但考虑到图的边是有限的，不能无限走下去，所以必然存在一条从v 到 v'的链 \mu

将这条链擦掉以后，我们得到了 G 的子图 G' ，其顶点全是偶顶点，因此G'的所有连通分支根据归纳假设，都是圈。

下面回到原来的图，因为他的连通性，所以每个 G' 的连通分支都与 \mu 至少一个公共点，，那么我们设 v_{i} 为 G_{i}' 的公共点，其中 i\leq k ,那么由下图我们可以看出，G是一条从v 到 v'的链，由 v 出发，途经每一个 v_{i} 是沿着 G_{i}' 走一圈，然后再这样走...直到走到 v'

如果 G 没有奇顶点，要想弄出一对奇顶点还是很容易的，只需要去掉连接v 与 v' 的边我们就得到了两个奇顶点 v 与 v'，按照上面的证明我们知道这个新图是一条链，同理对于满足上面论证的一条链，我们把两端点相连即得到了一个圈，此时奇顶点个数为0. \square

Corollary:

如果一个连通图 G 不是一条链，那么与之同构的图也不是一条链。若图 G 是一条链，与之同构的图也是一条链。

这个留给读者自己证明. \square

那么我们回到我们最初的问题，也就是下面这个图能不能一笔画成：

事实上这图有三个奇顶点，所以当然不行，根据定理2可得证。

那么至少要几笔才能画完这个图呢？这个就是我们下一篇文章会讨论的问题了