作者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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1538497176.A.04C.html
1F：推 gpsmelody07: 如果图包含至少一个边，则不可能用1个颜色完成proper 10/03 10:09
2F：→ gpsmelody07: coloring，因此P(G,1)=0，也就是说(λ-1)必为P(G,λ) 10/03 10:11
3F：→ gpsmelody07: 的因式，也才会有系数和要等於0的说法 10/03 10:13
4F：→ gpsmelody07: 但如果图上无边有3个点，可以用1色proper coloring 10/03 10:15
5F：→ gpsmelody07: 则P(G,λ)=λ^3，虽(λ-1)不为其因式，但仍是合法的 10/03 10:16
6F：→ befdawn: 原来如此，感谢 g大！说明的很清楚 10/04 00:48