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