請問助教,關於這兩題圖形分解的部份看不懂是怎麼進行的
6-98 EX4
這列圖形是指
一開始是由
P=(G,λ)=P(G-e,λ)-P(G*e,λ)開始著手?
這裡有疑問
這邊指的是
P(G-e,λ)=P(G-e-e,λ)-P(G-e*e,λ), G-e*e=G*e這樣嗎
故P(G,λ)=P(H-e,λ)-P(H*e,λ)-P(G*e,λ)
=P(H-e,λ)-2PP(G*e,λ)
6-115 Ex8
G1是G1左邊的圖
兩點視為同一點的結果嗎
兩點間無邊也可以重疊?
3 則留言:
1. (P6-98 EX4)
你的式子在寫法上有些問題, 因為在符號上會照成混淆, 或許你可以直接用想的, 不要看式子, 這裡只是不斷recursive的去做拆邊黏點的procedure, 直到我們可以求出最後剩下的那個圖的著色數為止, 所以假設在第一列中間那個沒有被命名的圖, 假設它叫 G', 則
P(G,λ) = P(G',λ)-P(G1,λ)
再對 G' 做拆邊黏點, 可得
P(G',λ) = P(G2,λ)-P(G1,λ)
所以 P(G,λ) = [P(G2,λ)-P(G1,λ)]-P(G1,λ)
= P(G2,λ)-2P(G1,λ)
然後因為我們還是不知道P(G1,λ)是多少,
所以後面就再拆G1的邊繼續往下做
2. (P6-115 Ex84)
對, 就是黏點, 這就跟上面那一題我們對G'所做的事情是一樣的; 其實拆邊就是指 e 的兩端點可以隨便塗, 而重疊的概念就是將被拆掉的 e 的兩端點a,b著同樣顏色, 那著不同色的方法數就是將全部的可能扣掉a,b著同色, 若有這樣的概念應該就會發現著色分解定理其實還滿單純的, 也不太需要去記方法了
謝謝助教
一開始看不太出遞迴的關係
這下我豁然開朗了
再請問圖形旁邊可以直接標示代號
如解答中圖型下直接標示G1 G2?
一直覺得有點怪
為了方便說明, 只要在不會產生混淆的情況下, 在考卷上面寫的東西都可以自己取名字, 這樣你再寫答案時就不用畫一大堆圖, 就像題目裡的 G 也只是一個符號而已, 其他像是P(G,λ)這種東西也都是符號, 考試時如果你要用到它, 那請記得要寫上 "令P(G,λ)為用λ種顏色對G著色的方法數, ..." 諸如此類的敘述
張貼留言