数据结构,算法分析,NN/MST
图的最大度(the maximum degree of a graph) is the maximum number of edges incident to a vertex in the graph.
试证明:
1.在平面点集中的Nearest Neighour (NN)图的度(degree)最多为6
2.在平面点集中的Euclidean minimum weight spanning tree (MST)的度最多为6
大家有什么思路?
[解决办法]
没学过图论，不过个人猜测Nearest Neighbour 图是不是指这样的一个图：该图中每一个结点都只和离它距离最近的点有连接线？
若是，对于该图中任意一个结点O，与点O有连接线的点集{A1,...,An}必然处于以点O为球心的球面上。对于平面图形来讲，这些点则是处于以点O为圆心的圆上。当{A1,...,An}的数量>6时，必然存在其中的两个点Ai和Aj，它们与点O的连线的夹角<60°。这样一来，Ai和Aj之间的距离就比Ai到O之间的距离要短，因此Ai和O之间就不应该有连线，与假设相矛盾，因此NN图的最大度<=6。NN度=6的一个实例可以设想为有7个点O,A1,...,A6，其中O为中心，A1,...,A6分布在以O为圆心的圆上面，而且任意两个相邻的Ai, Aj的圆心角均为60°（即相邻的Ai,Aj与O构成了等边三角形）。
第2题MST不知道是什么，哪位大大可以帮忙解释一下。
[解决办法]
查了一下那个网址，生成树是由原始图生成的一个Tree，其特点是由图中的一个结点遍历到图中所有其它结点。最小生成树MST则是指路径权重和最小的生成树。而LZ的题目使用的则是 欧几里德MST。顾名思义，欧几里德MST是将2个结点之间的平面距离视作权重，不知道这个猜测对不对。
若上述猜测正确的话
==============================================================================
反证法：
对于MST中某一节点O来说，假设它的度>6，即O下引出了{a1,...,an|n>6}个子节点。
现在在平面坐标系中画出O以及a1,...,an这n+1个点。
由于该MST是欧几里德MST，因此各个节点连线的权重就是节点之间的直线距离。
现在将O分别连接到a1,...,an这n个点。
和前面讨论的一样，由于n>6，因此必存在两个ai, aj，使得它们与O的连线的夹角<60度。
将找到的ai简写为A,aj简写为B，可写作角AOB<60°。
这里有两种情况：
1, AOB三点共线。在此情况下，或者是A处于线段OB中间，或者是B处于线段OA中间。不失一般的，假定A处于线段OB中间。这时，很显然的有长度AB>OB，因此在MST图上，B应该是A的子节点，而不是O的子节点。
2. AOB三点不共线。在此情况下，AOB将构成一个三角形，其中的∠AOB < 60°。由于三角形内角和为180°，因此必定有某一个角>60°，不失一般的，假设∠ABO > 60°。这时，自然地有∠ABO>∠AOB。根据三角形大角对大边的定理，边AO>边AB。因此，将A放到B下面所构造的树必将A放在O下面的树具备更低的权重和。这与题设相矛盾。
证毕
