[理工] [DM]-chromatic polynomial

[nowar100 (拋磚引玉)]

今天如果有個圖長這樣， ˙─˙ ，對四點著色，求著色多項式？
                       │  │
                       ˙─˙


<法一>

根據 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
→ doom8199:第二題討論是對的，但列式不對:
→ doom8199:λ(λ-1)*1*(λ-1) + λ*(λ-1)(λ-2)^2
→ nowar100:請問為什麼^ 是*1  考慮左下的時候不能跟左上同樣不是嗎
→ doom8199:先填左上，有λ種填法，然後討論 右上和左下是否同色
→ doom8199:<1>同色:先填右上，有(λ-1)種，然後左下因為與右上相同
→ doom8199:所以只有1種，接著填左下時就有 (λ-1) 種
→ doom8199:<2>不同色: 也是類似的討論
→ doom8199:　　　　　　　　　 右      ---> 打錯字 OTZ
→ nowar100:懂了  謝謝您
→ nowar100:所以列式應該是唯一的才對
→ doom8199:不過法一的扣除法我倒是第一次看過 ...離散學太少了XD