這幅圖在圖論裏就稱為「強正則圖」。先了解下，什麼是正則圖。正則圖的定義是：如果一個圖的所有點的度數，也就是所有點的鄰居數量相等，則它就是正則圖。正則圖非常好畫，比如如果一個圖中任何兩個點之間都有連線，也就是n個點的圖中，每個點的度數都是n-1，則它必是正則圖，而且我們稱它為「滿圖」，因為其中的連線數已經滿了。

另一種簡單的正則圖就是把所有點連起來，構成一個圈，這樣每個點的度數為2，稱為「環圖」(cycle graph)。這兩種都是很平凡的正則圖，還有很多不那麼平凡的正則圖。一道很好的智力題就是，對n個點的圖，當每個點的度數是多少時，可以構成正則圖。這道題是難度中等的一道智力題，供大家思考挺不錯的。（答案）

因為正則圖很多，所以不好玩，但是強正則圖就好玩多了。強正則圖，顧名思義，其要求要比正則圖強。它需要在正則圖基礎上再多兩個條件：

1. 對任意兩個相鄰的點，同時與這兩點相鄰的點的數目相等，這個數字通常記作希臘字母λ
2. 對任意兩個不相鄰的點，同時與這兩點相鄰的點數目也相等，這個數字記作希臘字母μ。

通常我們把一個圖的總的點數記作v，每個點的度數記作k，所以v, k, λ, μ四個參數，決定了一個強正則圖的基本特徵，我們常把這個四個數字連寫，來稱呼一個強正則圖。比如之前9個點的圖就被稱為（9,4,1,2）-強正則圖。

此時又有一個有意思的智力題，對一個強正則圖來說， 它的四個參數v, k, λ, μ是互相獨立的嗎？你稍微想一下，會發現，它們不是獨立的，需要滿足一定關係。可以從圖中某個點A考慮。這個點A的有k個鄰居。對這個k個鄰居，每個點也有k個鄰居，考慮其中某個鄰居B。B的鄰居中必有一個是A點，另外還有λ個是A的鄰居。所以B的鄰居中有k-1-λ個鄰居不是A的鄰居，且到A的距離是2。總體而言就有 k(k-1-λ)個點到A的距離是2。這裡，距離的定義就是兩點之間最短的路徑長度。

另一方面，A的鄰居有k個，則圖中有v-k-1個點不是A的鄰居。而這v-k-1個點到A的距離都是2，一共有μ個這樣的點，所以總共有μ(v-k-1)個點到A的距離是2。這個表達式與之前的表達式都是到A距離為2的點數量，應該相等，由此我們就得到了一個含有v, k, λ, μ的等式！所以這個四個變數不是獨立的，以上聽上去有點繞，但強烈推薦你自己在紙上畫畫，算算看，相信你也能找到這個等式:

而一般我們是先確定v,λ,μ去計算k，你會發現計算k，是一個解一元二次方程的過程，那意味著只有這個方程有正整數解，才表示這組v, k, λ, μ可能構成一個強正則圖。

既然v,k,λ,μ要滿足如此強的條件，才能構成強正則圖，那是不是這也是構成強正則圖的充分條件？很可惜不是。接下來我帶大家瀏覽一下點數比較少的情況下的一些強正則圖，你會發現這是一個不斷有驚喜也不斷有意外的過程。

再說明一下，接下來我默認排除完全圖的情況，即任何兩點之間都有連線的情況。因為n個點完全圖必然是(n, n-1, n-2, n-2)的強正則圖，這是一種很平凡的情況。另外，我還要排除μ等於0。μ等於0，圖會斷開，但我們只考慮連通圖。

還有一點，如果一個圖是強正則圖，則它的「補圖」也是強正則圖。「補圖」是：當你有一個圖之後，你看看還要添加哪些邊可以補成一個完全圖，你添加的這些邊就是原圖的補圖。你可以體會下一個v, k, λ, μ的強正則圖的補圖的四個參數是啥。總之強正則圖經常成對出現，除非它的補圖就是它自身。

那我們先看3個點，三個點的強正則圖只有三角形，即三個點的完全圖。4個點的強正則圖出現第一個非完全圖的強正則圖，即4邊型，參數是(4,2,0,2)，五邊形也是強正則圖，其參數是(5,2,0,1)。稍思考下，你會發現6邊型及以上就沒有強正則圖了。

但6個點的話，會出現兩種其他類型的強正則圖。構造方法如下：6個點分成兩組，每組三個點，然後把屬於不同組的點互相都連線，同一組的則不連線，這樣你很輕易的得到一個（6, 3, 0, 3）的強正則圖。這種圖也被稱作「完全雙邊圖」（Complete Bipartite Graph），因為其中的點可以分成兩組，同一組的點不連線，不同組的必連線。你也能發現，任何完全雙邊圖中，只要兩邊的點數一樣，則必然得到一個強正則圖。

類似，6個點你也可以分成三組，每組兩個點。同樣，同一組的2點不連線，不同組的點都連線，則你又輕易得到一個（6，4，2，4）的強正則圖：

這種圖你可以猜到被命名為：完全3方圖。你也可以發現，只要點數是合數，那隻要做質因數分解，把點數分解成若干相等的份，總能搞出一個「完全n-方圖」，而且是強正則圖。因為這種強正則圖構造很簡單，所以也是無趣的。幸好除去這種圖之外，還有很多強正則圖。所以後面的介紹我就忽略這種「完全n方圖」，也把它算一種平凡強正則圖。

7個點就沒有強正則圖了，你可能認為這是因為7是一個質數，所以其中無法構造這種強對稱性。確實11個點也沒有強正則圖，但是13個點的情況下又有了！稍後你會看到。8個點沒有非平凡的強正則圖。

9個點情況，在節目開始的智力題裏已經介紹過，存在一個（9，4，1，2）的強正則圖。而這個圖也被稱為「廣義四邊形」（Generalized Quadrangle）。我一開始看到這個名詞也很迷惑，四邊形還不夠「一般化」嗎，它怎麼還能推廣？我們來想一下，四邊形要推廣，那我們就要去掉四邊形的一些性質，但儘可能保留四邊形的其他性質。顯然，我們得去掉4個點和4條邊的要求，但去掉4個點和4條邊，四邊形還剩啥?! 數學家就是會來事，他們說四邊形還有這條性質：如果兩個點不相鄰，則可以找到另外兩個點與它們同時相鄰，這樣這四個點就構成一個四邊形。如果一個圖符合上述性質，則就是一個「弱廣義四邊形」。確切的廣義四邊形和廣義n邊型定義，請各位自行查閱思考了。

接下來10個點的情況下，有一個很有意思的強正則圖：（10, 3, 0, 1），這個圖形狀是一五角星外面套一個五邊形，然後把五角星的角和五邊形的角連接起來，兩兩連接起來。這個圖又被稱為佩特森圖（Petersen Graph）。佩特森（Julius Peter Christian Petersen，1839年6月16日－1910年8月5日）是19世紀後期的丹麥數學家。佩特森圖有一些很有意思的性質，最有意思的一條是它必有哈密爾頓路，但沒有哈密爾頓迴路。也就是你可以在佩特森圖中找出一筆畫的方法通過所有點，但是你無法找到一筆畫的路徑通過所有點之後還能回到起點的。而且可以證明，佩特森圖森圖裡只要再任意添加一條邊，就可以找到哈密爾頓迴路。

再接下來，我們要跳到13個點的情況了。前面說了7個點和11個點都沒有非平凡強正則圖，但是13個點卻有一個，這就是（13, 6, 2, 3）圖! 它又被稱為佩裏圖。 佩裏是20世紀初的英國數學家Raymond Paley (7 January 1907 – 7 April 1933，因滑雪事故去世）。佩裏圖的特點是點的個數必須是單個素數的冪次；此外還必須是除以4餘1。這個條件蘊含了只要是除以4餘1的素數都可以，13正好是符合條件的。符合這一條件的點數，必然可以構造出佩裏圖，而佩裏圖必然是強正則圖；它也是哈密爾頓圖，即它必然含有哈密爾頓迴路；它也必然是「自補圖」，就是它的補圖就是自身。以上就是佩裏圖的部分有趣性質。

13個點之後，我們再看看16個點的強正則圖，這裡又出現了一個有意思的情況。前面我們已經討論了這麼多，不知你有沒有發現一個問題，就是給定一組強正則圖的四個參數(v, k, λ, μ)，這四個參數如果可以構成強正則圖，是否唯一確定一個圖？我們前面真還沒說這件事。當然這裡要排除那種把A點換到B點，B點換A點之類這種置換情況下構成的新的圖，術語叫「同構」。我們問的是，排除同構的情況，4個參數是否唯一確定一個強正則圖？

感覺上強正則圖對參數已經有很嚴格要求了，所以你可能認為四個參數是唯一確定一個強正則圖，但是錯了，（16, 6, 2, 2）就能確定兩種強正則圖！其中一種圖中文可以叫「車(ju)圖」（rook graph）。不管是國際象棋還是中國象棋裏的車都是直線前進的。如果你在一個4*4的國際象棋棋盤上，把一個車可以移動的路線全部畫出，就到了（16, 6, 2, 2）的車圖。

（16, 6, 2, 2）還可以確定的一種圖叫「西力克漢特」圖(Shrikhande graph)，它是1959年印度數學家西力克漢特首先發表的：

它的特點是一種「距離規則圖」(distance-regular graph)，即在圖中你任取兩點a,b，然後你任取數值，比如2和3。數一下與a距離為2的點和與b距離為3的點數量，記錄一下這兩個數字。然後你換一對a,b，同樣統計這兩個數字。你會發現，無論取怎樣的a和b，你的統計結果總是一樣的。所以它叫距離規則圖。

而西力克漢特圖又是一種「非距離傳遞圖」（non distance-transive graph），所謂」距離傳遞「就是從a到b的距離加b到c的距離，等於a到c的距離。所有距離傳遞圖都是距離規則圖，但是它的逆命題並不成立。西力克漢特圖不是距離傳遞圖，卻是距離規則圖，它是這種反例中點數最少的一個，（請觀察一下反例在何處）所以它是很特別的。

以上就是(16,6,2,2)的強正則圖。16個點還有一個強正則圖是：（16, 5, 0, 2），它又叫克勒佈施圖（Clebsch Graph），因為它與1868年，德國數學家Alfrad Clebsch發現的四次曲面的16條線的配置有關。同時它又是距離規則圖和16個點的分圓圖（Cyclotomic Graph）。而分圓圖就是佩裏圖在三維空間裏的一個模擬。

接下來17個點，因為17除以4餘1，所以有17個點的佩裏圖，就不講了。

接下來，21個點又有一個新圖了，(21, 10, 3, 6)，又有一個新名字叫：克內澤爾圖（Kneser』s Graph）。這個名字來自於數學家克內澤爾1955年提出的一個組合數學中猜想：對2n+k個元素的集合，取n個不相交子集，並把子集分為k個類，則其中至少有兩個不相交子集屬於同一類。1978年匈牙利數學家拉茲洛·洛瓦茲（László Lovász）就用圖論的方法證明瞭克內澤爾的這個猜想，其中圖中的點代表一個子集，每條邊連接兩個不想交子集。因此這個圖就被叫做克內澤爾圖。也許更應該叫洛瓦茲圖，但數學對象的命名是相當隨意的，需要一些運氣。

17點之後，我們略過一些之前講過的圖，比如25個點，因為25是5的平方，且除4餘1，所以也有25個點的佩裏圖（25,12,5,6）。25個點可以構造一個5*5的象棋棋盤，所以也必有一個「車圖」，還有很多圖我必須略過。

但36個點的時候有一個非常令人喫驚的情況，就是（36, 15, 6, 6）這個圖。之前我們說過一個正則圖的參數不一定只決定一個圖，比如（16, 6, 2, 2）就有兩種圖，但大多數情況只有一種圖。但是（36, 15, 6, 6）對應的強正則圖有32548個！為什麼會突然爆發，完全不知道。

你可能認為36這個數字因子比較多？但是36個點之後，再沒有哪個參數能達到那麼多。我一開始以為是不是36這個數字基礎因子只有2和3，所以圖種類多。但我看了下48或者72個點，這兩個點數居然完全沒有非平凡的強正則圖。當然，也可能是數學家沒有辦法去枚舉更多點數的情況。總之數學家用計算機枚舉了（36, 15, 6, 6）不同構強正則圖的數量，就有那麼多。之後很多參數下確切的強正則圖的數量數學家都是不知道的，因為枚舉是無法窮盡的。

接下來一個有意思的圖是（50, 7, 0, 1）圖，人稱霍夫曼-辛格爾頓圖(Hoffman-Singleton Graph)。這個圖是唯一的一個，所有點度數達到7，直徑為2，周長為5的圖。要解釋一下圖的直徑和周長。其實很簡單，這是對圓直徑和周長概念的模擬。圖的直徑就是圖中最遠距離的兩個點的路徑長度。周長就是圖中最短的一個環路長度。

一般來說，一個圖直徑越短，它的周長也會越短。但是霍夫曼-辛格爾頓圖直徑只有2，也就是任何2點，只要走兩條邊，必可到達；但是周長又達到5，也就是圖中你要找個環路，必須要走5條邊。而且圖中每個點都有7條邊相連，說明圖中的邊是很多的，所以這個圖就更難得了。這絕對是非常有意思的一個圖。

接下來有意思的是（56, 10, 0, 2）圖，人稱格維茲圖（Gewirtz graph)。這個圖好玩之處在於，可以用一下方法來構造了這個圖：畫了一個7*8的格子，然後在每個格子裏填入6個字母。然後檢查任何兩格之間的字母有沒有相同的。沒有相同的字母，則就在兩格之間連一條線。當你把所有格子的連線都完成後，你就畫出了這幅格維茲圖。

有人還在7*11的格子裏做了類似的事情，這樣能夠構造出（77, 16, 0, 4）這個圖，而這個圖又稱 圖。這個 名字你聽起來是否耳熟？這不是一種武器或戰鬥機型號。我之前在介紹散在單羣時，就介紹過馬蒂厄羣，其中的一個就是 。而這個強正則圖，恰好蘊含了這個散在單羣的結構！這也不奇怪，因為強正則圖本身是高度對稱的，而有限羣就是體現對稱性的一個最佳抽象，所以強正則圖與羣聯繫是毫不意外。

好了，接下來準備收尾，講最後一個特定的圖：（100，22，0，6），人稱「西格曼-西姆斯圖」（Higman-Sims Graph）。這個圖點數正好100，而且它的一種構造方法是利用M22加上施泰納系統（3，6，22），就可以得到！

這個施泰納系統正好是大老李上一期節目提到過的。 有77個點，施泰納系統(3，6，22）有22個點，每6個點連一條線，每3個點恰好在一條線上。此外再加1個獨立點，有點像畫龍點睛一般，完成77+22+1=100，就可以完成西格曼-西姆斯圖。具體構造過程也請大家自己思考下。

希望聽到這裡你能感受到聽大老李節目的一個好處就是，以前的內容能在後面的節目中不經意的串聯起來。大老李在剛開始做這期的節目是，完全沒想到強正則圖還能與散在單羣和施泰納系統聯繫起來，但正好大老李之前看過單羣和施泰納系統的內容，所以再看到這裡就感覺容易理解多了。希望你也有同樣感覺。

講到這裡，我大概已經把點數100以內，非平凡的強正則圖中，最有意思和特點的一些講給大家聽了。但每個圖我也只能浮光掠影般的介紹一下，有很多圖本身都可以做一期節目。目前人們找到的最大非平凡的強正則圖已經到了點數幾十萬，但還有很多點數很少的參數組合，我們還不能確定是否存在。

看到這些強正則圖，我一個感想就感覺好像在集郵。完全圖和完全n邊圖都可以算作普通郵票，佩裏圖稍微特殊點，但很多，可以算紀念郵票。剩下的就可以算作特種郵票了。如果把這些圖發行郵票放在一起看真的是會很好看的。

另外我也想到了元素週期表。如果你把非平凡強正則圖按點數從小到大排列，很像一個元素週期表。而點數一樣的不同的圖，就像同位素。而像（16，6，2，2）可以對應兩種圖的情況，則就像碳，石墨，金剛石的這種同素異形體。

更妙的是，跟化學元素一樣，數學家也預言了在某些位置上，可能有強正則圖。比如（100，33，8，12） 這組參數，是可能存在強這則圖的，甚至於如果它存在，它的很多性質都能算出來了，但是就是不能證明它存在。

這也是強正則圖神祕的地方，除了少數幾種，比如佩裏圖這種，我們知道它存在的充分必要條件，其他的我們都只知道必要條件，不知道充分條件，所以數學家只能一個個去驗證。所以我把它們叫做圖中的寶石，你知道在某個很確切的地方可以有寶石，但是你挖下去可能還是沒有。

而目前有一塊寶石，有人懸賞1000美元去發掘，這就是我在不久前一期節目中，提到過的

康威的4道懸賞題?

www.ximalaya.com

康威四道懸賞題中的一道。其中一道是問：是否存在一個99點的圖，如果圖中兩個點相鄰，則這兩個點恰好屬於一個三角形；如果兩個點不相鄰，則這兩個點恰好屬於一個四邊形。你應該聽出來，這道題就是問是否存在這樣一個99個點的強正則圖！但是康威沒有給出每一個點應該有多少個鄰居，這個問題就留給聽眾自行計算了，是一道非常好的智力題。

如果問我是否存在這個99點的圖，我現在傾向於它不存在。因為證明一個東西存在要比不存在簡單很多，但是這麼久時間都沒有人證明它存在，所以我傾向於它不存在。要證明不存在，用電腦枚舉是一種方法，但是99個點暴力枚舉是不可能等到結果的，這就是難度所在。

好了，今天聊的夠久了，希望大家喜歡強正則圖，它們很對稱，很漂亮，確實可稱寶石。

在喜馬拉雅FM收聽「大老李聊數學」：

http://www.ximalaya.com//album/14777844#10006-weixin-1-52626-6b3bffd01fdde4900130bc5a2751b6d1 (二維碼自動識別)

參考鏈接：

http://mathworld.wolfram.com/StronglyRegulyeGraph.html

http://www.maths.gla.ac.uk/~es/srgraphs.php

https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html

http://users.cecs.anu.edu.au/~bdm/data/graphs.html

http://staffhome.ecm.uwa.edu.au/~00013890/remote/srgs/

推薦閱讀：