[理工] 離散 圖論

看板Grad-ProbAsk作者 (zrae)時間10年前 (2015/12/05 15:40), 10年前編輯推噓6(6推 0噓 13→)
留言19則, 3人參與, 最新討論串3/16 (看更多)
http://i.imgur.com/anFWdFN.jpg
這是小黃 離散 課本6-24頁的題目 看不太懂 解答這句話 欲證k>(1/2)*(n-1)*(n-2）,則G為 disconnected graph 後面解答也有寫到 很顯然 當r=2 最多邊數k=....... 這邊也不太懂 qq 麻煩各位鄉民給點提示～_～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.17.63 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1449301237.A.6DB.html ※ 編輯: keke0421 (39.10.17.63), 12/05/2015 15:41:41
推
12/05 16:06, , 1F
N點不連通則一定有兩個分量圖，而邊最多就是把點分
12/05 16:06, 1F
→
12/05 16:06, , 2F
成1 和 n-1 而k(n-1)的邊數為c(n-1,2) k>k(n-1)矛盾
12/05 16:06, 2F
→
12/05 16:06, , 3F
故為連通
12/05 16:06, 3F
推
12/05 17:18, , 4F
“欲證若k>，，，，” ←這句話只是把題目抄下來而已
12/05 17:18, 4F
推
12/05 17:20, , 5F
然後他就開始用 q→ p 開始証
12/05 17:20, 5F
→
12/05 17:21, , 6F
～q → ～p
12/05 17:21, 6F
→
12/05 17:26, , 7F
不對 他是用矛盾証法 sorry～
12/05 17:26, 7F
推
12/05 20:42, , 8F
你的第一個疑問 因為他是用矛盾證法去證
12/05 20:42, 8F
→
12/05 20:43, , 9F
題目是證連通 他就假設不連通
12/05 20:43, 9F
→
12/05 20:44, , 10F
如果證到有矛盾的情況 就代表假設(不連通)是錯的
12/05 20:44, 10F
推
12/05 21:02, , 11F
然後為什麼會是r=2的時候有最多的邊
12/05 21:02, 11F
推
12/05 23:00, , 12F
嗚嗚剛剛手機沒電
12/05 23:00, 12F
→
12/05 23:00, , 13F
有最多邊卻不連通的情況是 當你把n個點分兩堆
12/05 23:00, 13F
→
12/05 23:01, , 14F
一堆只有一點 一堆n-1個點
12/05 23:01, 14F
→
12/05 23:02, , 15F
當這n-1個點形成complete graph的時候
12/05 23:02, 15F
→
12/05 23:03, , 16F
你此時的邊數就是題目那個(1/2)(n-1)(n-2)
12/05 23:03, 16F
→
12/05 23:04, , 17F
這時候如果你還要再加邊上去 必定會把另一邊那個孤立點
12/05 23:04, 17F
→
12/05 23:04, , 18F
連向這個comple gragh 那就會連通了
12/05 23:04, 18F
→
12/05 23:05, , 19F
這就是為什麼他說在不連通的情況下r=2會具最大邊數
12/05 23:05, 19F
‣ 更多 keke0421 的文章
文章代碼(AID): #1MOfJrRR (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 3 之 16 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共16篇)
‣ 更多 keke0421 的文章
文章代碼(AID): #1MOfJrRR (Grad-ProbAsk)