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

看板Grad-ProbAsk作者 (qianling)時間5年前 (2020/01/24 19:38), 5年前編輯推噓0(0推 0噓 14→)
留言14則, 2人參與, 5年前最新討論串1/1
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
→
01/24 20:11, 5年前 , 1F
先回答第一個 k-plex定義是每點deg至少S-k
01/24 20:11, 1F
→
01/24 20:12, 5年前 , 2F
所以如果不是k-plex 至少有一點deg<S-K
01/24 20:12, 2F
→
01/24 20:16, 5年前 , 3F
然後其實我看不太懂你要問啥XD 我就解釋他的證法好了
01/24 20:16, 3F
→
01/24 20:16, 5年前 , 4F
因為題目要證明K-plex S的子圖 S'也是K-plex
01/24 20:16, 4F
→
01/24 20:18, 5年前 , 5F
所以就先假設S是k-plex 但S'不是k-plex
01/24 20:18, 5F
→
01/24 20:18, 5年前 , 6F
如果結論跟假設矛盾 那假設就錯誤 代表S的子圖S'是kplex
01/24 20:18, 6F
→
01/24 20:21, 5年前 , 7F
具體怎麼推就看圖吧 然後你畫的圖右邊是4plex不是1plex
01/24 20:21, 7F
→
01/24 21:11, 5年前 , 8F
我漏看at least，以為是最小的deg. 恰好為|s|-k
01/24 21:11, 8F
→
01/24 21:12, 5年前 , 9F
但是請問這樣的話為k-plex的圖 必也為(k+n)-plex 嗎 S
01/24 21:12, 9F
→
01/24 21:14, 5年前 , 10F
舉例題目S={a,b,c,d,e} 其induced graph 的min. deg=2
01/24 21:14, 10F
→
01/24 21:16, 5年前 , 11F
所以min. deg.>=|S|-k (2>=5-3) 但是2>=5-4 所以也
01/24 21:16, 11F
→
01/24 21:16, 5年前 , 12F
是4-plex嗎
01/24 21:16, 12F
→
01/24 21:24, 5年前 , 13F
謝謝解釋
01/24 21:24, 13F
→
01/24 23:46, 5年前 , 14F
應該沒錯 k-plex的k越大 所需degree就越小
01/24 23:46, 14F
‣ 更多 zaqxsw2230 的文章
文章代碼(AID): #1UAjSzDZ (Grad-ProbAsk)