1.png
2.png
- a. 令圖G 為一個環(huán)，環(huán)上的頂點(diǎn)數(shù)等于圖 H 的頂點(diǎn)數(shù)。那么若G 是 H 的同構(gòu)子圖，則說明 H 存在 Rudrata 回
路。于是知 Rudrata 回路事實(shí)上是子圖同構(gòu)問題的一個特例。 - b. 如果令 g =| V | ?1，即得到一條 Rudrata 路徑。
- c. 令 g 為子句的總數(shù)，即成 SAT。
- d. 令 b=a(a-1)/2,此時這 a 個頂點(diǎn)兩兩相連，于是即成最大團(tuán)問題。
- e. 令b = 0，即成最大獨(dú)立集問題。
- f. 顯然是最小頂點(diǎn)覆蓋的一個推廣。
- g. Hint 中所描述的特例即是一個 TSP。
