如何做到连通的代价最小

摘要

在本刊第九期我们讨论了如何判断一个图(或者网络)是否连通的问题。这一期我们换个角度,研究如何让把一些节点连通起来的代价最小。可以想象这些节点是一些城市,它们之间的直飞航线是边,代价则是在它们之间开辟直航的成本。