2010-02-21

[離散] - 圖論 3


For the following graph, how many maximal cliques of size 3 are there,
and what is the size of maximum idependent sets?

答案是 8跟4嗎?
於

10 則留言:

  1. Chesley2010年2月21日 下午4:41

    同一題借問，
    1.minimal dominating set size?
    2.minimal covering ?

    回覆刪除
  2. Chesley2010年2月21日 下午4:46

    我還是有點搞不懂

    indep. set
    找最多點，然後每個點都不相連?

    dominating set ???
    covering 找最少點可以包含所有邊?

    回覆刪除
  3. 匿名2010年2月21日 下午4:55

    乍看之下我也覺得是8/4..

    回覆刪除
  4. Chesley2010年2月21日 晚上8:19

    1.minimal dominating set size? 2
    2.minimal covering ? 4

    這樣對嗎~?

    回覆刪除
  5. chi2010年2月22日 凌晨12:20

    maximal cliques是4
    cliques是求最大的，所以只有外面那四個三角形

    maximum idependent set也是4
    外面那四點為最大的獨立集

    minimal dominating set size為4
    好像只能取中間那四點才可形成minimal dominating set size

    minimal covering不太懂，麻煩助教講解一下…

    回覆刪除
  6. 線代離散助教(wynne)2010年2月22日 凌晨12:20

    上面兩個對, maximum independent sets 的 size 為 4 也沒錯, 不過maximal cliques of size 3只有 4 個, 因為只要是在中間那個K4裡的三角形都不是maximal

    回覆刪除
  7. 線代離散助教(wynne)2010年2月22日 凌晨12:23

    minimal covering就是用最少的點去涵蓋到所有的邊, 書上有定義你可以查一下

    回覆刪除
  8. glay_luncy2010年2月22日 凌晨2:35

    那minimal covering不就是
    演算法的vertex cover??

    回覆刪除
  9. glay_luncy2010年2月22日 凌晨3:07

    mim, dominating set is 2才對

    取中間K4對角任兩點即可把點分成兩堆
    一堆為在dominating set的點

    一堆為跟dominating set有邊相連

    所以兩個就夠了

    回覆刪除
  10. Chesley2010年2月22日 上午9:38

    結論是
    maximal cliques是4，因為如果中間可以取到K4，取K3不是maximal

    maximum idependent set 4
    minimal dominating set size 2
    minimal covering 4

    回覆刪除