欧拉路判定

欧拉回路： 无向图：每个顶点的度数都是偶数，则存在欧拉回路。 有向图：每个顶点的入度都等于出度，则存在欧拉回路。 欧拉路径： 无向图：当且仅当该图所有顶点的度数为偶数 或者 除了两个度数为奇数外其余的全是偶数。 有向图：当且仅当该图所有顶点 出度=入度 或者 一个顶点 出度=入度+1，另一个顶点 入度=出度+1，其 他顶点 出度=入度。 混合图存在欧拉回路条件 要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下： 假设有一张图有向图G'，在不论方向的情况下它与G同构。并且G'包含了G的所有有向边。那么如果存在一个图G'使得G'存在欧拉回路，那么G就存在欧拉回路。 其思路就将混合图转换成有向图判断。实现的时候，我们使用网络流的模型。现任意构造一个G'。用Ii表示第i个点的入度，Oi表示第i个点的出度。如果存在一个点k，|Ok-Ik|mod 2=1，那么G不存在欧拉回路。接下来则对于所有Ii>Oi的点从源点连到i一条容量为(Ii-Oi)/2的边，对于所有Ii<Oi的点从i连到汇点一条容量为(Oi-Ii)/2的边。如果对于节点U和V，无向边（U，V）∈E，那么U和V之间互相建立容量为1的边。如果此网络的最大流等于∑|Ii-Oi|/2，那么就存在欧拉回路。