→ chengweihsu: (D) DAG任兩點間至多一條path,所以#path應當正比於# 12/16 13:32
→ chengweihsu: node，非指數增長 12/16 13:32
→ chengweihsu: (E) 設G之minimum clique partition 為 12/16 13:32
→ chengweihsu: P = {C_1,...,C_k},其中 |C_i|<=|C_ j|, for all 12/16 13:32
→ chengweihsu: 1 <= i < j <= k,因為G上的每個node至多連出e條邊， 12/16 13:32
→ chengweihsu: 所以該node與其連接的e個node， 12/16 13:32
→ chengweihsu: 共e+1個點，最大只會形成K_(e+1)。 12/16 13:32
→ chengweihsu: n=|V|=|C_1 U ... U C_k|<=|C_1|+...+|C_k| 12/16 13:32
→ chengweihsu: <=k|C_k|=k(e+1) 12/16 13:32
→ chengweihsu: => k >= n/(e+1) 12/16 13:32