高分悬赏：NOIP2005:平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1).……平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1).以这五点作为完全图G的顶点,每两点之间的直线距离是图G中对

Question

高分悬赏：NOIP2005:平面上有五个点 A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1).……
平面上有五个点 A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1).以这五点作为完全图 G 的顶点, 每两点之间的直线距离是图 G 中对应边的权值.以下哪条边不是图 G 的最小生成树中 的边（ ）.
A. AD B. BD C. CD D. DE E. EA
望解答具体过程,希望能够详细些,是否加悬赏就看你讲得清不清楚,越详细越好.
1.什么是最小生成树
2.什么是完全图
3.什么叫权值
4.什么是图
5.……
希望详细解答诸如此类问题,定会加悬赏.
一下子解答不了这么多也没关系,帮帮我吧!

Answer 1

答案是D
【详解】其实题目的意思说白了就是让你选几个点连接,使任意两点都能通,且这几条线的长度之和最短,试一下就知道是连接AD、BD、CD、EA选择题试一下就可以了,（上机编程的话学一下Prim算法和Kruskal算法）
【最小生成树】一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图联通的最少的边.
【完全图】完全图是每对顶点之间都恰连有一条边的图.
【权值】权值就是定义的路径上面的值.可以这样理解为节点间的距离.
想要详细研究图的话最好买本书看,有的题目是非常难的.