试证明n个顶点的完全图，在每个顶点之间的路径最多为：

设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min(i).

(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:

式中,a(u,v)是边(u,v)的费用.

(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.

设G是一个有n个顶点的有向图,从顶点i发出的边的最大费用记为max(i).

(1)证明旅行售货员回路的费用不超过.

(2)在旅行售货员问题的回溯法中,用上面的界作为bestc的初始值,重写该算法,并尽可能地简化代码.

A、无向完全图

B、无向连通图

C、无向强连通图

D、无向树图

A.n

B.n(n-1)

C.n(n+1)

D.n²

A、n*(n-1)/2

B、n*(n+1)/2

C、n*(n-1)

D、n*(n+1)

给定n个小区之问的交通图，若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值wij表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院，试问这家医院应建在哪个小区，才能使距离医院最远的小区到医院的路程尽可能缩短?试设计一个算法解决上述问题.