[離散] 證明題

看板Math作者 (yu12510 )時間7年前 (2018/12/23 00:24), 編輯推噓0(0推 0噓 9→)
留言9則, 3人參與, 7年前最新討論串1/1
大家好 請問看看有沒有大神可以解決這題證明題 看起來很簡單，可是我卻想不到下手點 https://imgur.com/a/VANsS1V 這裡的k(G)是指: The size of the smallest vertex cut 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.7.151 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1545495853.A.E26.html
→
12/23 00:29, 7年前 , 1F
n是啥？
12/23 00:29, 1F
→
12/23 10:49, 7年前 , 2F
應該是vertices
12/23 10:49, 2F
→
12/24 00:44, 7年前 , 3F
n 應該是 vertices 個數
12/24 00:44, 3F
→
12/24 00:45, 7年前 , 4F
path 相對於 vertex cut 好操作, 所以先假設能找到
12/24 00:45, 4F
→
12/24 00:46, 7年前 , 5F
最長的 path 長度只有 2κ(G)-1 (那個不是 k)
12/24 00:46, 5F
→
12/24 00:48, 7年前 , 6F
再考慮這 path 有哪些頂點與 path 以外的頂點相連
12/24 00:48, 6F
→
12/24 00:49, 7年前 , 7F
其中必定有兩個相鄰的頂點有外連的邊
12/24 00:49, 7F
→
12/24 00:49, 7年前 , 8F
再想辦法把 path 弄得更長就好了
12/24 00:49, 8F
→
12/24 00:53, 7年前 , 9F
上面說的有瑕疵, 只能說最長的 path 長度 < 2κ(G)
12/24 00:53, 9F
‣ 更多 triumphant10 的文章
文章代碼(AID): #1S7cKjuc (Math)