举例：扫雪机、街道清洁卡车和邮递员是需要穿过每条街道但又想避免两次穿过同样街道的汽车和人。

图论始于数学家莱昂哈德·欧拉（Leonhard Euler）对这类路径的研究。

欧拉写了一篇关于柯尼斯堡七桥的论文，证明在这座城市中行走，不可能每座桥都恰好经过一次。

点击下面的问题地图，了解更多相关信息。

证明：

计算所有边的所有端数与将所有节点的所有度数相加的数字相同，同意吗？

由于每条边有 2 个端点，因此所有边的端总数必须为偶数。（将偶数相加得到偶数。

要将所有节点的度数相加，可以将偶数相加，得到一个偶数，然后将奇数相加。

如果有奇数个奇数度节点，则该总和将是奇数，然后是偶数 + 奇数 = 奇数，因此总度数将是奇数。但它等于所有边的所有端的总数，这是偶数。因此，奇数次节点的数量不能是奇数， 它必须 是偶数。

例如，1 是奇数，因此没有只有 1 个奇数节点的图像。

如果节点的度数为偶数，即 2、4、6,...边缘连接到节点，然后当到达该节点时，会留下奇数个大于零的未使用边缘，因此可以离开该节点并继续前进。如果度数为奇数，即 1、3、5,..附加边后，要么必须在此节点处开始路径，要么路径将在此节点处结束。因为一条路径只有 2 个端，所以只能有 2 个奇数节点。因此：

要有欧拉循环，图必须只有偶数度节点，要有欧拉路径，它必须有 2 个奇数度节点，一个节点是路径的起点，一个节点是路径的终点。

要检查边是否为桥，需要从边的一端开始，访问其所有相邻节点及其所有相邻节点，依此类推。如果一个人没有到达边缘的另一侧，那么边缘就是一座桥。对所有邻居进行如此彻底的搜索并不是很昂贵。但是，如果一个人必须在越过每个边缘之前这样做，那么总的努力就很大了。完整的算法称为弗勒里算法，其历史可以追溯到 1883 年。

更有效的算法是Hierholzer（1873）的算法。

如果图像有 2 个奇数节点，那么人们会找到一条路径，否则会找到一个循环，在这两种情况下都非常快，而无需检查桥。

1） 删除所有已经过边后，剩余未经过边的程度对于所有节点都是均匀的。

为什么？

2） 必须至少有一个节点具有已使用和未使用的相邻边。

为什么？

因为 1） 可以找到一个未经过边的循环，从这个节点开始和结束。因为 2） 当这个循环到达这个节点时，它可以包含在第一个路径/循环中。这种对迄今为止未使用的边的循环的嵌入是重复的，直到所有边都被使用，因此有一个欧拉路径或使用所有边的欧拉循环。

这个更快版本的代价是什么？

例如：

     2   4  
    / \ / \ 
   1---3---5

假设第一个循环为 1-3-2-1。节点 3 出现在此循环和未使用的循环 3-4-5-3 中。我们将其插入第一个循环并得到循环 1-3-4-5-3-2-1。没有更多未使用的边，所以算法到此结束，我们找到了欧拉循环。

如何使用我们的界面插入循环？

每当一个人到达一个节点时，一个人也会离开该节点，因此使用偶数条边。现在，一个到达并在偶数度节点上使用一条边。因此，在偶数度节点上总共使用了奇数条边。