这并不是我发表的第二篇论文，选它作为第二个介绍的工作，因为这是我最最喜欢的几篇论文之一，而且它引出了我本科时的第三位导师：徐俊明教授。实际上这是一个很偶然的故事，我那个时候已经选择物理的方向了，但是对于数学和计算机还有割舍不了的情缘，于是在大三上学期的时候，选了一门带有计算机背景的应用数学的课程，叫做组合网络分析，是组合数学和图论的方向。那门课的老师就是徐俊明教授。

 

课程上到1/3左右的时候，接触到了一个极值图论最基本的定理：Ore定理。极值图论主要是研究在给定了某些限制条件的前提下，图的某些指标（拓扑结构的特征量）的上下界问题。Ore在四十年前给出了一个著名的定理[O. Ore, J. Combinational Theory 5 (1968) 75]，这个定理是一个上界不等式：e<=d+1/2*(v-d+4)(v-d-1)，其中e是一个简单无向连通图的边数，v是这个图的节点数，d是这个图的直径（最长的最短距离）。

 

尽管在教材中多次用到了Ore定理，但是却没有给出Ore定理的证明。但是各位搞过数学的同仁都知道，一个教材上看起来很简单的定理却没有证明，本身就是一种难以抗拒的诱惑。于是我去问徐老师，他说这个证明很长很烦，在课程要求之外。于是乎我自己尝试去证明（当时并不觉得能成功），结果一不小心证明出来了，而且非常简单。实际上，Ore以及后来一些相关的工作，其证明的思路都是先把网络（图）表达成一种广度搜索树的形式（这种层次结构可以很好表达最短距离这个量），然后在这个平台上play。这些方法也是证明和距离有关系的极值不等式的常见方法（现在常见，四十年前是很不常见的），所以说，这套招术可以看作是少林武当的招术，比较正统。我那个时候，学过的招术很少，所以走了一条邪路，就是把当前的图看作是从一个完全图移除掉一些边得到的，通过分析这个移除过程对Ore定理所涉及的各个量的影响来证明这个问题。有意思的是，这个方法不仅能十倍简单于Ore原来的方法，而且可以处理很多相关相续的工作，例如Entringer, Jakson, Slater, Ng, Teh等人的研究工作。

 

我当时证明完毕后，又去图书馆的过刊阅览室复印了Ore的工作（看懂他的证明比我自己完成证明消耗了更多的能量），然后把自己的证明整理好给徐俊明老师看。徐老师非常高兴，接着告诉了我一些相关的工作（就是我上面提到的Entringer, Jakson, Slater, Ng, Teh等人的研究工作），指导我继续深入研究。后来文章由刘隽完成了英文初稿（那个时候我的英文水平还没有达到4级，而刘隽高中的时候雅思考试就已经是整个华中地区的no. 1。），再由徐老师整理加工，投到了运筹学学报，很快就得以顺利发表。

 

我以科大数学系为单位的论文一共只有4篇，这一篇是我最喜欢的。虽然是发表在国内的杂志上，但是我觉得这个文章整个结构和证明思路可以用“雅致”来形容，我自己证明的时候都很享受。后来也发表过一些SCI的纯数学方向的论文，用到一些似乎高深的技术，但都没有这篇文章的精巧。就好像玩塔罗牌也需要智力和技巧，但终究是无法和围棋媲美的——花样太繁多，规则太复杂，以至于掩盖了单纯的美本身。

 

PS1：刘隽是个怪才，她精通多种乐器，钢琴有专业水平，美术书法都相当厉害，英语是同龄人中首屈一指的（全国英语辩论赛银奖），还拿过楚才杯的特等奖（在新概念作文比赛前，这是最大的青少年文学比赛之一）。在这种情况下，她高考还得了678分（那年四川省北大清华科大复旦的招分线在610-630之间）。如果她选择了音乐或者文学作为终生事业，或许成为一代大豪。不过现在在新加坡读生物学的博士，不知道是不是一个合适的选择。

 

PS2： T. Zhou , J. –M. Xu and J. Liu, “On diameter and average Distance of Graphs”, 运筹学学报 8 (4), 33-38 (2004).