欧拉回路

Obelia ·

更新时间:2024-09-20

· 663 次阅读

欧拉通路

定义

从图G一个节点出发走完全部的边，且这条路上的每个边恰好只经过一次。这样的路称为欧拉通路

无向图的欧拉通路

判断是否存在欧拉通路

无向图

如果一个图G是连通图，G中仅有两个节点的度数是奇数，其他节点的度数均是偶数，那么图G存在欧拉通路

有向图

G为有向图，G中仅有两个节点特殊节点，一个节点入度比出度大1（通路的终点），另外一个节点是出度比入度大1（通路的起点），其余节点入度等于出度，那么图G中存在欧拉通路

欧拉回路

定义

图G中若存在欧拉通路且该欧拉通路是回路，那么该回路称为欧拉回路。欧拉回路其实是欧拉通路的特殊情况

无向图的欧拉回路

判断是否存在欧拉回路

无向图

图G连通，所有节点的度数都是偶数，那么无向图G存在欧拉回路

有向图

图G连通，所有节点的入度和出度都相等，那么有向图G存在欧拉回路

判断欧拉通路

下面是有向图判断是否存在欧拉通路(前提是图已经连通):

int in[maxn],out[maxn];  //记录节点的出度和入度
int n;
bool judge(){
    int num1=0,num2=0;   //记录起点和终点个数
    for(int i=1;i<=n;i++){
        if(in[i]!=out[i]){
            if(in[i]==out[i]+1)
                num1++;  //满足起点
            else if(out[i]==in[i]+1)
                num2++;  //满足终点
            else return false;  //存在其他情况一定不存在
        }
    }
    if( (num1==1 && num2== 1) || (num1==0 && num2==0)) return true; //要么欧拉通路要么欧拉回路
    else return false;
}

作者：Happig丶

回路欧拉欧拉回路

1024 个赞