欧拉回路与欧拉路径

给定一个无向图G, 一条路径经过图G的每一条边, 且仅经过一次, 这条路径称为欧拉路径(Eulerian Tour), 如果欧拉路径的起始顶点和终点是同一顶点,则称为欧拉回路(Eulerian circuit).

欧拉路径算法：

　　无向图G存在欧拉路径的充要条件：             1.图G是连通的。

                                                               2.至多除两个点外（可以为0个，连通图不可能有且仅有一个顶点的度为奇数），其他所有顶点的度为偶数。

                                                               要找欧拉路径，满足上述条件，只要简单的找出一个度数为奇数的节点，遍历节点，看是否图连通。

判断一个图中是否存在欧拉回路：

一、无向图

每个顶点的度数都是偶数，则存在欧拉回路。

二、有向图

每个节顶点的入度都等于出度，则存在欧拉回路。

三、混合图（有的边是单向的,有的边是无向的。常被用于比喻城市里的交通网络,有的路是单行道,有的路是双行道）

找到一个给每条无向边定向的策略，使得每个顶点的入度等于出度，这样就能转换成有向图的情况。这就可以转化成一个二分图的最大匹配问题。

欧拉回路与欧拉路径

原文：https://www.cnblogs.com/yuanweidao/p/10843822.html