现在拟建造一个连接11个城市的铁路网络,要求任何2个城市或者直接可达或者间接可达。用每个结点表
现在拟建造一个连接11个城市的铁路网络，要求任何2个城市或者直接可达或者间接可达。用每个结点表示一个城市，2个结点之间边的权值表示2个城市之间直达铁路的造价，由此可得如图5-3所示的各城市之间的造价图。若要求设计的铁路网络总造价最小，则这个最小造价为(1)。这个问题相当于求解已知图的(2)。
A．266
B．268
C．271
D．273
正确答案：A解析：显然，这是求已知图的最小生成树的问题。含有n个顶点的连通图的生成树有n个顶点和n-1条边。对一个带权的图(网)，在一棵生成树中，各条边的权植之和称为这棵生成树的代价。其中代价最小的生成树称为最小代价生成树(简称最小生成树)。 MST性质：设G=(V,E)是一个连通网络，U是顶点集V的一个真子集。若(u,v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u,v)。 求连通的带权无向图的最小代价生成树的算法有普
词条内容仅供参考，如果您需要解决具体问题
（尤其在法律、医学等领域），建议您咨询相关领域专业人士。