Research Space for Linear Algebra & Discrete Mathematics
請問 這個 6-95 的解答 有點看不太懂 為什麼是 一直加邊 變成 kn 呢？
這題解答這樣寫怪怪的我之後會在勘誤表更新這題的解法想法應該是說, 假設G的點集可以被分成 k 堆每堆著同一顏色, 那麼若有 λ 種顏色即有λ(λ-1)...(λ-k+1)種塗法 (此時最高項次為λ^k)所以若分成 k 堆的方法有 n_k 種著色多項式從另個角度看其實就是在加總這些途法i.e., P(G,λ) = ∑ (n_k) * λ(λ-1)...(λ-k+1), k = 1~n這也是某些書對於著色多項式的定義所以說 λ^n 這一項只會在點集被分成 n 堆時才會出現因為將 n 個點分成 n 堆的方法只有一種所以 λ^n 之係數n_k = 1如果對上述著色多項式的定義不太熟悉另一個作法是利用數學歸納法, 對邊數做歸納Hint: 假設 G 的邊數少於 k 時成立在 G 有 k 個邊時利用拆邊黏點的分解定理再加上induction hypothesis即可得證
謝謝助教 真的超強 一點就通 十二萬分感謝
張貼留言
2 則留言:
這題解答這樣寫怪怪的
我之後會在勘誤表更新這題的解法
想法應該是說, 假設G的點集可以被分成 k 堆
每堆著同一顏色, 那麼若有 λ 種顏色
即有λ(λ-1)...(λ-k+1)種塗法 (此時最高項次為λ^k)
所以若分成 k 堆的方法有 n_k 種
著色多項式從另個角度看其實就是在加總這些途法
i.e., P(G,λ) = ∑ (n_k) * λ(λ-1)...(λ-k+1), k = 1~n
這也是某些書對於著色多項式的定義
所以說 λ^n 這一項只會在點集被分成 n 堆時才會出現
因為將 n 個點分成 n 堆的方法只有一種
所以 λ^n 之係數n_k = 1
如果對上述著色多項式的定義不太熟悉
另一個作法是利用數學歸納法, 對邊數做歸納
Hint: 假設 G 的邊數少於 k 時成立
在 G 有 k 個邊時利用拆邊黏點的分解定理
再加上induction hypothesis即可得證
謝謝助教 真的超強 一點就通 十二萬分感謝
張貼留言