[理工] 離散 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