广播时间

考虑在一个连通图上从起始顶点 开始的广播方案 ，该方案由一系列从 开始的并行呼叫组成。在每个时间步，每个知情节点（发送者）最多可以呼叫一个不知情的邻居（接收者），这对应于一个有向边。这个过程会一直重复，直到网络中的每个顶点都被通知到，结果是一个以 的 生成树，称为起始顶点 的广播树。

从顶点 广播到图 中所有顶点所需的最少时间步数称为顶点 的广播时间，记为 。 中所有起始顶点中的最大广播时间称为 的广播时间，记为 (Harutyunyan1 和 Li 2019)。

非连通图 的广播时间是其连通分量的广播时间的最大值。