[理工] 離散數學的證明題

看板Grad-ProbAsk作者 (yu12510 )時間5年前 (2018/12/23 00:28), 編輯推噓5(5推 0噓 14→)
留言19則, 5人參與, 5年前最新討論串1/1
大家好 Let S be a set of n points in the plane such that the distance between any two is at least one . Prove that there are at most 3n-3 pairs of points with distance exactly one. https://imgur.com/a/Z4WyGPV (附上原始題目) 請問看看有沒有大神可以證的出來或是提供點線索給小弟我 謝謝! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.7.151 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545496138.A.44C.html
推
12/23 00:57, 5年前 , 1F
幫推 作業好難都想不到QQ
12/23 00:57, 1F
→
12/23 01:03, 5年前 , 2F
目前這題只想到 如果把距離為1的邊都加上去行成一個新圖
12/23 01:03, 2F
→
12/23 01:03, 5年前 , 3F
可以證明它是planar graph
12/23 01:03, 3F
→
12/23 01:04, 5年前 , 4F
12/23 01:04, 4F
→
12/23 01:05, 5年前 , 5F
可是就只能證到有3n-6條edge(pair)而已
12/23 01:05, 5F
→
12/23 01:06, 5年前 , 6F
不知道3n-3是怎麼來的
12/23 01:06, 6F
→
12/23 01:08, 5年前 , 7F
還是這樣就算證明結束了??
12/23 01:08, 7F
推
12/23 01:13, 5年前 , 8F
這題跟 台大電機104的蠻像的，我看別人的解釋是用畫圓
12/23 01:13, 8F
→
12/23 01:14, 5年前 , 9F
但是這一題多減去3...
12/23 01:14, 9F
推
12/23 10:44, 5年前 , 10F
12/23 10:44, 10F
→
12/23 10:44, 5年前 , 11F
我用數學歸納證，有錯請指教
12/23 10:44, 11F
→
12/23 10:53, 5年前 , 12F
原來這裡都是修電機離散的XD
12/23 10:53, 12F
→
12/23 10:53, 5年前 , 13F
P大，我也是用數學歸納法去想
12/23 10:53, 13F
推
12/23 11:09, 5年前 , 14F
其實我是同時有修課也有要考試啦
12/23 11:09, 14F
→
12/23 11:10, 5年前 , 15F
p大的歸納法看起來怪怪的 n=k使用的假設和n=k+1證出來的
12/23 11:10, 15F
→
12/23 11:10, 5年前 , 16F
好像不一樣
12/23 11:10, 16F
推
12/24 21:50, 5年前 , 17F
有人可以說明一下作業第一題的3嗎QQ
12/24 21:50, 17F
→
12/24 22:15, 5年前 , 18F
把g1用矩陣表示 可以得到每個點的deg=4
12/24 22:15, 18F
→
12/24 22:16, 5年前 , 19F
所以去除4條邊後 c=1 or 2 就能帶公式了
12/24 22:16, 19F
‣ 更多 triumphant10 的文章
文章代碼(AID): #1S7cPAHC (Grad-ProbAsk)