Research Space for Linear Algebra & Discrete Mathematics
如果 k(G)>2, 那麼隨便找 2 個component出來, 加邊把它們連起來, 這樣邊數必定會增加, 且還是可以保持不連通
不好意思~我問的不夠清楚我想問的是" 一個disconnected的圖,點數固定 且 每個component都是complete" 為啥k(G)=2邊數會是最多ex: k(G)=2邊數 多於 k(G)=3邊數
上面那張照片紅色(橘色)部分是我的問題
所以我的意思是假設這句話不成立, 以你畫的那張圖裡的右邊那個圖(稱它為G)為例, 假設 G 已為一個具有最多邊的disconnected graph, 我們將左邊那兩個component加邊使他們連在一起, 如此一來並不會導致右邊那個圖變連通 (因為component數變成2, 還是大於1) 且此時邊數一定會多於原本不連時的狀況, 這樣就矛盾了原本的 G 為具有最多邊的disconnected graph
謝謝強者助教~我懂了~~不知道一開始的回答是矛盾證法
張貼留言
6 則留言:
如果 k(G)>2, 那麼隨便找 2 個component出來, 加邊把它們連起來, 這樣邊數必定會增加, 且還是可以保持不連通
不好意思~我問的不夠清楚
我想問的是" 一個disconnected的圖,
點數固定 且 每個component都是
complete" 為啥k(G)=2邊數會是最多
ex: k(G)=2邊數 多於 k(G)=3邊數
上面那張照片紅色(橘色)部分是我的問題
所以我的意思是假設這句話不成立, 以你畫的那張圖裡的右邊那個圖(稱它為G)為例, 假設 G 已為一個具有最多邊的disconnected graph, 我們將左邊那兩個component加邊使他們連在一起, 如此一來並不會導致右邊那個圖變連通 (因為component數變成2, 還是大於1) 且此時邊數一定會多於原本不連時的狀況, 這樣就矛盾了原本的 G 為具有最多邊的disconnected graph
謝謝強者助教~我懂了~~不知道一開始的回答是矛盾證法
張貼留言