关键词：简单图、分子拓扑指数、邻接矩阵的整数表示、标准邻接矩阵

1991年在北航工作时，朱昌中教授到我办公室，希望我解释当时化学杂志上新出现的词“分子拓扑指数”。 

      朱昌中是北航应用数理系前一任负责科研的副系主任，从事化学教学与科研。因已近退休年龄，所以没有留任。那时应用数理系获得国家自然科学基金资助的项目很少，但他主持了基金项目《吸收微波化合物物理化学性能与微波吸收效率关系研究》。作为老一辈，朱昌中非常关心我们的工作（特别是行政工作），经常给我们出主意应对一系列困难的问题。我原来认为，像他那样年龄大的化学教授在数学方面的知识要相对弱些，对高深的数学也不会感兴趣。但他却经常抽空与我讨论化学研究中的数学问题。他在学术方面认真追求和虚心态度使我深受感动。 

尽管对深刻的化学理论不熟悉，根据朱先生提到的“分子拓扑指数”一词，我联想到这肯定是与分子的结构图的拓扑性质有关。于是查阅了他所提供的资料，了解到该概念起源于对烷类大分子的研究。 

参考资料显示，化学家试图用不同数字代表不同的烷类分子，使得分子的性质与代表分子的数字形成简单的相关联系，这样就可通过这种关系设计新的分子，使之达到所需的性质。 

烷类是结构最简单的有机分子，分子只由碳原子和氢原子构成，而且所有的化学键都是单键。因此，这类分子的结构图可以看成是所有枝点次数都是4的树形图。树的叶子（次数为1顶点）代表氢原子，枝点代表碳原子。 

如果略去分子中原子的空间分布结构对分子性质的影响，将烷类分子结构简单地用树形图表示，那么用树形图的拓扑不变量作为表示烷类分子的数字应该是个不错的选择。 

一个几何体（曲线、曲面、或图论中的图）的所谓拓扑不变量是指当该几何体在做连续变形时（指在变形过程中几何体不发生断裂或粘连），始终保持不变的几何量。例如一个图的顶点数、边数、顶点的次数、图中三边形的个数等，又如一个定向的封闭曲面（定向指曲面可定义内外侧）的类似于环面的“洞”的个数（球面洞数为零，普通环面洞数是1。你也可做出有两个洞的环面，当用其做救生圈使用，它可让两人共用:)），欧拉示性数等，它们都是拓扑不变量。 

拓扑学是研究几何体的拓扑不变量的科学。 

资料显示，当时化学家已经给出烷类分子的若干拓扑不变量，分别称为不同的分子拓扑指数，如Wiener指数和Randic指数等，它们都能在一定程度上与分子的沸点有较好的相关性。但是这类指数也都有缺点，存在简并性，即存在两个或两个以上结构不同的分子共用同一个指数，也就是说这些指数不能和所描述的分子形成一对一的关系。

为了找出没有“简并性”的新拓扑指数，想到了简单图的邻接矩阵。结构不同的图对应的邻接矩阵肯定不同。但邻接矩阵也有缺点，即对同一个图，邻接矩阵可以有不同的形式，它们分别对应同一个图的顶点的不同标号方式。 

那么可不可将邻接矩阵变成若当标准型（Jordan form），用其数字特征构造分子拓扑指数？其实，这种尝试已有人做过，例如使用矩阵的特征根等，但这仍难消除简并性。除此，一般情况下，若当标准型不再是邻接矩阵的形式（简单图的邻接矩阵是对称，而且主对角线全是0的0、1 方阵）。 

这就产生了一个趣味的数学问题，如何将简单图（指无平行边，且无环的图）的邻接矩阵标准化，使标准化矩阵仍是该图的邻接矩阵，而且是唯一的。 

经尝试，这是可以做到的。注意，给定图的任何一个邻接矩阵的信息全部集中在左下三角阵（不包含原方阵的主对角线）或右上三角阵中的n(n-1)/2 个元素上。 

先将左下三角阵表示如下

           a_2,1

           a_3,1 a_3,2

           a_4,1 a_4,2 a_4,3

             _{…          …        …}      

           a_n,1 a_n,2 …     …   a_n,n-1

其中 a_i,j 是数字0 或1，i=2,3,…,n, j=1,2,…,n-1。

然后将左下三角阵元素按如下顺序由右向左排成一行:

(1)    将第一行的唯一元素a_2,1放在行的最右；

(2)    将第二行的两个元素由左至右按顺序逐个放在前面放好的第一行的元素的左方，得到一个有三个元素的行，

a_3,2 a_3,1  a_2,1  

(3)    再将第三行的三个元素由左至右按顺序逐个放在前面排放好的三个元素行的左方，得到一个有六个元素的行，

a_4,3 a_4,2  a_4,1  a_3,2  a_3,1 a_2,1      

…

这样继续下去就会将左下三角阵的所有元素排成一个长度为n(n-1)/2的0,1数字行

a_n,n-1  a_n,n-2 … a_n,1 … a_4,3  a_4,2  a_4,1  a_3,2  a_3,1  a_2,1      

将此行看成一个二进制非负整数，则该整数唯一地表示了对应的邻接矩阵。 

例如某4顶点图的邻接矩阵为

其左下三角为

1

0 1

0 1 1

根据上述规则就应排成如下6元素的0,1数字行

1 1 0 1 0 1

将其看成是某整数k 的二进制表示，该整数就是k=53。 

又如，某图邻接矩阵的左下三角阵为

1

1 0

1 0 1

对应的0,1数字行是

1 0 1 0 1 1

它表示整数43。 

再如

1

1 1

1 0 0

对应的数字行是

0 0 1 1 1 1

它表示整数15。 

不难看出非负整数与邻接矩阵形成一一对应，按此对应将该整数称为对应邻接矩阵的整数表示。 

但对每一给定的简单图，可以给出不同的邻接矩阵，它们所对应的整数表示也不同。应该选择哪个邻接矩阵作为标准矩阵呢？ 

联想理论物理学中常用的（充分体现了自然与美的）最小作用量原理，不妨将对应同一图的，整数表示最小的那个邻接矩阵定义为该简单图的自然标准邻接矩阵，将对应的最小整数表示称为该简单图的自然全信息拓扑指数，或简称自然拓扑指数。 

  由以下四点，可以看出这样定义是合理的： 

（1）显然，这个指数没有简并性；

（2）根据这个指数可以唯一地做出标准邻接矩阵，并画出图形，因此该指数包含了图的全部拓扑信息；

（3）将顶点数由2至5的全部简单图（可以不连通，但无孤立点）按这个指数由小至大排序，可得到图一

图一

由此可看出图的排序是很自然的；

（4）将碳原子数不超过9的全部无环的烷类分子（甲烷除外，因为对应图是孤立点，如果补充定义可将之放在排序的首位）按这个指数由小至大排序（图二，其中略去了氢原子）,

图二

此顺序与分子的沸点的高低显著相关（图三）

图三

（3）、（4）两点说明了这种定义的自然性。可以尝试用其它方式定义标准邻接矩阵及全息拓扑指数，但发现其它方式定义的指数很难有（3）、（4）两个性质，不自然。  

我将关于分子拓扑指数的理解及以上关于自然拓扑指数的想法介绍给朱昌忠先生后，他非常高兴，让我到他的讨论班上介绍。尽管他以前对图的邻接矩阵等概念不熟悉，他仍很努力地在家里的大桌子上用很多张大白纸认真画了有4个碳原子的所有烷类分子结构图，算出它们的Wiener指数和Randic指数，写出对应的邻接矩阵，并用上述思想将之标准化（那时还没给出标准化的算法，全靠尝试），算出相应的自然拓扑指数。 

在他完全了解了我的想法后，他又和他的研究生合作，进一步将分子的空间结构对分子性质的影响考虑进去，创造出一个在化学上可能更好的分子拓扑指数。该工作1995年发表在<Chemistry>第一期，15-18页。 

那时我也了解到将图的邻接矩阵标准化还有个好处是可以用于比较两个图是否同构。而当时我的研究重点是微分方程的可积性理论及一些力学的基本问题，在北航我没有进一步研究邻接矩阵的标准化问题。 

后来朱昌中先生得了重病，1998年不幸过世。那时我已调到北京交通大学工作。 

在交大，我曾抽空总结了将邻接矩阵化成标准邻接矩阵的规则，总起来说就是尝试给图的顶点逐步重新标号，使邻接矩阵最后一行对应的二进制数（注意是从左到右定义二进制数字的位数）最小，在保持最后一行最小的条件下，再使左下角阵倒数第二行对应的二进制数最小，等等，这样进行到最后一行即可得到标准邻接矩阵。 

当然，说起来简单，实际编程、操作时经常遇到不同的可能标号对应同一效果的情况（与图的自同构有关），在没有进行到最后一行的最小判定时，以前得到的每种等效标号都必须保留，以供随后选择哪个更小。因此，编程序很费周折。不过经努力还是编成了一个程序。在顶点为几十个的情况下，用现有的普通 PC运算，一般不超过两小时的计算时间。图的自同构较少时几分钟就能出结果。 

我不太清楚图论中是否已有同样结果，是否有意义。然而，相信通过此文介绍有关的研究经历及相关的学术问题可能有些读者会感兴趣。 

另外，作为我个人，重新回顾与朱昌忠先生的这段合作，回忆他在家里的大桌子旁，不太亮的灯光下，聚精会神、严肃、认真地尝试计算图的标准邻接矩阵的场景，回忆他虚心求教的科学态度，确有一种难以表达的感动。他是值得我学习的。 

愿藉此文追念朱昌忠先生。