四.实用的模型 允许在通信站之外的点连接,下图中的非站点网格结点 (共9×8-9=63个)称为“虚设站”。从这63个点中任 取k个(k=0,1,2,,63)与9个真站共同组成一个含(9+k)个 顶点的完备图,其最小生成树称为 Steiner树。有很 多个 Steiner树,权最小的称为最小 Steiner树。 结论:含n个真站的网络,其最小 Steiner树所 含的“虚设站”不超过(n2)个。 若用遍历法选取“虚设站”,则从n(n-1)中任取k 个,k=0,1(m-2),工作量是巨大的天文数字。 读书P181-P188四．实用的模型 允许在通信站之外的点连接，下图中的非站点网格结点 （共 98−9 = 63 个）称为“虚设站”。从这 63 个点中任 取 k 个(k=0,1,2,…,63)与 9 个真站共同组成一个含(9+k)个 顶点的完备图，其最小生成树称为 Steiner 树。有很 多个 Steiner 树，权最小的称为最小 Steiner 树。 结论：含 n 个真站的网络，其最小 Steiner 树所 含的“虚设站”不超过(n-2)个。 若用遍历法选取“虚设站”，则从 n(n-1)中任取 k 个，k=0,1,…,(n-2)，工作量是巨大的天文数字。 读书 P181----P188