一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题。一般认为,欧拉的研究是图论的开端。
一笔画问题是柯尼斯堡问题经抽象化后的推广,是图遍历问题的一种。在柯尼斯堡问题中,如果将桥所连接的地区视为点,将每座桥视为一条边,那么问题将变成:对于一个有着四个顶点和七条边的连通图 ,能否找到一个恰好包含了所有的边,并且没有重复的路径。欧拉将这个问题推广为:对于一个给定的连通图,怎样判断是否存在着一个恰好包含了所有的边,并且没有重复的路径?这就是一笔画问题。用图论的术语来说,就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径,如果路径闭合,则称为欧拉回路。一笔画问题的推广是多笔画问题,即对于不能一笔画的图,探讨最少能用多少笔来画成。
对于一笔画问题,有两个判断的准则,它们都由欧拉提出并证明。
定理一
连通的无向图有欧拉路径的充要条件是:无向图奇顶点(连接的边数量为奇数的顶点)的数目等于0或者2。
连通的无向图是欧拉环(存在欧拉回路)的充要条件是:每个顶点的度都是偶数。
定理二
如果连通无向图 有 个奇顶点,那么它可以用 笔画成,并且至少要用 笔画成。
输入一些二元组,二元组代表两个节点之间拥有一条通路,比如(a,b)表示a可以到达b,b也可以到达a。然后给出判断此图是否可以一笔画。
输入示范
3
a,b
a,c
b,c
输出示范
true