哥尼斯堡七桥问题

图论是数据结构和算法中十分重要的框架，比如单源最短路径，最小生成树，拓扑排序这些都是图论研究中的经典问题， 而图论的开创就绕不开欧拉提交的《哥尼斯堡的七座桥》问题

下面是之前写的关于图的相关文章，相关源码使用C++实现:

关于图 图的构建 深度优先搜索遍历图 广度优先搜索遍历图

DFS寻找两点所有路径 dijkstra算法 Bellman-Ford算法

Bellman-Ford算法优化 Floyd算法 prim算法

kruskal算法 拓扑排序 练习题一:Head Of A Hang

七桥问题

我们将图中的问题再进行一次整理，首先有四个顶点A，B，C，D，他们之间被七条边连接起来， 我们如何在每条边只走一次的情况下，将所有的边走完，并回到回到出发点。数学家欧拉将其抽象为一笔画问题：如何一笔将上图抽象模型画完(最近经常刷到一些视频：某个图形能否一笔画出，其实就是这个道理)，

既然问题提出了，如何去解决呢。

最简单的方法就是穷举法，把每一种可行的方案使用一遍， 即 7! = 5040种。

当时数学家欧拉将问题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示，并得到上图的几何模型，从几何模型中可以会发现:如果我们要想回到原点，并且过每座桥，那么点相连的线必须是偶数，如果是奇数我们必然回不来，如下图，A与B如果只有一座桥， 那么每座桥只走一次，过去就回不来，而两座桥可以有去有回，并且保证每座桥只走一次。

于是乎，欧拉发现了一笔画规律(之后提交《哥尼斯堡七桥》的论文，同时开创了数学新分支---图论)：

1．凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点一笔画完此图。

2．凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。

3．其他情况的图都不能一笔画出。

奇点:与奇数条边相连的点叫做奇点(顶点的度为奇数)

偶点:与偶数条边相连的点叫做偶点(顶点的度为偶数)

于是七桥问题就被顺利的搞定了，由于七桥问题有四个奇点，所以要找到一条经过七座桥，但每座桥只走一次的路线是不可能的。

那么下面的图能否一笔画出吗?