在证明 HC 属于 NPC 类的过程中，需要将简单图 G1(如下图所示)多项式时间变换到简单图 G1*。 请先构造证明该问题时用到的检测覆盖子图 G，再构造 G1*。(仅画出图 G 和 G1*即可)

好的，我理解了你的问题。在证明 HC 属于 NPC 类的过程中，需要用到检测覆盖问题（DS）。我们可以先构造一个图 G（如下图所示），其中每个节点代表 G1 中的一个顶点，每个节点之间有一条边当且仅当它们对应的顶点在 G1 中有边相连。


然后，我们需要对 G 进行多项式时间的变换，得到一个新的简单图 G1*。构造 G1* 的方法如下：

1. 对于 G 中的每个节点 v，我们在 G1* 中构造两个节点 v1 和 v2。
2. 对于 G 中的每条边 (u, v)，我们在 G1* 中构造一条有向边 (u2, v1)。

最终得到的 G1* 如下图所示：


这样构造出来的 G1* 是一个有向无环图，且每个节点的入度和出度均为 1。同时，G1* 中存在一个大小为 k 的路径覆盖，当且仅当 G1 存在一个大小为 k 的哈密顿回路。因此，检测覆盖问题 DS 是 NP 完全问题，可以用来证明 HC 属于 NPC 类。