1.4　图与次数

“刚才你说的内容就是一笔画问题中的一个很重要的发现。”

·考虑连接顶点的边的数量

·将“起点和终点”与“途经点”分开考虑

“嗯？”

“假设有一个可以一笔画成的图。我们只看与起点连接的边，忽略其他顶点，那么起点周围应该是这个样子的。”

可一笔画成的图的起点

“什么意思？”

“注意看图中与起点相连的边。假设有 7 条边与这个点相连，由于这个点是起点，所以总有 1 条边是一笔画的起始边，其他边则一定会以‘进入边’和‘离开边’的形式两两成对出现。当前图中的顶点有 3 对这样的边。当然，如果图不同，成对的连接边数亦会不同，也可能出现没有成对边的情形。”

“这样啊……”

“在能一笔画成的图中，起点有 1 条一笔画的起始边，其他边两两成对出现。这表示与起点相连的边有奇数条。也就是说，边数为 1、3、5、7 等。”

“哥哥，你好聪明啊。”

“同样，在一个可以一笔画成的图中，终点周围看起来是这个样子的。”

可一笔画成的图的终点

“连接终点的边也有奇数条。”

“没错。成对出现的边一定有偶数条，最后再加上 1 条进入边，所以与图的终点相连的边有奇数条。”我说，“另外，途经点的周围是这样的。”

可一笔画成的图的途经点

“偶数！”

“是啊。途经点的进入边与离开边必定成对出现，所以连接途经点的边一定有偶数条。顶点有起点、终点、途经点这三种，所以前面说的就是所有可能的情况了。”

“好有趣。”

“前面我们思考的是起点与终点不是同一个顶点的情况。如果起点和终点是同一个顶点，情况又会如何呢？从起点开始一笔画到终点结束。”

“哥哥，我知道答案！如果起点和终点相同，这个顶点所连接的边就有偶数条，因为起始边和最后进入该顶点的边都会连接到这个顶点。”

起点与终点相同的图

“没错，如果起点和终点相同，所有顶点连接的边都有偶数条。正如我们刚才提到的，如果起点和终点不同，连接起点和终点的边就有奇数条，连接其他点的边则有偶数条。我们把目前为止得出的结论整理一下吧。”

·在可一笔画成的图中，当起点与终点相同时：

◦起点：连接边数为偶数

◦终点：连接边数为偶数

◦途经点：连接边数为偶数

·在可一笔画成的图中，当起点与终点不同时：

◦起点：连接边数为奇数

◦终点：连接边数为奇数

◦途经点：连接边数为偶数

“原来如此……”尤里说。

“由此我们可以注意到一个很重要的问题。”

如果一个图可以一笔画成，

那么图中连接边数为奇数的顶点有几个？

“有几个……要么没有——或者说有 0 个——要么有 2 个吧？如果起点和终点相同就有 0 个，如果起点和终点不同就有 2 个。——啊！”

“想到了吧？”

“柯尼斯堡七桥问题中，连接边数为奇数的顶点有 4 个！”

“没错，A 有 3 条连接边，B 有 5 条连接边，C 有 3 条连接边，D 有 3 条连接边，所以连接边数为奇数的顶点有 4 个。”

连接边数为奇数的顶点有 4 个

“有 4 个就不行了。”

“没错。如果一个图可以一笔画成，那么连接边数为奇数的顶点应该有 0 个或 2 个。可是柯尼斯堡七桥的图中有 4 个这样的顶点，所以——”

“没办法一笔画成！”

“是啊。我们绝对没办法一笔画成柯尼斯堡七桥的图。也可以说，柯尼斯堡七桥问题无解。这样就结束证明了。”

解答 1-1（柯尼斯堡七桥问题）

如果柯尼斯堡七桥的图可以一笔画成，那么图中连接边数为奇数的顶点必须有 0 个或 2 个。然而在柯尼斯堡七桥的图中，连接边数为奇数的顶点有 4 个。因此，柯尼斯堡七桥问题无解。

“原来如此！就算不试完所有情况也可以证明。”尤里的眼睛闪闪发光。

“某个顶点的连接边数又称为该顶点的次数。所以，如果改用次数来描述一笔画问题的已知性质，就是下面这样。”

一笔画问题的已知性质

如果一个图可以一笔画成，

那么次数为奇数的顶点会有 0 个或 2 个。

“孩子们，茶泡好了。”妈妈的声音传进我的房间。