2007-12-19

[離散][四版習題本] ch6 圖論 6-87 p381



如框框
第一個框框：為什麼G2之chtomatic number會比G1小呢?
第二個框框：為什麼G減掉G2的其中一點後等於G1 的 chtomatic number?
麻煩懂的人指點一下吧....圖論的證明我都覺得好抽象 所以轉不過來~
謝謝囉~
張貼者： 於
標籤：

1 則留言:

線代離散助教(wynne) 提到...

因為計算各component的著色數是獨立事件,
所以要算一個graph G的最小著色數
一定是取著色數大的那個component的, 也就是G1
所以G2的最小著色數最多不超過G1

也是因為獨立, 此時若去掉G2中的一點,
並不會去影響到G1的著色數, 那G的也就不會改變

2007年12月19日 凌晨2:01

張貼留言

訂閱： 張貼留言 (Atom)