要用最少费用建设一条公路网，将五个城市连接起来，使它们可以相互到

参考答案：A——(4)，B——(5)，C——(3)，D——(1)，E——(2)

正确答案：C
解析：本题是一个典型的图论算法的应用问题。既可以看作赋权简单连通无向图的单源问题进行求解，也可以用两结点间最短距离算法进行求解。
  采用单源问题的迪克斯特拉(E．W Dijkstra)算法求解。
  将题图中未标记的结点进行标记，得到下图：
 
  令S={s}，T={a，b，c，d，e，f，S，h，i，t}，
  D(s)=0，D(a)=25，D(b)=21，D(c)=+∞， D(d)=+∞，D(e)=+∞，D(f)=+∞，
  D(g)=+∞， D(h)=+∞， D(i)=+∞， D(t)=+∞。
  因为D(b)=21是T中最小的D值，选x=b，令S ←S∪{X}={s,b}。
  令T ←T-{X}={a，d，c，d，e，f，g，h，i，t},然后计算：
  D(a)=min(25，21+23)=25，D(c)=min(+∞，21+20)=41，D(d)=min(+∞，21+25)=46，
  D(e)=min(+∞，+∞)=+∞，D(f)=min(+∞，+∞)=+∞，D(g)=min(+∞，+∞)= +∞，
  D(h)=min(+∞，+∞)=+∞，D(i)=min(+∞，+∞)=+∞，D(t)=min(+∞，+∞)= +∞。
  如此类推，直到T=终止，整个过程概括于表如下：
 
D(t)=81，所以城市s到城市t的最短距离为81。

参考答案：边缘连接

正确答案：将城市作为结点将连接两个城市的公路作为边则该问题等价于证明一个具有n个结点k条边的简单无向图G是连通图。当n=2时结论显然成立以下证明n＞2时结论也成立。 假设G不连通则可将G中的结点集V分为两个子集V1和V2它们．满足V1∪V2=VV1∩V2≠并且V1中的任何结点与V2中的任何结点均不连通。设由V1生成的G的子图G1中有n1个结点k1条边由V2生成的G的子图G2中有n2个结点k2条边则n1+n2=nk1+k2＝k。由于G是简单无向图因此G1和G2也是简单无向图从而有 k1≤1/2 n1(n1-1)k2≤1/2 n2(n2-1) 于是 k=k1+k2≤1/2 n1(n1-1)+1/2 n2(n2-1) ① 又 k＞1/2(n-1)(n-2)=1/2(n1+n2-1)(n1+n2-2) ② 由于n＞2因此n1和n2至少有一个大于等于2不妨设n12．由②得 k＞1/2(n1+n2-1)(n1+n2-2)=1/2 n1(n1+n2-2)+1/2(n2-1)(n1+n2-2)1/2 n1(n1-1)+1/2 n2(n2-1) 这与①式矛盾故G是连通图。
将城市作为结点，将连接两个城市的公路作为边，则该问题等价于证明一个具有n个结点k条边的简单无向图G是连通图。当n=2时，结论显然成立，以下证明n＞2时结论也成立。 假设G不连通，则可将G中的结点集V分为两个子集V1和V2，它们．满足V1∪V2=V，V1∩V2≠，并且V1中的任何结点与V2中的任何结点均不连通。设由V1生成的G的子图G1中有n1个结点k1条边，由V2生成的G的子图G2中有n2个结点k2条边，则n1+n2=n，k1+k2＝k。由于G是简单无向图，因此G1和G2也是简单无向图，从而有 k1≤1/2 n1(n1-1)，k2≤1/2 n2(n2-1) 于是 k=k1+k2≤1/2 n1(n1-1)+1/2 n2(n2-1) ① 又 k＞1/2(n-1)(n-2)=1/2(n1+n2-1)(n1+n2-2) ② 由于n＞2，因此n1和n2至少有一个大于等于2，不妨设n12．由②得 k＞1/2(n1+n2-1)(n1+n2-2)=1/2 n1(n1+n2-2)+1/2(n2-1)(n1+n2-2)1/2 n1(n1-1)+1/2 n2(n2-1) 这与①式矛盾，故G是连通图。

正确答案：见解析
城市范围内将多个校园网互联构成城域网。多个城域网又通过路由器与光纤接入作为国家级或区域主干网的广域网。

正确答案：B