通讯网络中极小费用生成树的一种算法  

An Algorithm of the Minimal Cost Spanning Tree about Communication Network

作　　者：安建业[1] 于义良[1] 朱建华[2] 

机构地区：[1]天津商业大学理学院,天津300134 [2]军械工程学院基础部,河北石家庄050003

出　　处：《数学的实践与认识》2007年第17期89-93,共5页Mathematics in Practice and Theory

基　　金：天津商学院青年科研培育基金(040117)

摘　　要：针对具有n个通讯站的局域网络,运用增加或调整虚设站的方法,给出一种在混合距离下的极小费用生成树的算法.并就MCM91问题B,求出了极小费用生成树,其总费用小于美国马里兰州里斯勃来莱州立大学数学科学系B.A.Fusaro所提供的论文中的费用.Using the method of increasing or adjusting imaginary stations, a kind of minimal cost spanning tree＇s algorithm is obtained to the n communication stations under the mixed distance. So far as MCMgl question B, we have found its minimum cost spanning tree, and its total cost is little than the cost which is given by B. A. Fusaro mathematical department of Shalisibelai university in Mulilan state USA.

关 键 词：通讯网络 最短路径生成树 “棋盘”距离 虚设站 极小费用生成树 

分 类 号：O157.6[理学—数学]