助教你好
想請問 用遞迴拆解法 P(G,入)=P(G-e,入)-P(G˙e,入)
是不是有什麼限制 或是需要注意的地方
因為有時候挑不同邊來做 結果好像會不同 X(G)會有出入
ex 96高大離散第九題
http://www2.nuk.edu.tw/lib/exam/96/master/96cs-master.pdf
我先去掉 (x,t) 接著(w,t) 接著(t,y ) 做出的X(G)會是3 可是正確答案是2 麻煩助教了 謝謝
Research Space for Linear Algebra & Discrete Mathematics
1 則留言:
你算的沒問題, 挑邊的順序並不會影響最後的結果, 這裡其實可以直接觀察出你參考的那個答案有誤, 因為 G 具有 size 為 3 的 complete subgraph, 所以著色數一定至少是 3, 此時再畫個用 3 種顏色來做正當著色的圖出來, 即可證明χ(G)=3
(b)小題這裡就真的要進一步去算出著色多項式, 雖然挑的順序沒差, 你可以用自己喜歡的方式來拆, 不過我們時常是會先保留比較大的complete subgraph graph, 然後再利用書上p6-116的定理6-16來算, 所以像這一題, 我可能就會先拆(w,z), 再拆(z,y)
張貼留言