作者befdawn (蜜蜂P助)
看板Grad-ProbAsk
標題[理工] 離散 chromatic polynomial 合法問題
時間Wed Oct 3 00:19:33 2018
https://i.imgur.com/4enq8kL.jpg
請問這題的 c，是因為這樣嗎：
把原式提出 λ 後，
應該要能夠因式分解出 λ-1，
也就是如果這條式子要合法，
一定會包含 λ-1 這個著色的方法在裡頭
換句話說，
不會有這種式子：λ^2-2λ = λ(λ-2)
以上是我自己看解答推的，不知道對不對
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.105.90.47
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1538497176.A.04C.html
推 gpsmelody07: 如果圖包含至少一個邊，則不可能用1個顏色完成proper 10/03 10:09
→ gpsmelody07: coloring，因此P(G,1)=0，也就是說(λ-1)必為P(G,λ) 10/03 10:11
→ gpsmelody07: 的因式，也才會有係數和要等於0的說法 10/03 10:13
→ gpsmelody07: 但如果圖上無邊有3個點，可以用1色proper coloring 10/03 10:15
→ gpsmelody07: 則P(G,λ)=λ^3，雖(λ-1)不為其因式，但仍是合法的 10/03 10:16
→ befdawn: 原來如此，感謝 g大！說明的很清楚 10/04 00:48