廣播時間

考慮在一個連通圖上從起始頂點 開始的廣播方案 ，該方案由一系列從 開始的並行呼叫組成。在每個時間步，每個知情節點（傳送者）最多可以呼叫一個不知情的鄰居（接收者），這對應於一個有向邊。這個過程會一直重複，直到網路中的每個頂點都被通知到，結果是一個以 的 生成樹，稱為起始頂點 的廣播樹。

從頂點 廣播到圖 中所有頂點所需的最少時間步數稱為頂點 的廣播時間，記為 。 中所有起始頂點中的最大廣播時間稱為 的廣播時間，記為 (Harutyunyan1 和 Li 2019)。

非連通圖 的廣播時間是其連通分量的廣播時間的最大值。