2020-2021:teams:hotpot:circuit

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:hotpot:circuit [2020/05/20 20:46]
misakatao [求解]
+++ 2020-2021:teams:hotpot:circuit [2020/05/20 21:05] (当前版本)
misakatao 更新
@@ 行 131: / 行 131: @@
 (3)当(2)不能继续进行时结束算法。
+<del>先研究一下边表写法</del>代码看[[https://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html|这篇博客]]
+======哈密顿回路问题======
+=====定义=====
+哈密顿回路指的是一个回路通过图的每个点一次且仅一次，每条边最多一次的回路。
+=====判定=====
+**Dirac定理(充分条件)**
+设一个无向图中有$N$个顶点，若所有顶点的度数大于等于$\frac{N}{2}$，则哈密顿回路一定存在。($\frac{N}{2}$指的是$[\frac{N}{2}]$，向上取整)。
+**必要条件**
+设图$G=\langle V,E \rangle$是哈密顿图，则对于$V$的任意一个非空子集$S$，若以$|S|$表示$S$中元素的数目，$G-S$表示$G$中删除了$S$中的点以及这些点所关联的边后得到的子图，则$W(G-S) \le |S|$成立。其中$W(G-S)$是$G-S$中连通分量数。
+**$N(N \ge 2)$阶竞赛图一定有哈密顿回路。**（竞赛图是通过在无向完整图中为每个边分配方向而获得的有向图）
+=====求解=====
+由Dirac定理为前提构造
+(1) 任意找两个相邻的节点$S$和$T$，在其基础上扩展出一条尽量长的没有重复结点的路径。即如果$S$与结点$v$相邻,而且$v$不在路径$S \rightarrow T$上,则可以把该路径变成$v \rightarrow S \rightarrow T$，然后$v$成为新的$S$。从$S$和$T$分别向两头扩展，直到无法继续扩展为止，即所有与$S$或$T$相邻的节点都在路径$S \rightarrow T$上。
+(2) 若$S$与$T$相邻，则路径$S \rightarrow T$形成了一个回路。
+(3) 若S与T不相邻,可以构造出来一个回路。设路径$S \rightarrow T$上有$k + 2$个节点，依次为$S, v1, v2 ... vk, T$。可以证明存在节点$v_i(i \in [1, k])$，满足$v_i$与$T$相邻，且$v_{i+1}$与S相邻。找到这个节点$v_i$，把原路径变成$S \rightarrow v_i \rightarrow T \rightarrow v_{i+1} \rightarrow S$，即形成了一个回路。
+(4) 到此为止，已经构造出来了一个没有重复节点的的回路，如果其长度为N，则哈密顿回路就找到了。如果回路的长度小于$N$，由于整个图是连通的，所以在该回路上，一定存在一点与回路之外的点相邻。那么从该点处把回路断开，就变回了一条路径，同时还可以将与之相邻的点加入路径。再按照步骤1的方法尽量扩展路径，则一定有新的节点被加进来。接着回到步骤(2)。
+时间复杂度为$O(n^2)$。代码可以看[[https://www.cnblogs.com/Ash-ly/p/5452580.html|这篇博客]]

2020-2021/teams/hotpot/circuit.1589978788.txt.gz · 最后更改: 2020/05/20 20:46 由 misakatao