(a)子图同构问题： 设算法f：能在多项式时间内把图G映射为一个圈。 则算法f可以把本问题的输入映射为Hamilton圈问题的输入，即对于H的所有子图，是否有一个子图存在Hamilton圈。 综上，本问题可以归约为Hamilton圈问题（书上的Rudrata问题）。 (b)最长路径问题： 设算法f：能在多项式时间内找出G的一个含有V个顶点的子图H，且g=V-1。 则算法f可以把这个问题的输入映射为Hamilton路径问题的输入，即对于H的符合条件的子图，是否有一个Hamilton路径存在。 (c)最大SAT问题： 设算法f：能在多项式时间内把输入的句子总数取为g。 则本问题可以规约为SAT问题。 (d)稠密子图问题： 设算法f：能在多项式时间内找到G的子图H，且H的顶点满足2b=a(a-1)。 则此时H中的a个顶点两两相连，本问题即规约为最大团问题。 (e)稀疏子图问题： 设算法f：能在多项式时间内找到G的子图H，且H的顶点满足b=0。 此时本问题可以归约为最大独立集问题。 (f)集合覆盖问题： 设算法f：能在多项式时间内找到输入集合的一个子集。 此时本问题可以归约为最小顶点覆盖问题。 (g)可靠网络问题： Hint中指示的就是TSP问题。 所以若能找到把输入映射为Hint当中给出的例子，本问题即可规约为TSP问题。
