[理工] [資演]清大106 8

[zaqxsw2230 (qianling)]

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://www.ptt.cc/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
→ MASAGA: 先回答第一個   k-plex定義是每點deg至少S-k
→ MASAGA: 所以如果不是k-plex 至少有一點deg<S-K
→ MASAGA: 然後其實我看不太懂你要問啥XD  我就解釋他的證法好了
→ MASAGA: 因為題目要證明K-plex S的子圖 S'也是K-plex
→ MASAGA: 所以就先假設S是k-plex 但S'不是k-plex
→ MASAGA: 如果結論跟假設矛盾 那假設就錯誤 代表S的子圖S'是kplex
→ MASAGA: 具體怎麼推就看圖吧 然後你畫的圖右邊是4plex不是1plex
→ zaqxsw2230: 我漏看at least，以為是最小的deg. 恰好為|s|-k
→ zaqxsw2230: 但是請問這樣的話為k-plex的圖 必也為(k+n)-plex 嗎 S
→ zaqxsw2230: 舉例題目S={a,b,c,d,e} 其induced graph 的min. deg=2
→ zaqxsw2230: 所以min. deg.>=|S|-k   (2>=5-3)  但是2>=5-4 所以也
→ zaqxsw2230: 是4-plex嗎
→ zaqxsw2230: 謝謝解釋
→ MASAGA: 應該沒錯  k-plex的k越大  所需degree就越小