想請教兩個基本的題目
Problem 1: 老師上課有補充 Covering 的定義，我抄的內容是 "選取的點，可以連通所有vertices" 但是我的例子又好像不是這樣。
所以我上網Google後找到 covering 分為兩種，一種是 vertex covering，另一種是 edge covering，前者是 "選取的點，可以連通所有 edges" 我覺得這樣定以好像才對吧?所以應該是我抄錯?
另外，既然有兩種 covering 的定義，那麼一般我們會討論哪一個呢?
Problem 2 : P.6-126 範例 9
我想問 (b)，雖然我已經懂解答中的黏點方式計算，但是我試著用一個點一個點推的，卻得不到正確解答。
My Thinking :
w 可以有 入 種方法
x, z 皆與 w 相連，所以 x, z 的方法數是 (入-1)種
t 雖然也跟 w 相連，但是又與 x 相連，所以方法數是 (入-2)種
y 跟 x, t, z 相連，但是可以跟 w 同色，所以方法數是 (入-2)種
這樣子的話，P(G,5) = 5*(5-1)*(5-1)*(5-2)*(5-2) = 5 * 16 * 9 = 720 ????
為什麼會比答案的 600 多 120 呢???
麻煩助教了! 謝謝
6 則留言:
您好：
1. 確實用的是前者的定義，老師講這個我認為是跟演算法有關，求 minimal vertex cover 問題是我們演算法中著名的NP complete問題，仍為我們考試範圍。
2. 您的討論法不正確，若您假設w,y同色，則x的著色數就不會是 (5-1)種，而是(5-2)種(w,y,t與之相連)。
以上淺見..
建議您用著色多項式較安全。
謝謝月戀大!
第二題重新推導有得到 600
w y 同色
w 5
y 1
x 5-1
i 5-2
z 不要是w那一色即可，固有 5-1色
共 5 * 1 * 4 *3 *4 = 240
w y 異色
w 5
x 5-1
i 5-2
y 5-3(x和i和w三種色)
z 5-2(w和y兩種色)
共 5*4*3*2*3 = 360
240 + 360 = 600
老師上課教的covering和演算法談的vertex cover是一樣的, 定義寫在習題第6-104題, 同學可稍微看一下, 還有6-106也是相關的題目
知道了! 謝謝助教!!!
請問著色多項式 是先拆wz 再zy 再用上三角加1個點的-上三角-上三角嘛??
張貼留言