[理工] 離散 圖論

[yahooyamgoog (安安唷)]

https://i.imgur.com/qBXjJy9.jpg

我想問的是

b選項為何不能用a選項的方法來做？

兩選項看起來是很相似的問題啊

在b選項的條件下

令G有k個component且k>1

則

|E| >= |V| - k

代入 |E| = 11, |V| = 6 不等式成立


如果換個數字那我該用哪個方法？

我有漏掉什麼嗎？謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.223.59 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577186131.A.F46.html
推 mistel: b是問你有沒有>1個components，但你直接假設有>k個compon
→ mistel: ents，那結果是當然有可能有 關鍵是第二題「可能」沒有兩
→ mistel: 個以上的分量圖
題目應是問這樣的敘述是否可能為真吧？
※ 編輯: yahooyamgoog (223.136.223.59 臺灣), 12/24/2019 19:40:21
推 mistel: 我看錯題目了，應該是就像題目寫的，當圖不連通時一定在2
→ mistel: 個components，一個components5個點，另一個components1
→ mistel: 個點，最大邊頂多10條
→ mistel: 你說的不等式是必要條件，當這個不等式成立不一定代表你
→ mistel: 的命題成立，第一題是：若p則q，非q則非p，所以q不成立，
→ mistel:  p也不成立
推 mistel: 至於不連通的圖在何時會達到最大的邊是可以證明的