[理工] 离散 chromatic polynomial 合法问题

楼主: befdawn (橙花雨露)   2018-10-03 00:19:33
https://i.imgur.com/4enq8kL.jpg
请问这题的 c,是因为这样吗:
把原式提出 λ 后,
应该要能够因式分解出 λ-1,
也就是如果这条式子要合法,
一定会包含 λ-1 这个着色的方法在里头
换句话说,
不会有这种式子:λ^2-2λ = λ(λ-2)
以上是我自己看解答推的,不知道对不对
作者: gpsmelody07 (YC)   2018-10-03 10:09:00
如果图包含至少一个边,则不可能用1个颜色完成propercoloring,因此P(G,1)=0,也就是说(λ-1)必为P(G,λ)的因式,也才会有系数和要等于0的说法但如果图上无边有3个点,可以用1色proper coloring则P(G,λ)=λ^3,虽(λ-1)不为其因式,但仍是合法的
楼主: befdawn (橙花雨露)   2018-10-04 00:48:00
原来如此,感谢 g大!说明的很清楚

Links booklink

Contact Us: admin [ a t ] ucptt.com