作者jack0602 (21)(21)
看板Grad-ProbAsk
標題Re: [理工] 幾題離散
時間Wed Nov 20 15:48:42 2013
102年第5題個人想到的證法 不確定正不正確 歡迎討論看看
假設s到t的任兩條path皆沒有共同的vertex
已知任何從s到t的path至少含floor(n/2)+1個edges
所以任何從s到t的path中 不包含s和t的vertices至少有floor(n/2)個
令P1和P2為兩條s到t的path 因P1和P2沒有共同的vertex
G的vertices總數為(P1不含s和t的vertices數)+(P2不含s和t的vertices數)+(s和t)
因此G總共有floor(n/2)+floor(n/2)+2個vertices
若n是奇數 floor(n/2)+floor(n/2)+2=(n-1)+2=n+1>n
與已知G有n vertices矛盾
若n是偶數 floor(n/2)+floor(n/2)+2=n+2>n
與已知G有n vertices矛盾
故假設錯誤 即s到t的任兩條path皆有共同的vertex
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.67.81
推 LOVEEE5566:感謝不過我還是有點疑惑在share a vertex那邊 11/21 11:51
→ LOVEEE5566:不知道是不是只要有交點即可還是只能有一個交點@@ 11/21 11:53
題目是寫share "a" common vertex 我個人是傾向於只能有一個交點
另外 由證明可看出n似乎必須為奇數?
※ 編輯: jack0602 來自: 140.113.67.81 (11/21 20:58)
推 LOVEEE5566:感覺應該是對的如果照你證的這樣 11/25 19:29
推 LOVEEE5566:但是如果用畫的 假設有12345 五個點 如果我走1345跟 11/25 19:31
推 LOVEEE5566:12345 那不就有兩個交點了！？題目說任意兩條 11/25 19:32
推 LOVEEE5566:不知到我有沒有漏掉什麼QQ 11/25 19:35