有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

知識 01-18

是你的朋友

也是我的朋友

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

今天超模君來跟模友討論一個問題：「屋子裡有若干個人，任意兩個人都有恰好 1 個共同的朋友。」這有可能嗎？

有可能。

比方說，屋子裡有 9 個人，其中 8 個人正好組成 4 對朋友，第 9 個人則和前面 8 個人都是朋友。

容易驗證，任意兩個人都有恰好 1 個共同的朋友。

我們可以用下面這個圖表示此時這 9 個人之間的朋友關係，其中每個點代表一個人，如果兩個人是朋友，就在他們之間連一條線。

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

除了上圖展示的情況之外，我們還能構造出很多別的同樣滿足要求的情況。

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

事實上，上述方案可以擴展到一切奇數個人的情況，比如下面這樣：

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

現在，假設屋子裡有若干個人，任意兩個人都有恰好 2 個共同的朋友。這有可能嗎？有可能。

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

比方說，屋子裡有 4 個人，他們互相之間都是朋友。容易驗證，任意兩個人都有恰好 2 個共同的朋友。

我們可以用下面這個圖表示此時這 4 個人之間的朋友關係。

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

我們的問題是，除了上圖展示的情況之外，還有別的同樣滿足要求的情況嗎？

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

有。

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

想像屋子裡有 16 個人，他們站成了一個 4 × 4 的方陣。每行里的 4 個人互相之間都是朋友，每列里的 4 個人互相之間也都是朋友。

於是，對於任意兩個同一行或者同一列的人來說，都恰好有 2 個共同的朋友，即這一行或者這一列的另外兩個人；對於任意兩個既不同行又不同列的人來說，也都恰好有 2 個共同的朋友，即與我同行與你同列的人，以及與你同行與我同列的人。

我們可以用下面的這個圖表示此時這 16 個人之間的朋友關係（我們把同一行的點以及同一列的點都稍微錯開了一些，使得連線不會重疊在一起）。

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

那麼，除此之外，還有沒有別的滿足要求的解呢？有，比如下面這個圖：

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

上面這兩個圖有很多類似的地方：它們都有 16 個點， 48 條連線，每個點都恰好引出了 6 條連線。

不過，這兩個圖確實是本質不同的兩個圖。

你可以這樣看出來：前面這個圖中，與每個點相鄰的 6 個點互相之間連成的是兩個三角形；而後面這個圖中，與每個點相鄰的 6 個點互相之間連成的是一個「圈」。

任意兩個人都有恰好 2 個共同的朋友，究竟有多少種可能的情況呢？

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？

現在，我們已經看到了三個解。第一個解是 4 個互相之間都有連線的點。

在圖論中，我們通常用 K4 來表示這個圖。第二個解則是藉助一個 4 × 4 的方陣構造出來的。

在圖論中，這個圖叫做 4 × 4 rook』s graph ，因為它相當於國際象棋中的車（rook）擺成 4 × 4 的方陣後互相之間能否攻擊的示意圖。

真正神奇的就是問題的第三個解了。它叫做 Shrikhande graph 。這是由印度數學家 Sharadchandra Shankar Shrikhande 在 1959 年發現的。在圖論中， Shrikhande graph 是一個非常神奇的圖。

如果一個圖的每個點都引出了相同數目的線，我們就說這個圖是一個「正則圖」（regular graph）。

如果一個正則圖有 v 個點，每個點都引出了 k 條線，並且它額外地滿足，任意兩個相鄰的點之間都恰好有 λ 個公共鄰點，任意兩個不相鄰的點之間都恰好有 μ 個公共鄰點，我們就說這個圖是一個「強正則圖」（strongly regular graph），用符號 srg(v, k, λ, μ) 表示。

顯然， n × n rook』s graph 屬於強正則圖 srg(n^2, 2n – 2, n – 2, 2) 。

那麼反過來，滿足 srg(n^2, 2n – 2, n – 2, 2) 的圖是否一定就是 n × n rook』s graph 呢？基本上是，除了唯一的一個反例：當 n = 4 時， Shrikhande graph 也滿足 srg(n^2, 2n – 2, n – 2, 2) 。

有沒有可能屋子裡有若干個人，任意兩人都恰好有1個共同朋友？