作者triumphant10 (yu12510 )
看板Grad-ProbAsk
标题[理工] 离散数学的证明题
时间Sun Dec 23 00:28:55 2018
大家好
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1545496138.A.44C.html
1F：推 Leaving: 帮推 作业好难都想不到QQ 12/23 00:57
2F：→ Leaving: 目前这题只想到 如果把距离为1的边都加上去行成一个新图 12/23 01:03
3F：→ Leaving: 可以证明它是planar graph 12/23 01:03
5F：→ Leaving: 可是就只能证到有3n-6条edge(pair)而已 12/23 01:05
6F：→ Leaving: 不知道3n-3是怎麽来的 12/23 01:06
7F：→ Leaving: 还是这样就算证明结束了?? 12/23 01:08
8F：推 eggy1018: 这题跟 台大电机104的蛮像的，我看别人的解释是用画圆 12/23 01:13
9F：→ eggy1018: 但是这一题多减去3... 12/23 01:14
11F：→ ponponjerry: 我用数学归纳证，有错请指教 12/23 10:44
12F：→ triumphant10: 原来这里都是修电机离散的XD 12/23 10:53
13F：→ triumphant10: P大，我也是用数学归纳法去想 12/23 10:53
14F：推 Leaving: 其实我是同时有修课也有要考试啦 12/23 11:09
15F：→ Leaving: p大的归纳法看起来怪怪的 n=k使用的假设和n=k+1证出来的 12/23 11:10
16F：→ Leaving: 好像不一样 12/23 11:10
17F：推 zqAI3yGOAT: 有人可以说明一下作业第一题的3吗QQ 12/24 21:50
18F：→ Leaving: 把g1用矩阵表示 可以得到每个点的deg=4 12/24 22:15
19F：→ Leaving: 所以去除4条边後 c=1 or 2 就能带公式了 12/24 22:16