论文标题:
Adjacency-degree algebras and spectral determination of graphs
发表日期:
2026年07月 发表单位:
深圳北理莫斯科大学（Shenzhen MSU–BIT University）、北京理工大学（Beijing Institute of Technology） 原文链接:
https://arxiv.org/pdf/2607.21494v1.pdf
树谱的终极秘密：主矩如何不动声色地重建一棵树
树这个东西，看着朴素，实则非常“难伺候”。它没有环，结构干净，但正因为干净，任何一点局部信息都可能被别的树学着长出来。谱图理论里最经典的问题之一，就是：能不能只看一些代数不变量，就把一棵树唯一认出来？这篇论文给出的答案很硬气：只看主矩（principal moments）就够了。更准确地说，围绕邻接矩阵 A 和度矩阵 D 的那些“带着一号向量一起算”的矩，已经足以重建任意一棵树。这个结论的味道很像：别再只盯着树的外形了，连它的“代数指纹”都能直接验明正身。图1：论文核心结论示意——主矩足以确定树，并与叶子剥离、轨道分解和颜色精化建立联系。这里的“主矩”不是玄学词。论文定义的是形如 1Tw(A,D)1 的标量矩，其中 1 是全 1 向量，w(A,D) 是由 A 和 D 组成的任意词。把它翻成人话，就是：不是单看矩阵自己的谱，而是看“矩阵作用在全 1 向量上会留下什么痕迹”。这个痕迹像一串不容易伪造的脚印，树一旦走过，多少会留下点不可逆的信息。
叶子剥离的代数版本：从矩阵恒等式到轨道指示子
这篇工作的精彩之处，不在于它“说树能重建”这件事本身，而在于它把 McKay 经典的 叶子剥离（leaf stripping） 方法，改写成了一套非常整齐的代数流程。原来手工剥树皮的动作，现在变成了矩阵乘法和选择算子之间的配合，读起来像在做线性代数，实际却是在“拆树”。论文里最关键的一个观察很朴素，也很要命：如果 W 是森林里的某些叶子集合，令 XW 为它们的对角指示矩阵，那么 A XW A 竟然会变成一个对角矩阵，而且对角线上记录的正是“每个点挨着多少个被选中的叶子”。这一步非常妙。因为它意味着：本来需要外部颜色或手工标记才能做的“谁是叶子、谁连着谁”，现在可以直接从 A 和 D 的代数运算里长出来。论文把这种“长出来”的对象叫做轨道指示子，本质上就是把每一类在自同构下等价的点，用一个 0-1 向量准确圈出来。看到这里，思路其实已经透了：先用矩阵把“叶子邻居计数”做出来，再用这些计数去筛选下一轮可以剥掉的点，接着继续更新图，直到只剩下中心。这个过程和传统树同构算法里的 AHU 剥叶非常像，但这里的重心不是“算法实现”，而是“这些步骤都能写进主矩里”。更进一步，论文还把森林中每个点的“下层根类型”一层层编码出来。这里的“下层根类型”可以理解成：站在某个点往远离中心的方向看，下方挂着一棵什么样的子树。剥叶时，当前点不是孤立地被看待，而是连同它下面那些已经剥出来的结构一起被标记。于是整个森林被拆解成一套层层递归的类型系统，最后再把这些类型重新拼回原树。这就解释了为什么论文会强调“主矩不仅是数值，更是结构证书”。因为这些矩不是孤立地给一个分数，而是在一步步暴露整棵树的分层轨道、父子关系和中心结构。说得接地气一点：树以为自己只是在安静生长，结果被一串矩阵乘法扒得明明白白。😂
主矩为什么够用？——全矩阵商与树刚性定理
如果说上一部分是在“怎么扒树皮”，这一部分就是在回答：为什么扒到最后，信息不会丢。论文给出的核心结构是：对树而言，自同构轨道上的商图，不只是能看，甚至在邻接与度的诱导作用下，会变成一个“全矩阵代数”。这个结论很狠，因为全矩阵代数意味着这套商表示已经足够富，几乎没有信息残留在外面。把这件事翻成人话：如果把一棵树按自同构轨道压缩成几个“代表点”，那么在这几个代表点上由 A 和 D 诱导出来的运算，已经强到可以生成所有矩阵单位。矩阵单位都能生成，别的细节自然也就能拼回来了。这就是论文里“树刚性”的本质：不是靠某个偶然不变量碰运气，而是代数结构本身已经没有缝可钻。图2：轨道商与全矩阵代数的关系——树的商表示足够丰富，因此主矩可恢复整棵树。这也是为什么论文不是简单停留在“矩相同，所以树相同”的口号上，而是沿着三个层次推进：先证明森林里主模块等于轨道模块，再证明树的轨道商代数是全矩阵，最后把主矩的相等转化成轨道商的相等，进而得到树同构。这条链条看起来长，但每一环都咬得很紧，没有哪一环是靠“相信作者的直觉”硬顶过去的。还有一个值得一提的点：论文不仅证明了“存在性”，还强调这种重建是构造性的。也就是说，它不是那种“理论上可以，但谁也不知道怎么做”的结果，而是可以顺着剥叶、找中心、回传轨道这一套流程把树恢复出来。对算法党来说，这句话比“存在唯一性”更像真金白银。
