作者clonsey1314 (Clonsey)
看板Grad-ProbAsk
标题[理工] 离散 交大101 图论
时间Sat Dec 16 21:00:37 2017
What is the largest n so that the following assertion is always true?
Assertion:
Let G be a graph with 10 vertices in which there is at least one edge among
any three vertices. Then G must contain Kn, where Kn is the complete graph
with n vertices.
https://imgur.com/DEt2zUs
https://imgur.com/p8QrQcg
请问为甚麽解答一开始就这麽确定是K4, 然後就直接证是K4?
是要先用猜的吗? 还是有甚麽方法可以直接先判断是K4?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.161.228.154
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1513429239.A.DA6.html
※ 编辑: clonsey1314 (1.161.228.154), 12/16/2017 21:01:46
1F：→ TMDTMD2487: 我把它当作六个人必有三个人相认识或不互相认识的题目 12/16 21:54
2F：→ TMDTMD2487: 的一个延伸 12/16 21:55
3F：→ TMDTMD2487: 与x相邻的六个点必定有三个点连满或都没有连 12/16 21:55
4F：→ TMDTMD2487: 都没有连的话与题意不合所以会有三个连满的点 12/16 21:56
5F：→ TMDTMD2487: 我想步道别的方法XD 12/16 21:56
6F：→ TMDTMD2487: 解答一开始取deg(x)<=5 就是为了制造上面的情境我想 12/16 21:57
7F：→ TMDTMD2487: 10个点再扩大我猜也是这种方法做下去 12/16 21:57
8F：→ clonsey1314: 为什麽这麽肯定的取6个? 12/16 22:30
9F：推 sarsman: 这题我觉得交大超狠的，题目量已经多到很难做完了还出这 12/16 22:54
10F：→ sarsman: 种题目XDD 12/16 22:54
11F：→ sarsman: 三点必有一边，所以固定一点x考虑，与x不相连的点必能形 12/16 23:13
12F：→ sarsman: 成complete subgraph 12/16 23:13
13F：推 TMDTMD2487: 上述只有证明他前半部分讲得@@ 12/17 10:14
14F：→ TMDTMD2487: 六个就只是为了把那个很基本的题目延伸过来而已(六个 12/17 10:15
15F：→ TMDTMD2487: 人的那个 12/17 10:15
16F：→ TMDTMD2487: 不用担心这种东西交大应该考一次就换题目了 12/17 10:15