作者goodGG (( ￣ c￣)y▂ξ)
看板Math
標題Re: [離散] 著色數問題
時間Sun May 2 20:52:49 2010
※ 引述《xdd1524 (一個人的牙刷)》之銘言：
: Q:對一個具有n個頂點的cycle,相鄰之頂點不同色
: 找出最小著色數?
: 這題一開始知道情況要分奇數點跟偶數點
: 很簡單就知道
: 奇數點的最小著色數是3,偶數點是2
: 但是證明就遇到麻煩了
可以直接證呀。
C_n: n-cycle.
(1) If n is even, then χ(C_n) > 1. So χ(C_n)≧2.
把著色數 2 的著色法找出來，這很顯然。
(2) If n is odd, then χ(C_n) > 2. (這很顯然)
So χ(C_n)≧3，把著色數 3 的著色法找出來，這很顯然。
: 自己想法是先把偶數點的cycle的著色多項式寫出來
: 寫出來後就可以用分解定理直接寫出奇數點的著色多項式
: 但就是想不到要如何寫偶數點的多項式
: 有高手可以指點一下嗎,thx
當 n > 2, 砍掉 C_n 的某邊會變 P_n 與 C_{n-1}.
硬幹。( χ(C_3;k) = k(k-1)(k-2). χ(P_n;k) = k(k-1)^{n-1}. )
可以用 induction on n 做上去, 試試看.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.229.33
推 xdd1524 :看不太懂,什麼叫做把著色數2(3)的著色法找出來? 05/02 21:30
→ xdd1524 :是說把圖畫出來還是怎樣? 05/02 21:30
→ xdd1524 :別人給我的答案是個把n=3,4情況畫出來,然後就證完... 05/02 21:36
這樣不行，要把所有的 n 畫出來。
推 hcsoso :畫圖也許 ok, 或是把點標號, 然後直接定一個著色 05/02 21:47
推 xdd1524 :所以說直接可以圖畫出來,然後直接定論推到n都成立? 05/02 21:57
→ xdd1524 :雖然答案是正確的,不過真的可以這樣做? 05/02 21:58
Write down the 2-coloring of C_n if n is even explictly.
3-coloring odd
--
※ 編輯: goodGG 來自: 118.160.169.206 (05/03 11:29)