Research Space for Linear Algebra & Discrete Mathematics
同一題借問，1.minimal dominating set size?2.minimal covering ?
我還是有點搞不懂indep. set 找最多點，然後每個點都不相連?dominating set ???covering 找最少點可以包含所有邊?
乍看之下我也覺得是8/4..
1.minimal dominating set size? 22.minimal covering ? 4這樣對嗎~?
maximal cliques是4 cliques是求最大的，所以只有外面那四個三角形maximum idependent set也是4外面那四點為最大的獨立集minimal dominating set size為4好像只能取中間那四點才可形成minimal dominating set sizeminimal covering不太懂，麻煩助教講解一下…
上面兩個對, maximum independent sets 的 size 為 4 也沒錯, 不過maximal cliques of size 3只有 4 個, 因為只要是在中間那個K4裡的三角形都不是maximal
minimal covering就是用最少的點去涵蓋到所有的邊, 書上有定義你可以查一下
那minimal covering不就是演算法的vertex cover??
mim, dominating set is 2才對取中間K4對角任兩點即可把點分成兩堆一堆為在dominating set的點一堆為跟dominating set有邊相連所以兩個就夠了
結論是maximal cliques是4，因為如果中間可以取到K4，取K3不是maximalmaximum idependent set 4minimal dominating set size 2minimal covering 4
張貼留言
10 則留言:
同一題借問，
1.minimal dominating set size?
2.minimal covering ?
我還是有點搞不懂
indep. set
找最多點，然後每個點都不相連?
dominating set ???
covering 找最少點可以包含所有邊?
乍看之下我也覺得是8/4..
1.minimal dominating set size? 2
2.minimal covering ? 4
這樣對嗎~?
maximal cliques是4
cliques是求最大的，所以只有外面那四個三角形
maximum idependent set也是4
外面那四點為最大的獨立集
minimal dominating set size為4
好像只能取中間那四點才可形成minimal dominating set size
minimal covering不太懂，麻煩助教講解一下…
上面兩個對, maximum independent sets 的 size 為 4 也沒錯, 不過maximal cliques of size 3只有 4 個, 因為只要是在中間那個K4裡的三角形都不是maximal
minimal covering就是用最少的點去涵蓋到所有的邊, 書上有定義你可以查一下
那minimal covering不就是
演算法的vertex cover??
mim, dominating set is 2才對
取中間K4對角任兩點即可把點分成兩堆
一堆為在dominating set的點
一堆為跟dominating set有邊相連
所以兩個就夠了
結論是
maximal cliques是4，因為如果中間可以取到K4，取K3不是maximal
maximum idependent set 4
minimal dominating set size 2
minimal covering 4
張貼留言