欧拉路径与欧拉回路
1.无向图的欧拉路径
在一张无向图 \(G\) 中，存在一条路径可以不重复地经过每一条边。
2.欧拉回路
欧拉回路是一条特殊的欧拉路径，起点和终点重合。
3.无向图存在欧拉路径的充分必要条件
度数为奇数的点的个数要么是 \(0\) 个，要么是 \(2\) 个。
4.实现方法
-
判定是否有解
-
选取一个度数为奇数的点作为起点
-
\(\text{dfs}\) 搜索每一条边并标记
-
存储经过的顶点必须在递归之后
汉密尔顿环问题
在一张无向图 \(G\) 中，存在一条路径可以不重复地经过每一个点。
这个问题目前没有非暴力的解法，属于 \(\text{NP}\) 难题。
标签：一条,text,路径,问题,图上,无向,回路,一些,欧拉 From： https://www.cnblogs.com/yhx-error/p/16818220.html