[理工] 離散證明題

[triumphant10 (yu12510 )]

各位好

想問一下大神有沒有這些證明的頭緒

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
推 cks116: 第一題 寫得潦草 有錯提醒一下 https://i.imgur.com/bPrw7
→ cks116: iJ.jpg
→ cks116:  https://i.imgur.com/KSEOntB.jpg
→ DLHZ: 修網址 https://i.imgur.com/bPrw7iJ.jpg
→ cks116: 抱歉 匆忙看錯題目
→ cks116: 這才對 https://i.imgur.com/iFN3s3M.jpg
推 cks116: 更正 https://i.imgur.com/x3JxrRf.jpg
→ cks116: 抱歉啊 寫錯一直改
推 ponponjerry: G不是connect，不能帶e<=3v-6 而且應該是3/2v<=e<=
→ ponponjerry: 3v-6
→ anonimo: G應該是connect 不然題目不會給min vertex cut=5
→ cks116: 因為是k(G)=5 所以一定是connect 且每點degree 至少為5
推 ponponjerry: 抱歉～沒看清楚，直覺以為那代表components個數
→ ponponjerry: 推c大，我寫出來也是那樣
16:46
→ triumphant10: 請問c大為什麼每個點的degree至少為5？
※ 編輯: triumphant10 (1.164.1.40), 12/19/2018 20:49:59
→ anonimo: 如果有一點deg<=4 那把他連出去的vertex都拿掉即形成一個
→ anonimo: cut 與題目條件矛盾 所以一定>=5
→ triumphant10: 對齁，感謝anonimo !
→ triumphant10: 請問 G的補集中，為什麼deg(v)=6 ?
→ triumphant10: 喔~ 我知道了，是因為sum的deg(v) = 2e = 2*C12取2
→ triumphant10: 2*12*11/2=132，132-60=72(補集)，72/12=6=deg(v)
→ cks116: 可以這樣想 總node為12則每點最多11邊 G有5邊 那補圖就是6
→ cks116: 了
→ triumphant10: c大這個方法更好! 謝謝!