题目：
利用推广的方法证明NP-完全性。对以下每个问题，请通过证明它是本章某个NP-完全问题的推广说明它是NP-完全的。
(a)子图同构：给定两个作为输入的无向图G和H，判断G是否与H的某个子图同构，且如果是，返回由V(G)到V(H)的相关映射。
(b)最长路径：给定图G和整数g，求G中一条长为g的简单路径。
(c)最大SAT：给定一个CNF公式和整数g，求满足其中至少g个子句的真赋值。
(d)稠密子图：给定一个图和两个整数a,b，求G中的a个顶点，使得他们之间最少有b条边。
(e)稀疏子图：给定一个图和两个整数a和b，求G中的a个顶点，使得它们之间最多有b条边。
(f)集合覆盖
(g)可靠网络：给定两个n*n矩阵，一个距离矩阵dij，一个连接需求矩阵rij以及预算b。我们要求一个图G={{1,2,3,….n},E}使得：(1)其中所有边的总代价不超过b；(2)在任意两个不同的顶点i和j之间，存在rij条顶点互不相交的路径。（提示：假设所有的dij都为1或2，b = n，所有的rij = 2，想一下这是哪个著名的NP-完全问题？）
证明：
(a)令图G为一个环，环上的顶点数等于图H的顶点数。那么若G是H的同构子 图,则说明 H 存在 Rudrata 回路。因此， Rudrata 回路事实上是子图同构问题的一个特例。
(b) 令g = |V| - 1， 则实际上在求一条Rudrata 路径。
(c)令g为子句的总数，则成了SAT问题。
(d)令b= a(a−1)/2，则问题变成了最大团问题。
(e)令b=0， 则问题变成了最大独立集问题。
(f)集合覆盖就是最小顶点覆盖的一个推广。将G={V,E}，以及最小顶点覆盖k，推广成集合覆盖的全集S，子集Ci，以及集合覆盖k。其中令S = V，Ci为与顶点i有连边的边集。则集合覆盖k等于最小顶点覆盖k。
(g)假设所有dij都为1或2，b=n，所有的rij=2， 则这是一个TSP问题。