[理工] 離散證明題

看板Grad-ProbAsk作者 (yu12510 )時間7年前 (2018/12/18 20:59), 7年前編輯推噓4(4推 0噓 20→)
留言24則, 5人參與, 7年前最新討論串1/1
各位好 想問一下大神有沒有這些證明的頭緒 https://imgur.com/a/d5wUNhM https://imgur.com/a/uuizLKh 這裡的k(G)是指 : The size of the 「smallest」 vertex cut 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.1.40 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545137964.A.EE5.html
推
12/19 00:56, 7年前 , 1F
第一題 寫得潦草 有錯提醒一下 https://i.imgur.com/bPrw7
12/19 00:56, 1F
→
12/19 00:56, 7年前 , 2F
iJ.jpg
12/19 00:56, 2F
→
12/19 00:57, 7年前 , 3F
12/19 00:57, 3F
→
12/19 01:01, 7年前 , 4F
12/19 01:01, 4F
→
12/19 06:20, 7年前 , 5F
抱歉 匆忙看錯題目
12/19 06:20, 5F
→
12/19 06:22, 7年前 , 6F
12/19 06:22, 6F
推
12/19 06:25, 7年前 , 7F
12/19 06:25, 7F
→
12/19 06:25, 7年前 , 8F
抱歉啊 寫錯一直改
12/19 06:25, 8F
推
12/19 08:28, 7年前 , 9F
G不是connect，不能帶e<=3v-6 而且應該是3/2v<=e<=
12/19 08:28, 9F
→
12/19 08:28, 7年前 , 10F
3v-6
12/19 08:28, 10F
→
12/19 10:15, 7年前 , 11F
G應該是connect 不然題目不會給min vertex cut=5
12/19 10:15, 11F
→
12/19 14:30, 7年前 , 12F
因為是k(G)=5 所以一定是connect 且每點degree 至少為5
12/19 14:30, 12F
推
12/19 16:46, 7年前 , 13F
抱歉～沒看清楚，直覺以為那代表components個數
12/19 16:46, 13F
→
12/19, , 14F
推c大，我寫出來也是那樣
12/19, 14F
16:46
→
12/19 20:49, 7年前 , 15F
請問c大為什麼每個點的degree至少為5？
12/19 20:49, 15F
※ 編輯: triumphant10 (1.164.1.40), 12/19/2018 20:49:59
→
12/19 23:13, 7年前 , 16F
如果有一點deg<=4 那把他連出去的vertex都拿掉即形成一個
12/19 23:13, 16F
→
12/19 23:13, 7年前 , 17F
cut 與題目條件矛盾 所以一定>=5
12/19 23:13, 17F
→
12/20 00:56, 7年前 , 18F
對齁，感謝anonimo !
12/20 00:56, 18F
→
12/20 01:02, 7年前 , 19F
請問 G的補集中，為什麼deg(v)=6 ?
12/20 01:02, 19F
→
12/20 01:10, 7年前 , 20F
喔~ 我知道了，是因為sum的deg(v) = 2e = 2*C12取2
12/20 01:10, 20F
→
12/20 01:13, 7年前 , 21F
2*12*11/2=132，132-60=72(補集)，72/12=6=deg(v)
12/20 01:13, 21F
→
12/20 08:01, 7年前 , 22F
可以這樣想 總node為12則每點最多11邊 G有5邊 那補圖就是6
12/20 08:01, 22F
→
12/20 08:01, 7年前 , 23F
了
12/20 08:01, 23F
→
12/20 11:39, 7年前 , 24F
c大這個方法更好! 謝謝!
12/20 11:39, 24F
‣ 更多 triumphant10 的文章
文章代碼(AID): #1S6Eyixb (Grad-ProbAsk)