某些广播图的构作

1.引言 广播图G的广播方式见文,在讨论广播问题时,我们使用下述定义: 定义1 图G中某结点u的广播时间t(u)是完成以u为源结点的广播所需要的最少单位时间数。 定义2 图G的广播时间t(G)是指G中结点广播时间的最大值。即 定义3 若n阶广播图G满足t(G)=[logn],则称G为n阶合格广播图。 定义4 若n阶合格广播图G的任一真生成子图G′,有t(G′)】t(G)。