这幅图在图论里就称为「强正则图」。先了解下，什么是正则图。正则图的定义是：如果一个图的所有点的度数，也就是所有点的邻居数量相等，则它就是正则图。正则图非常好画，比如如果一个图中任何两个点之间都有连线，也就是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/

推荐阅读：