作者zaqxsw2230 (qianling)
看板Grad-ProbAsk
標題[理工] [資演]清大106 8
時間Fri Jan 24 19:38:35 2020
https://i.imgur.com/3ffo8bh.jpg
https://i.imgur.com/M0y46H6.jpg
https://i.imgur.com/xgVcbzS.jpg
假設S’不為k-plex 我們已知H’的min. deg.<=H的min. deg.
想請問第三張圖的（2）第四句話說 :
H' 的min. deg.<|s'|-k 是為什麼
因為H' 可以為 (k+n)-plex 這樣一來H’的min. deg= |s'|-(k+n)> |s'|-k
另外最後一句話老師的意思是說H' 的min. deg. node必為H的min. deg node嗎？ 我覺得老師最後
一句話是要說存在一點 v 為H' min. deg. node其在H的deg. 小於H的min. deg. 故矛盾
第二張圖是我畫的G 設S就是所有G的node 然後取S’為右圖 明顯不存在4-plex 不是嗎
不好意思問題比較多
謝謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.205.231 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579865917.A.363.html
※ 編輯: zaqxsw2230 (114.137.205.231 臺灣), 01/24/2020 19:42:45
※ 編輯: zaqxsw2230 (114.137.205.231 臺灣), 01/24/2020 19:44:07
※ 編輯: zaqxsw2230 (114.137.205.231 臺灣), 01/24/2020 19:46:36
1F：→ MASAGA: 先回答第一個 k-plex定義是每點deg至少S-k 01/24 20:11
2F：→ MASAGA: 所以如果不是k-plex 至少有一點deg<S-K 01/24 20:12
3F：→ MASAGA: 然後其實我看不太懂你要問啥XD 我就解釋他的證法好了 01/24 20:16
4F：→ MASAGA: 因為題目要證明K-plex S的子圖 S'也是K-plex 01/24 20:16
5F：→ MASAGA: 所以就先假設S是k-plex 但S'不是k-plex 01/24 20:18
6F：→ MASAGA: 如果結論跟假設矛盾 那假設就錯誤 代表S的子圖S'是kplex 01/24 20:18
7F：→ MASAGA: 具體怎麼推就看圖吧 然後你畫的圖右邊是4plex不是1plex 01/24 20:21
8F：→ zaqxsw2230: 我漏看at least，以為是最小的deg. 恰好為|s|-k 01/24 21:11
9F：→ zaqxsw2230: 但是請問這樣的話為k-plex的圖 必也為(k+n)-plex 嗎 S 01/24 21:12
10F：→ zaqxsw2230: 舉例題目S={a,b,c,d,e} 其induced graph 的min. deg=2 01/24 21:14
11F：→ zaqxsw2230: 所以min. deg.>=|S|-k (2>=5-3) 但是2>=5-4 所以也 01/24 21:16
12F：→ zaqxsw2230: 是4-plex嗎 01/24 21:16
13F：→ zaqxsw2230: 謝謝解釋 01/24 21:24
14F：→ MASAGA: 應該沒錯 k-plex的k越大 所需degree就越小 01/24 23:46