《算法概论》习题8.10
2018-01-20 本文已影响0人
岛上痴汉
1.png
2.png
- a. 令图G 为一个环，环上的顶点数等于图 H 的顶点数。那么若G 是 H 的同构子图，则说明 H 存在 Rudrata 回
路。于是知 Rudrata 回路事实上是子图同构问题的一个特例。 - b. 如果令 g =| V | −1，即得到一条 Rudrata 路径。
- c. 令 g 为子句的总数，即成 SAT。
- d. 令 b=a(a-1)/2,此时这 a 个顶点两两相连，于是即成最大团问题。
- e. 令b = 0，即成最大独立集问题。
- f. 显然是最小顶点覆盖的一个推广。
- g. Hint 中所描述的特例即是一个 TSP。
