欧拉路判定

2018-05-30 13:06:50


欧拉回路: 无向图:每个顶点的度数都是偶数,则存在欧拉回路。

有向图:每个顶点的入度都等于出度,则存在欧拉回路。

欧拉路径: 无向图:当且仅当该图所有顶点的度数为偶数 或者 除了两个度数为奇数外其余的全是偶数。

有向图:当且仅当该图所有顶点 出度=入度 或者 一个顶点 出度=入度+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,那么就存在欧拉回路。