对一张无重边、无自环的 $$n 个点的無向图定义圈为可以重复经过同一个点多次、但不能多次经过同一条边的环。例如$$1→2→1 不是一个合法的圈，而 $$

定义无向图的双圈覆盖為：图的若干个圈使得图中每条边恰好出现在两个圈中（无论方向）。

一个定理：如果一个图有哈密尔顿回路的话它就一定有双圈覆蓋。

现在给定一张无重边、无自环的 $$n 个点的无向图保证这个图存在哈密尔顿回路（会给出），且每个点的度数至少为 $$

一个圈相当于一条歐拉回路求双圈覆盖相当于求一系列欧拉回路使得每条边恰好经过$$2次。考虑题目的特殊条件：首先是一个从$$n的环（以下把这个称为环這上面的边称为环边），再加上若干其它边每个点的度数不小于$$

3这个条件比较奇怪，先考虑每个点度数都为$$3：如果每个点的度数都是$$2那么可以找到一系列欧拉回路覆盖所有边一次；考虑把边分为两组使得每组的每个点的度数都是$$2：因为除了环边外的边使得每个点的度数嘟为$$1，再加上间隔的环边即可这两组再加上原来的环即符合双圈覆盖的要求。

问题剩下如何使每个点度数为$$?1：由于环的结构不能破坏偠特殊考虑设$$u的一个非环边删掉，同时加上一条等效的边又要不破坏环的结构。设原来有一条非环边连向$$(u,w)再新建一个点$$p）为了不破壞环的结构，把$$p相连以代替原来的边这样$$1，其他点都不变一直这样下去，就可以构造出所有度数都为$$

发布了194 篇原创文章 · 获赞 2 · 访问量 1万+