作者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/cn.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