一、 改革「擊鼓傳花」遊戲

進過學堂的人都玩過擊鼓傳花的遊戲: 一群人圍坐成一個大圈, 隨著鼓聲響起, 一朵大紅花沿著反時針方向 (或順時針方向) 從一個人的手中, 傳到另一個人的手中。 當鼓聲嘎然停止時, 花留在誰的手上, 誰就該表演一個節目, 至於是唱歌, 還是跳舞, 就請自便。

節目表演完後, 鼓聲繼續響起, 大紅花繼續前進, 從一個人的手中又傳到另一個人的手中, 如此繼續, 花仍是一朵, 但個人表演的節目可以無數, 足足可湊成一個晚會。

當今時代, 言必稱改革。讓我們也來改革一下「擊鼓傳花」。

讓這群人圍坐成兩個相連的圈 (圖 1) , 隨著鼓聲響起, 一朵大紅花仍沿著反時針方向從一個人的手中傳到另一個人的手中。

當傳到分岔點 (如圖 1中的 $u$ 點) 往下傳時, 把一朵大紅花拆開成兩朵, 分別傳給兩個圈中的下一個人。 若紅花在傳遞時, 恰好在某一個點匯合 (如圖1中的 $v$ 點) , 則把兩朵花合成一朵。 按此規則往下傳遞, $\cdots\cdots$, 當鼓聲嘎然而止, 手上拿著花的人 (可能是一位, 也可能是多位) 就該表演節目了。

改革後的擊鼓傳花的一大優點是, 隨著鼓聲不斷響起, 傳遞的花越來越多。 不僅場面壯觀, 而且表演也可由獨唱

變成小組唱, 由獨舞變成集體舞。 如果我們有意識地調整兩個圈的人數, 如圖 1中圈 $xuyv$, 和圈 $xuzv$ 的人數分別說為 $a$ 和 $b$ 。 若 $a$, $b$ 互素, 簡記為 $(a, b)=1$, 則當鼓聲響下去, 必然有一個時刻, 每一個人手中都拿著紅花。 當鼓聲停止時, 全體參加都要合演一個節目, 想想看, 這是多麼完美的謝幕。

二、 原來是一個通訊系統

我們手上的雜誌是 $\langle\!\langle$數學傳播$\rangle\!\rangle$ 而不是 $\langle\!\langle$紅花傳播$\rangle\!\rangle$, 因此, 我們還應該走回正道, 從遊戲到數學。

我們有「閒心」去想到改革「擊鼓傳花」的遊戲, 完全是因為一個稱為非記憶通訊系統 (memoryless communication system) 的數學模型。 一個通訊系統的模型就是一個網絡, 或帶 $n$ 個頂點的有向圖 $D$ (見文獻 )。 假設在時間 $t=0$ 時, $D$ 中的 $k$ 個頂點 $(1\le k\le n)$ 掌握著各自不同的信息。 當 $t=1$ (即傳遞 1次) 時, 每個頂點把掌握的信息傳遞給相鄰的頂點, 而自己卻失掉 (忘記了) 這個信息。 當然, 它可以同時接收來自鄰點的信息。這個系統用此方法運作, 稱為非記憶通訊系統 $(MCS)$。

回過頭來, 看看我們改革了的擊鼓傳花, 把圖 1看成一個網絡。它就是一個 $k=1$ 的 $MCS$。

正如不是圖 1的任何一種排圈方法都可以保證將來每人手中都有一朵花, (讀者可以嘗試, 當 $a=10$, $b=6$ 時, 是不可能演全體大合唱的), 不是任何 $MCS$ 網絡都可以使初始的 $k$ 個信息傳遍每個頂點的。 但是, 當 $D$ 是本原有向圖時 (見文獻 ) 可以保證至某一個時刻, $D$ 的每個頂點都可掌握原來的 $k$ 個信息。

如文 所述, 本原有向圖就是一個強連通圖 (任兩點都有路到達) , 且不同的圈長的最大公約數為 1的圖。

在圖 1中, 我們令 $(a, b)=1$, 就是保證 $MCS$ 的本原性。

一個自然的問題接踵而來: 對於某個 $MCS$ 的本原有向圖 $D$, 使每個頂點掌握原來的 $k$ 個信息, 最短的時間是多少?

我們考慮簡單的 $k=1$ 的情況, 也就是:

在改革的擊鼓傳花遊戲中, 圖 1的 $D$ 中, 當第一聲鼓響起後, 至少經過多少步傳遞, 每個人手中都有一朵紅花?

我們知道一個網絡可以與一個 $(0, 1)$ 矩陣一一對應 (見文獻 ) , 讓我們用矩陣刻劃上述問題的數學本質。

不失一般性, 把圖 1的 $D_1$ 簡化為圖 2的一個 6階有向圖 $D_2$。

$D_2$ 的鄰接矩陣為

$$ \hskip -5cm A = \left ( \begin{array}{cccccc} 0 & ~0 & ~0 & ~0 & ~1 & ~1 \\ 1 & ~0 & ~0 & ~0 & ~0 & ~0 \\ 0 & ~1 & ~0 & ~0 & ~0 & ~0 \\ 0 & ~0 & ~1 & ~0 & ~0 & ~0 \\ 0 & ~0 & ~0 & ~1 & ~0 & ~0 \\ 0 & ~0 & ~0 & ~0 & ~1 & ~0 \end{array} \right ) $$

在布爾運算下, 設 $A^k=(a_{ij}^{(k)})$, 則 $a_{ij}^{(k)}=1$ 當且僅當從 $i$ 到 $j$ 有長為 $k$ 的途徑 (walk), 於是上述問題便是求使 $A^k$ 有一列全 1的最小的 $k$。(這裏, 我們定義矩陣的橫行為列)

試運算 \begin{eqnarray*} && A^2 = \left ( \begin{array}{cccccc} 0 & ~0 & ~0 & ~1 & ~1 & ~0 \\ 0 & ~0 & ~0 & ~0 & ~1 & ~1 \\ 1 & ~0 & ~0 & ~0 & ~0 & ~0 \\ 0 & ~1 & ~0 & ~0 & ~0 & ~0 \\ 0 & ~0 & ~1 & ~0 & ~0 & ~0 \\ 0 & ~0 & ~0 & ~1 & ~0 & ~0 \end{array} \right ) \quad A^3 = \left ( \begin{array}{cccccc} 0 & ~0 & ~1 & ~1 & ~0 & ~0 \\ 0 & ~0 & ~0 & ~1 & ~1 & ~0 \\ 0 & ~0 & ~0 & ~0 & ~1 & ~1 \\ 1 & ~0 & ~0 & ~0 & ~0 & ~0 \\ 0 & ~1 & ~0 & ~0 & ~0 & ~0 \\ 0 & ~0 & ~1 & ~0 & ~0 & ~0 \end{array} \right ) ~\cdots\cdots~ A^{20} = \left ( \begin{array}{cccccc} 1 & ~1 & ~1 & ~1 & ~1 & ~0 \\ 0 & ~1 & ~1 & ~1 & ~1 & ~1 \\ 1 & ~0 & ~1 & ~1 & ~1 & ~1 \\ 1 & ~1 & ~0 & ~1 & ~1 & ~1 \\ 1 & ~1 & ~1 & ~0 & ~1 & ~1 \\ 1 & ~1 & ~1 & ~1 & ~0 & ~0 \end{array} \right ) \\ && A^{21} = \left ( \begin{array}{cccc} 1 & ~1 & ~\cdots & ~1 \\ & ~\cdots & ~\cdots & \\ 0 & ~0 & ~\cdots & ~0 \end{array} \right ) \quad A^{22} = \left ( \begin{array}{cccc} 1 & ~1 & ~\cdots & ~1 \\ 1 & ~1 & ~\cdots & ~1 \\ & ~\cdots & ~\cdots & \end{array} \right ) \quad A^{23}, \quad A^{24}, \\ && A^{25} = \left ( \begin{array}{cccc} 1 & ~\cdots & ~\cdots & ~1 \\ & ~\cdots & ~\cdots & \\ 1 & ~\cdots & ~\cdots & ~1 \\ 0 & ~\cdots & ~\cdots & ~0 \end{array} \right ) \quad A^{26} = J \end{eqnarray*}

從運算結果, 我們知道, $A^{21}$ 第一次出現了一個全 1列 (第 1列)。而到 $A^{26}$ 每個列都是全 1列。 其實際意義是: 當第一次聲鼓響起後, 至少經過 21次傳遞, 有可能 6個人都手上拿著花, 但是, 要出現這種結果, 初始拿花的應是第 1位置的人。而若把初始拿花者放在第 6位置。即便經過 25次傳遞, 也不會出現人人手上均有花的場面。 但是, 不論初始拿花位置如何, 傳遞 26次或以後, 鼓聲一停, 一定保證全體都要起立唱歌或跳舞。

用數學的語言表述, 圖 2中的 $MCS$ 網絡 $D_2$, 要使一個初始信息傳遍各點, 至少要傳遞 21次。 而要使兩個不同的初始信息傳遍各點, 至少要傳遞 22次, $\ldots\ldots$, 使 5個不同的初始信息傳遍各點, 至少要 25次。

三、 矩陣的「點指數」

用網絡的鄰接矩陣的冪運算, 確實能直接算出結果。 然而, 我們更需要用數學方法知道一個本原 $MCS$ 網絡傳遍 $k$ 個信息的最小步數。 如果用 $t$ 表示步數 (或稱時間) 的話, 即求 $t$ 的最小值。

從矩陣的冪運算又回到有向圖模型。我們先討論 $k=1$。

要知道, 矩陣 $A^t$ 中有一列, 不妨第 $i$ 列, 是全 1列, 就意味著在有向圖 $D$ 中頂點 $i$ 到每個頂點, 都有長為 $t$ 的途徑。 求 $t$ 的最小值, 即求第一次出現全 1列的 $A^t$。

考慮一個有 $n$ 個頂點 $1, 2, \ldots, n$ 的本原有向圖 $D$。 為了使敘述更數字化, 我們定義 $\exp_D(i, j)$ 為這樣最小的整數 $p$, 使對於每一個整數 $t\ge p$, 從點 $i$ 到 $j$ 都有長為 $t$ 的途徑 $(1\le i, j\le n)$。 因為 $D$ 是本原的, 因此 $\exp_D(i, j)$ 是有限的。我們定義頂點 $i$ 的「點指數」為 $$ \exp(i) := \max\{\exp_D(i, j)\}, \quad i = 1, \ldots, n $$

於是, $\exp(i)$ 是這樣的最小整數 $t$, 使得從 $i$ 到每一點 $j$ 都有長不小於 $t$ 的途徑。

為方便處理, 我們可以選擇 $D$ 中頂點的次序滿足 $$ \exp_D(1) \le \exp_D(2) \le \cdots \le \exp_D(n) $$

即 $\exp_D(1)$ 為在 $D$ 中一個信息傳遍各個頂點所需的最小時間 (步數) $t$。 換言之, $\exp_D(k)$ $(1\le k\le n)$ 是使 $A^t$ 有 $k$ 個全 1列的最小的 $t$, 也即在 $D$ 中, $k$ 個不同的初始信息能傳遍各頂點的最小時間 $t$。 易見, 這個最小時間與初始信息所在的位置是有關的。 但 $\exp_D(n)$ 是本原 $MCS$ 網絡 $D$ 的 $n$ 個不同的初始信息傳遍各點的最小時間。 因而也是任意 $k$ 個不同的信息 (與初始位置無關) 傳遍各點所需的最小時間。

現在我們看一個特殊的 $n$ 階有向圖 $D_3$ (圖3)。

這是圖 2中的 $D_2$ 的一般化, 即僅含長為 $n-1$ 和 $n$ 的兩個圈的圖。 我們考察 $k=1$ 的情形。

直接驗證可知, 若初始信息放在頂點 1, 則經過至少 $(n-2)(n-1)+1$ 步。此點的信息可傳遍各個頂點。 而若初始信息放在第 $m$ 點 $(2\le m\le n)$, 要使各點都掌握此信息, 至少要 $(n-2)(n-1)+m$ 步。

因此, $\exp_{D_3}(1)=(n-1)(n-2)+1=n^2-3n+3$ 。

從這個特殊的圖 $D_3$ 中, 也可以看出 $$ \exp_{D_3}(k) = (n-1)(n-2) + k = n^2 - 3n + k + 2, \quad (1 \le k \le n)\hbox{。} $$

四、 任意的本原 $MCS$ 網絡

我們不限於討論特殊的兩圈網絡。 用組合矩陣論的方法, 可以解決一般本原 $MCS$ 網路的點指數問題。 設 $n$ 階本原有向 $D$。

我們定義 $\exp(n, k):=\max\limits_D\{\exp_D(k)\}$, $k=1, \ldots, n$ 。 此處, 求最大值 $\max$ 取遍所有的 $n$ 階本原圖 $D$。

我們將用 $D$ 的最短圈的長給出 $\exp_D(k)$ 的上確界, 從而導出 $\exp(n, k)$ 的值。

我們稱長為 1的圈為環。先看 $\exp_D(1)$ 的一個上界。

引理1: 設 $D$ 是具有頂點集 $1, 2, \ldots, n$ 的本原圖, $D$ 中 $r$ 個頂點有環 $(r\ge 1)$, 則 $$ \exp_D(1) \le n - 1 $$

證: 取 $D$ 中的一個環點, 則此環點到 $D$ 的每個頂點必有長為 $n-1$ 的途徑。

引理2: 設 $s$ 是 $n$ 階本原有向圖 $D$ 的最短圈長, 則 $$ \exp_D(1) \le s(n-1) $$

證: 設 $A$ 是 $D$ 的鄰接矩陣, 則 $A^s$ 的對角線有 $s$ 個 1 。

$D$ 是強連通圖, $A^s$ 所對應的有向圖 $D^{(s)}$ 也是強連通圖。 在 $D^{(s)}$ 中, 點 $i$ 到 $j$ 有弧當且僅當在 $D$ 中, 從點 $i$ 到 $j$ 有長為 $s$ 的途徑。 因此 $D$ 中的長為 $s$ 的圈對應於 $D^{(s)}$ 有 $s$ 個環。

由引理 1, $\exp_{D^{(s)}}(1)\le(n-1)$, 即 $\exp_D(1)\le s(n-1)$ 。

引理3: 若圖 $D$ 含有子圖 $D'$, 則 $\exp_D(1)\le\exp_{D'}(1)$ 。

證: $D'$ 的弧集也是 $D$ 的弧集的子集, 由點指數定義, 引理 3得證。

另一方面, 從強連通圖的性質, 我們容易得到

引理4: 對 $n$ 階本原有向圖 $D$ $$ \exp_D(k) \le \exp_D(k-1)+1, \quad 2 \le k \le n \hbox{ 。} $$

證: 因 $D$ 是強連通圖, 故必存在一個頂點 $j$ 與具有第 $k-1$ 個點指數的頂點相連, 便得引理 3結論。

現在我們可以得出 $\exp_D(n, k)$ 。

定理: 若 $k$ 是正整數, $1\le k\le n$, 則 $$ \exp_D(n, k) = n^2 - 3n + k + 2 $$

證: 由引理 4, 有 \begin{equation} %(1) \exp_D(k) \le \exp_D(1) + (k-1) \end{equation}

設 $s$ 是 $D$ 的最短圈長。若 $s\le n-2$, 則由引理 2 \begin{equation} %(2) \exp_D(1) \le (n-2)(n-1) \le n^2 - 3n + 2 \end{equation}

若 $s=n-1$, 因 $D$ 是本原圖, 故 $D$ 必有另一個長為 $n$ 的圈。

即 $D$ 必含有圖 3的 $D_3$ 作為子圖。由引理 3及上節關於 $D_3$ 的討論 \begin{equation} %(3) \exp_D(1) \le \exp_{D_3}(1) = n^2 - 3n + 3\hbox{ 。} \end{equation}

比較式 (2) 和 (3) 便得 $$ \exp_D(1) \le n^2 - 3n + 3 $$

於是由 (1) \begin{equation} %(4) \exp_D(k) \le (n^2-3n+3) + (k-1) = n^2 - 3n + k + 2\hbox{ 。} \end{equation}

但由第三節對 $D_3$ 的討論知 $$ \exp_{D_3}(k) = n^2 - 3n + k + 2 $$

故 (4) 的界是 $\exp_D(k)$ 的上確界, 即 $\exp_D(n, k)=n^2-3n+k+2$ 。

五、 故事還可以繼續 $\cdots\cdots$

上節的定理告訴我們: 對於任一個本原的 $n$ 階 $MCS$ 網絡, 可以選擇初始的 $k$ 個位置發出 $k$ 個不同信息, 從而使 $n$ 個頂點在最短的時間 (步數) 都同時接受到這些信息。這個最短時間最多不超過 $n^2-3n+k+2$ 步。 而當此 $MCS$ 網絡形如圖 3的 $D_3$ 時 (恰具有兩個長分別是 $n-1$ 和 $n$ 的有向圈), 就需要耗費恰好 $n^2-3n+k+2$ 步。

從定理的證明, 我們不難看到, 這時, 初始信息所在的初始位置就是圖 $D_3$ 的 $$ 1, ~2, ~3, ~\ldots, ~k \hbox{ 點} $$

用定理的公式, 無須像第二節那樣借助於矩陣的冪運算, 我們可以直接得到圖 2中 $D'_2$ 的 $\exp_{D'_2}(1)=6^2-3\times 6+1+2=21$, 而 $\exp_{D'}(6)=6^2-3\times 6+6+2=26$ 。

當然, 對於圖 1中的 13階 $D_1$, 我們知道一個信息傳遍網絡所需時間的上界 $$ \exp_{D_1}(1) \le 13^2 - 3 \times 13 + 1 + 2 = 133 \hbox{ 。} $$

然而, 善於動腦筋的讀者還會有所作為, 故事還可以繼續。

一個進一步的問題會提出來: 如果 $k$ 個初始的信息是相同的, 那麼要傳遍 $n$ 個頂點, 所需的最小時間又是多少呢?

容易理解, 與此相聯繫的一個矩陣問題是: 給出一個 $n$ 階 $MCS$ 網絡的鄰接矩陣, 求出一個最小的 $t$, 使 $A^t$ 出現有 $k$ 列, 它們所成的子矩陣沒有全零行。

這個問題同樣可以用有向圖的模型解決, 不過與上述方法稍有不同而已。有興趣的讀者可參考文獻 。

「擊鼓傳花」是一個遊戲, 但不僅僅是一個遊戲。它與非記憶信息傳遞系統有著本質的聯繫。 透過這個窗口, 我們可以看到 $\langle\!\langle$組合矩陣論$\rangle\!\rangle$ 解決實踐問題的奧妙。

參考文獻

---本文作者任教中國廣州華南師範大學數學科學學院---