首页 > 代码库 > 欧拉回路与欧拉路径
欧拉回路与欧拉路径
若图G中存在这样一条路径，从某个顶点出发，使得它恰通过G中每条边一次(通过每一个顶点可以多次),则称该路径为欧拉路径。若该路径是一个圈(回到起点)，则称为欧拉(Euler)回路。
欧拉回路与欧拉路径的充要条件：
1)无向图存在欧拉回路的充要条件:一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。
2)有向图存在欧拉回路的充要条件:一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。
判断无向图是否存在欧拉回路：(1)图联通(dfs或者并查集判图联通)(2)所有顶点的度数均是偶数
判断有向图是否存在欧拉回路：(1)底图(忽略边方向后的无向图)联通(2)每个顶点的入度等于出度
判断无向图是否存在欧拉路径：(1)图联通(dfs或者并查集判图联通)(2)仅有2个顶点(起点和终点)的度数为奇数，其他顶点的度数均是偶数。
判断有向图是否存在欧拉路径：(1)底图(忽略边方向后的无向图)联通(2)只有两个点的入度不等于出度，并且其中一个点出度恰好比入度大1，另一个恰好入度比出度小1，每个顶点其它每个点的入度等于出度
欧拉回路与欧拉路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。