欧拉路径
liumuyvan
·
2023-07-16 19:22:19
·
个人记录
相信很多人都听说过七桥问题，什么？你没听说过，没关系，我们一起来看看。七桥问题。
很多人可能会觉得这和我们小时候玩的一笔画问题很像，没错，这就是我们今天要讨论的问题。
定义
欧拉路径的定义为:“在一个图中，从某一点出发，经过一条不间断的路径，经过所有边一次且仅一次。（这个图可以有向也可以无向甚至可以是混合图）”就像我们的一笔画一样。当然我们可以轻易得到一个结论：“每个图可能有多条欧拉路径。”而首尾相连的欧拉路径，被称作欧拉回路。如果一个图，它只有欧拉路径但没有欧拉回路，那它就被称作半欧拉图；若它有欧拉回路，则被称为欧拉图。
判断
知道了定义，那怎么判断呢？在无向图里，若所有变得度数都是偶数，那么它是欧拉图，若仅有两个顶点的度数是奇数，那么它是半欧拉图。在有向图里，若所有顶点的入度等于出度，那么它是欧拉图，若仅有一个顶点出度比入度多一（起点），且仅有一个顶点入度比出度多一（终点）那么它是半欧拉图。证明也非常简单，欧拉图需要每个顶点一进一出，相互匹配。半欧拉图则需要两个特例，一个少一个出边，一个少一个入边（虽然在无向图里不好区分）。
计算
学习完这些，我们要引入一个新的推论：“欧拉图中每一条欧拉路径都是欧拉回路。”这个很好理解，但是有什么用呢？它可以简化你在求欧拉回路时的步骤，只需要求出欧拉路径即可。
那怎么求欧拉路径呢？
我们要判断这个图是欧拉图还是半欧拉图（方法如上）。
分类讨论一下，如果是欧拉图，就可以随便找一个点，跳过此步；如果是半欧拉图，就再分类讨论，如果是无向图，就找两个度数为奇数的点之一，如果是有向图，就找出度比入度多一的那个点。
然后进行DFS遍历，并记录沿途经过的点。注意，这里要标记（记录下来不能再走）的是边，不是点（具体方法不会的可以去查百度）。
等到遍历结束，存下来的路径就是欧拉路径/回路。
好啦，关于欧拉路径的就这些完结撒花。
PS
作者在学习欧拉路径之前也曾经被它吓到过，导致一直没敢学，学了之后发现其实非常简单，所以还是不要被它“狰狞”的外表吓着了，好好学就行。