作为一种新的网路拓扑结构，组合星图日趋受到重视，其不仅保留了星图小直径、高连通度、高容错度、点对称、层次结构和度较低等特点，同时克服了星图增量因子较大的弊端(n维星图有n!个结点，相同维数的组合星图有n!/(n-k)!个结点)。对于组合星图的研究，已经取得大量成果：拓扑性质、容错问题、嵌入性、广播路由算法等。 广播是一个网络拓扑最基本的功能，设计行之有效的组合星图的广播算法能在很大程度上提高处理器之间的通信性能，避免通信瓶颈问题。广播问题可以划分为一对多广播和多对多广播。结点的通信模式可以划分为单点模式和多点模式。一般地，在广播问题中涉及两类时间：初始化链路时间和数据传输时间。在基于传统的数据包存储转发的广播问题中，广播一个具有b位数据的数据包耗时为T<,s>+b*Tc，其中，T<,s>为初始化链路的时间，T<,c>为广播一位数据的延时。特别地，初始化链路的时间T<,s>在实时系统中扮演着非常重要的角色；当广播的数据包很大时，数据延时T<,c>是不容忽视的。 树结构由于在大规模并行应用中取得了商业成功而受到普遍关注，其中，生成树是用于解决通信问题和广播问题的重要工具。基于多生成树的星图的广播算法、基于多生成树的超立方体的广播算法和基于多生成树的排列图的广播算法均已提出并取得较优的广播效率。 本文旨在利用单生成树和多生成树解决多点模式和单点模式下的组合星图的一对多和多对多广播问题。 与利用拓扑结构的层次结构构造生成树不同，本文着眼于组合星图的最短路由规则，依此规则得到的单生成树具有最优的高度，由于基于生成树的广播算法的效率很大程度上依赖于生成树的高度，故基于单生成树的组合星图的一对多广播和多对多广播在多点模式下取得近似最优的初始化链路时间，单点模式下取得近似最优的初始化链路时间和数据传输时间。 本文首次提出组合星图的多生成树，并证明在组合星图中同时嵌入n-1棵生成树的可能性。基于多生成树的组合星图的一对多广播和多对多广播在多点和单点模式下均取得近似最优的数据传输时间。