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