1. Determine the vertex connectivity of G
請問這是要算什麼阿~? 算什麼個數~? 答案: 2
2. independent set : maximal indep. set
這是找圖中完全沒有連結到的點，但補圖卻是最大的cligue ??
3. dominating set : minimal dominating set
這個是要找點還是找邊??
4. covering : minimal covering
這是說找最少的點涵蓋所有邊嗎?
不好意思，簡單的幾個問題，書上沒找到解釋~~"
老師當初上課有講但忘了
謝謝
請問這是要算什麼阿~? 算什麼個數~? 答案: 2
2. independent set : maximal indep. set
這是找圖中完全沒有連結到的點，但補圖卻是最大的cligue ??
3. dominating set : minimal dominating set
這個是要找點還是找邊??
4. covering : minimal covering
這是說找最少的點涵蓋所有邊嗎?
不好意思，簡單的幾個問題，書上沒找到解釋~~"
老師當初上課有講但忘了
謝謝
10 則留言:
1.connectivity:最少取幾個點可以導致G不連通,答案2的話就是最少也要2個點的意思.
4.選最少的點來蓋住所有的邊
1.沒圖沒真相(誤
開玩笑的啦
可是沒有圖你給答案也不知道從何推敲阿orz
2.補圖的定義不就是
本來沒有邊的 要全部變有邊 而且包括原來的點喔
所以我想不只independent set
其他像dominating set和vetex covering 等等的補圖 應該也是最大clique
3.找點 與其他點至少有一邊相連的點
4.應該沒錯 我那時候是記圖上任一邊有點相連
圖長這樣
............a
.....e......r......b
.........d......c
(a,e) (a,d) (a,r) (e,d) (b,c)
(r,c) (r,d) (c,d) 八個邊
怎樣去掉2點不連通~~?
3.dominating set
還是不太懂~ 其他大致上了解
去掉點{r,d}就不通了或{r,c}或{a,d}都可以
意思大概是這樣:
a.....b.....c
你把b拿走,a和c就變成兩個分量了
{a,d} {a,c}都可以
{r,c} {r,c}好像還是連通
1.抱歉 我英文真是太爛
我看了你們討論我糊塗了orz
因為我想說不連通的點 砍掉C就好了阿
這樣b就和其他人不連通了
我的猜測:
題目要求的應該是指cut set
他是指"邊" 不是"點"
所以你拿掉(r,c) (d,c)
兩邊後 就變成不連通的圖了
這一段是不負責讓發言 還是問助教比較好orz
3.那換個說法
選擇圖上的點把所有點連起來
(0...1...0) 這樣1就連了兩個點0
有被連到就算
這樣有比較好想嗎?
所以答案會不只一組解
可能有MIN 有MAX
ps.
其實我看到你用那個點點點來畫圖
我覺得超有趣的XD
沒想過可以這樣表示
1.最少去掉幾個點會不連通
2.點點之間沒有邊相連的集合
3.為一點的集合 其中點與所有點有邊相連
4.與所有邊相鄰的點集
這樣吧
因為不用...
用空白它會縮在一起
謝謝幫忙解答的人
張貼留言