作者nowar100 (拋磚引玉)
看板Grad-ProbAsk
標題[理工] [DM]-chromatic polynomial
時間Wed Jul 22 21:05:19 2009
今天如果有個圖長這樣， ˙─˙ ，對四點著色，求著色多項式？
│ │
˙─˙
<法一>
根據 P(G,λ) = P(G-e,λ) - P(G．e,λ) ，現在把 e 當成是最下面的那個邊
˙─˙ ˙─˙
│ │ ╲╱
˙ ˙ ˙
3
原式 = λ(λ-1) - λ(λ-1)(λ-2)
2
= λ(λ-1)(λ - 3λ + 3)
這是小黃書上寫法
<法二>
這是我的想法，逐一討論，先討論左上點，有λ種選擇
接著討論右上，有λ-1 種
討論左下，有λ-1 種
最後討論右下， 這時候分成兩種情況討論
i) 右上=左下時，此時右下有λ-1 種可選擇
ii) 右上=/=左下時，此時右下有λ-2 種可選擇
3 2
照以上討論，P(G,λ) = λ(λ-1) + λ(λ-1) (λ-2)
2
= λ(λ-1) (2λ- 3)
神奇了，雖然答案皆一樣，λ=2，不過式子卻不同
所以同一題目的 chromatic polynomial 有可能不唯一嗎？
麻煩解答一下囉，謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.93.39
1F：→ doom8199:第二題討論是對的，但列式不對: 07/22 21:11
2F：→ doom8199:λ(λ-1)*1*(λ-1) + λ*(λ-1)(λ-2)^2 07/22 21:12
3F：→ nowar100:請問為什麼^ 是*1 考慮左下的時候不能跟左上同樣不是嗎 07/22 21:27
4F：→ doom8199:先填左上，有λ種填法，然後討論 右上和左下是否同色 07/22 21:32
5F：→ doom8199:<1>同色:先填右上，有(λ-1)種，然後左下因為與右上相同 07/22 21:35
6F：→ doom8199:所以只有1種，接著填左下時就有 (λ-1) 種 07/22 21:36
7F：→ doom8199:<2>不同色: 也是類似的討論 07/22 21:36
8F：→ doom8199: 右 ---> 打錯字 OTZ 07/22 21:37
9F：→ nowar100:懂了 謝謝您 07/22 21:39
10F：→ nowar100:所以列式應該是唯一的才對 07/22 21:39
11F：→ doom8199:不過法一的扣除法我倒是第一次看過 ...離散學太少了XD 07/22 21:42