离散数学-图论，求解

来源：百度知道 编辑：UC知道 时间：2024/09/21 19:33:45
离开学校太久了，遇到一个证明题不会做。麻烦大家帮帮忙给出解，感谢
设S={X1;X2;X3;X4......Xn}是在平面上的一组点，两两之间的距离不小于1（即最小距离为1），证明：S中间距为1的点对数据不超过3n.

只要证明，在S中任取一个点Xi，S中与之相距为1的点不超过6个即可。
这个很容易，用Dirichlet的抽屉原理就可以了。以Xi为圆心做半径为1的圆。用3条直径将这个圆等分成6个60度的扇形，使得S中没有点落在这3条直径上(因为S有限，通过旋转显然可以做到)。如果与Xi距离为1的点至少有7个，那么至少有两个落在同一个扇形的弧上，它们之间的距离小于1，矛盾。