邻接矩阵在简单多项式中的实现

Simple Polynomial Generation of Adjacency Matrices

摘要: 在代数图论中，邻接矩阵的多项式变换为刻画图特征子空间及对称性之间的联系提供了重要工具。本文研究简单无向图的邻接矩阵经特定3次及以下多项式变换前后仍保持图的邻接性的问题，系统刻画了满足该性质的图类。通过对二次与三次多项式的分类讨论，给出了邻接矩阵经多项式变换后仍对应邻接矩阵的必要条件，证明其必须为正则图且不含特定圈C₄作为子图。在此基础上，分析了广义彼得森图$P\left(n,k\right)$ ，确定了其在一类3次多项式变换下保持邻接矩阵性质的参数约束。进一步，本文刻画了多项式$x^2-k$ 变换前后保持同构的图，证明满足上述条件的图只有奇圈。最后，讨论了两类特殊图，彼德森图$P\left(5,2\right)$ 和树$W_n$ ，找出了两个三次多项式，使其邻接矩阵在变换后仍对应某个图。

Abstract: In algebraic graph theory, polynomial transformations of adjacency matrices provide an important tool for characterizing the relationship between graph eigenspaces and symmetry. This paper investigates the problem of preserving graph adjacency when the adjacency matrix of a simple undirected graph undergoes specific polynomial transformations of degree 3 or lower, and systematically characterizes the classes of graphs satisfying this property. Through the classification and discussion of quadratic and cubic polynomials, the necessary conditions for the adjacency matrix to still correspond to an adjacency matrix after polynomial transformation are given, proving that it must be a regular graph and contain no specific cycles as subgraphs. On this basis, the generalized Petersen graph $P\left(n,k\right)$ is analyzed, and the parameter constraints for preserving the adjacency matrix property under a class of cubic polynomial transformations are determined. Furthermore, this paper characterizes graphs that remain isomorphim before and after polynomial $x^2-k$ transformation, proving that the only graphs satisfying the above conditions are odd cycles. Finally, two special types of graphs, the Petersen graph $P\left(5,2\right)$ and trees $W_n$ , are discussed, and two cubic polynomials are found such that their adjacency matrices still correspond to some graph after transformation.

1. 引言

图论作为离散数学的重要分支，在刻画复杂系统结构、分析网络关系以及描述组合对象方面发挥着重要作用。图在计算机中通常以图矩阵或邻接表方式存储，常见的图矩阵有邻接矩阵，拉普拉斯矩阵，关联矩阵等。图矩阵的代数特征为图结构的研究提供了强有力的分析手段。对于一个简单无向图，其邻接矩阵反映了图中顶点之间的相邻关系。通过研究邻接矩阵的代数性质，可以将原本离散的图结构问题转化为矩阵分析问题，从而借助矩阵论、线性算子理论以及谱理论等工具，深入揭示图的正则性、对称性及整体结构特征。这种由“图”到“矩阵”的转化，是代数图论研究的核心思想之一[1] [2]。

在此背景下，一个具有挑战性的问题逐渐受到关注：当对图的邻接矩阵施加代数运算，尤其是多项式变换时，所得矩阵在什么条件下仍然是某个图的邻接矩阵？进一步地，如果多项式变换前后的邻接矩阵不仅在形式上对应图，而且其对应的图与原图同构，则意味着该图在此多项式变换下具有某种不变性。这类问题不仅深化了对图结构本质的理解，也为通过代数方式系统生成新图提供了理论基础。

从应用角度来看，邻接矩阵及其多项式变换在多个领域中具有重要价值。在统计物理中，晶格模型常通过图结构描述，矩阵多项式被用于高温展开和相变分析[3]；在网络科学中，多项式形式的邻接矩阵被广泛用于描述信息传播与动力学过程，对社会网络和复杂系统的扩散行为建模具有重要意义[4]；此外，在图像信号处理领域，多项式图滤波器作为核心工具，被用于信号平滑、去噪及分布式计算，其理论基础正是图矩阵的多项式算子[5]。

从理论研究的角度看，邻接矩阵多项式变换问题最早由Beezer系统提出并研究。Beezer完全刻画了路径图邻接矩阵在多项式作用下仍保持邻接矩阵性质的所有多项式，为后续研究奠定了基础[6]。随后，Weichsel将这一思想推广到更一般的图类，指出在多项式变换下保持图结构的图往往与距离正则图密切相关[7]。Fonseca等人进一步研究了圈图与路径图之间的多项式联系，通过引入切比雪夫多项式，明确揭示了图谱性质与多项式表示之间的代数关系[8]。

随着研究的深入，学者们开始从更一般的代数运算角度审视图的矩阵表示问题。一方面，有研究考察了邻接矩阵乘积仍对应某个图的情形，刻画了在矩阵乘积意义下保持图结构的图类[9]；另一方面，也有工作从矩阵可分解性的角度出发，研究哪些图可以表示为其他图邻接矩阵的乘积，从而拓展了图代数表示的理论框架[10]。在[11]中，研究了与图相关联的矩阵的乘积所能实现的图。[12]研究了图的矩阵乘积的谱性质，包括正则性、二分性及连通性。近年来，相关研究进一步与谱图理论和图神经网络中的多项式算子联系起来，显示出新的发展趋势[2] [13]。

在上述研究基础上，本文研究了邻接矩阵的多项式变换问题，系统研究在一些二次和三次多项式作用下，哪些图的邻接矩阵仍然保持邻接矩阵的基本性质。与现有研究相比，本文不仅关注是否仍为邻接矩阵这一判定问题，还进一步探讨了多项式变换前后图的结构关系，尤其是同构性问题，从而在代数变换与图结构保持之间建立更精细的联系。

本文结构组织如下：第二章中引入了本文所需的图论与代数图论基础概念，包括子图、图同构以及广义彼得森图等，为后续分析提供统一的理论框架。第三章围绕邻接矩阵的多项式变换展开系统讨论，从一次和二次多项式入手，逐步刻画使得多项式变换后仍为邻接矩阵的必要条件，得到图必须满足正则性以及不含三圈、四圈等结构限制。进一步地，本文对广义彼得森图进行了重点分析，明确给出了参数条件，并揭示了多项式变换对其局部结构与整体结构的影响。在此基础上，本文还研究了多项式变换前后图保持同构的情形，证明只有极其有限的图类(如奇圈)能够满足这一强条件，从而揭示了多项式作用下图结构稳定性的本质来源。最后，讨论了两类特殊图，彼德森图和树，找到相应的三次多项式，使得该图族的邻接矩阵在多项式作用下仍对应某个图的邻接矩阵，在有限分类与无限生成之间建立了清晰的代数联系。

2. 预备知识

本文仅考虑简单无向非空图。设$G=\left(V\left(G\right),E\left(G\right)\right)$ 为一个图，其顶点集$V\left(G\right)=\left\{1,2,\cdots ,n\right\}$ ，边集$E\left(G\right)=\left\{e_1,e_2,\cdots ,e_m\right\}$ ，$V\left(G\right)$ 中的任意两个顶点$i,j$ ，若$ij\in E\left(G\right)$ 则记为$i~j$ 。$G$ 的邻接矩阵$A\left(G\right)={\left(a_{ij}\right)}_{n\times n}$ (在不引起歧义下$A\left(G\right)$ 简记为$A$ )是一个对称$\left(0,1\right)$ 矩阵，其中$a_{ij}=1$ 若$i~j$ ；否则为$a_{ij}=0$ 。对$\forall i,j\in V\left(G\right)$ ，从$i$ 到$j$ 的最短长度的路称为$i$ 到$j$ 的最短路，其长度定义为$i$ 到$j$ 的距离，记作$d\left(i,j\right)$ 。图$G$ 中与顶点$i$ 所关联的边的数目称为顶点$i$ 的度，记为$\text{deg}\left(i\right)$ 。若图$G$ 所有顶点度数都等于$k\left(0\le k\le n-1\right)$ ，则称$G$ 为$k$ 正则图。下面给出本文需要的一些定义。

定义2.1 对图$G$ 和图$H$ ，如果$V\left(H\right)\subseteq V\left(G\right)$ 且$E\left(H\right)\subseteq E\left(G\right)$ ，则称$H$ 是$G$ 的一个子图，记为$H\subseteq G$ 。

定义2.2 广义彼得森图$P\left(n,k\right)$ 是一个含有$2n$ 个顶点的3正则图，其中顶点集$V\left(G\right)=\left\{x_1,x_2,\cdots x_n{y}_1,y_2,\cdots y_n\right\}$ ，边集$E\left(G\right)=\left\{x_i{x}_{i+1},x_i{y}_i,y_i{y}_{i+k}\right\}$ ，其中$i\in \left\{1,2,\cdots ,n\right\}$ ，下标均进行$\mathrm{mod}n$ 运算。

定义2.3 设$G_1=\left(V_1,E_1\right)$ 和$G_2=\left(V_2,E_2\right)$ 是两个图，如果存在一个双射函数$f:V_1\to V_2$ ，使得对$V_1$ 中任意两个点$i$ 和$j$ ，$ij\in E_1$ 当且仅当$f\left(i\right)f\left(j\right)\in E_2$ ，则称$G_1$ 与$G_2$ 同构，记作$G_1\cong G_2$ 。

定义2.4 对于一个连通的简单无向图$G=\left(V,E\right)$ ，其直径为图中任意两个顶点之间距离的最大值。记为$diam\left(G\right)=\underset{u,v\in V}{\max }d\left(u,v\right)$ 。

设$A$ 为一个$n\times n$ 方阵，$f\left(x\right)$ 是任一多项式，以下命题给出$A$ 与$f\left(A\right)$ 特征值及特征向量之间的联系。

命题2.5 设$\lambda$ 是$n\times n$ 矩阵$A$ 的一个特征值，$v$ 为其对应的特征向量，则对任意多项式$f\left(x\right)$ ，$f\left(\lambda \right)$ 也是$f\left(A\right)$ 的一个特征值，且对应的特征向量仍然是$v$ 。

证明：由$Av=\lambda v$ ，得$A^{k}v={\lambda }^{k}v$ 。设$f\left(x\right)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$ ，则

$\begin{array}{c}f\left(A\right)v=a_n{A}^{n}v+a_{n-1}{A}^{n-1}v+\cdots +a_{1}Av+a_{0}Iv\\ =a_n{\lambda }^{n}v+a_{n-1}{\lambda }^{n-1}v+\cdots +a_1\lambda v+a_{0}v\\ =\left(a_n{\lambda }^n+a_{n-1}{\lambda }^{n-1}+\cdots +a_1\lambda +a_0\right)v\\ =f\left(\lambda \right)v\end{array}$

故结论成立。

3. 邻接矩阵的多项式变换

Beeze在[7]中确定了所有的多项式$\varphi \left(x\right)$ ，使得将路邻接矩阵$A\left(P_n\right)$ 代入多项式$\varphi \left(x\right)$ 所得矩阵仍是某个图的邻接矩阵。Fonseca [9]完全描述了将圈的邻接矩阵$A\left(C_n\right)$ 代入路的特征多项式中所得的矩阵。本节我们将考虑给定多项式$f\left(x\right)=ax+b,x^2+bx+c$ ，存在哪些图$G$ ，使得其邻接矩阵$A$ 满足$f\left(A\right)$ 仍为某个非空图的邻接矩阵。

i) $f\left(x\right)=ax+b$ 。

因为$f\left(A\right)=aA+bI$ 仍是一个主对角线元素全为$0$ 的对称的$\left(0,1\right)$ 矩阵，故$a=1,b=0$ 。即$f\left(x\right)=x$ 。

ii) $f\left(x\right)=x^2+bx+c$ 。分三种情况讨论：

1) $c=0$ ，即$f\left(x\right)=x^2+bx$ 。

此时$f\left(A\right)=A^2+bA$ 。$f\left(A\right)$ 的第$i$ 个主对角线元素为$f{\left(A\right)}_{ii}=A_{ii}^2+b{A}_{ii}=\mathrm{deg}\left(i\right)$ 。对于任意非空图，显然无论$b$ 取何值，$f\left(A\right)$ 的主对角线元素均不全为0，因此$f\left(A\right)$ 不可能是一个简单图的邻接矩阵。

• $b=0$ ，即$f\left(x\right)=x^2+c$ 。

此时$f\left(A\right)=A^2+cI$ 。$f\left(A\right)$ 的第$i$ 个主对角线元素$f{\left(A\right)}_{ii}=A_{ii}^2+c=\mathrm{deg}\left(i\right)+c$ 。若$f\left(A\right)$ 仍是邻接矩阵，则$f{\left(A\right)}_{ii}=0$ ，即$c=-\mathrm{deg}\left(i\right)$ 。

• $b\ne 0$ 且$c\ne 0$ ，即$f\left(x\right)=x^2+bx+c$ 。

此时$f\left(A\right)=A^2+bA+cI$ 。$f\left(A\right)$ 的主对角线元素$f{\left(A\right)}_{ii}=A_{ii}^2+b{A}_{ii}+c=0$ ，即$c=-\mathrm{deg}\left(i\right)$ 。非主对角线元素$f{\left(A\right)}_{ij}=A_{ij}^2+b{A}_{ij}$ 。若$i,j$ 相邻，则有$A_{ij}=1$ ，那么$b=1-A_{ij}^2$ 。若$i,j$ 不相邻，则有$f{\left(A\right)}_{ij}=A_{ij}^2\le 1$ ，与$b$ 取值无关。综上，$b=1-A_{ij}^2$ 且$c=-\mathrm{deg}\left(i\right)$ 时，$f\left(A\right)$ 对应邻接矩阵。

下面讨论情形2)。

定理3.1 设$G$ 是一个$n$ 阶简单图具有邻接矩阵$A$ ，给定多项式$f\left(x\right)=x^2-k$ ，若$f\left(A\right)$ 仍对应某个图$H$ 的邻接矩阵，则图$G$ 是不含$C_4$ 作为子图的$k\left(0\le k\le \lfloor \frac{1+\sqrt{4n-3}}{2}\rfloor \right)$ 正则图，且$f\left(A\right)$ 所对应的图$H$ 为$k\left(k-1\right)$ 正则图。

证明：因为$f\left(A\right)=A^2-kI$ ，一方面，$f\left(A\right)$ 的主对角线元素$f{\left(A\right)}_{ii}=A_{ii}^2-k=\mathrm{deg}\left(i\right)-k=0$ ，也就是对$\forall i\in V\left(G\right)$ ，$\mathrm{deg}\left(i\right)=k$ ，故$G$ 为$k$ 正则图。另一方面，$f{\left(A\right)}_{ij}=A_{ij}^2$ 表示从顶点$i$ 出发到顶点$j$ 终止长为2的路径(walk)数，也就是$i,j$ 之间公共邻点的数目，记此数为$N\left(i,j\right)$ 。若$f\left(A\right)$ 仍对应某个图的邻接矩阵，则$N\left(i,j\right)=1$ 或0。若图$G$ 含$C_4$ 作为子图，则必存在$i,j\in V\left(G\right)$ ，使得$N\left(i,j\right)\ge 2$ ，与$f\left(A\right)$ 是邻接矩阵矛盾。所以$G$ 是不含$C_4$ 作为子图的$k$ 正则图。

下面考虑$f\left(A\right)$ 所对应的图$H$ 中任一顶点$i$ 的度。

图$H$ 中任意两点$i,j$ 相邻等价于$f{\left(A\right)}_{ij}=A_{ij}^2=1$ ，同时$f{\left(A\right)}_{ij}=A_{ij}^2=1$ 当且仅当图$G$ 中从顶点$i$ 出发到顶点$j$ 之间有且仅有一条步长为2的路径，则图$H$ 中任一顶点$i$ 的度等价于图$G$ 中与顶点$i$ 之间仅有一条步长为2的路径的顶点的个数。因为图$G$ 是$k$ 正则图，即$\forall i\in V\left(G\right)$ ，有$\mathrm{deg}\left(i\right)=k$ 。与顶点$i$ 距离为1的点有$k$ 个，另外这$k$ 个点除去与顶点$i$ 相连以外，还与其他$k-1$ 个点相连，所以图$G$ 中与顶点$i$ 距离为2的点有$k\left(k-1\right)$ 个，也就是在图$H$ 中，顶点$i$ 与$k\left(k-1\right)$ 个点相邻，所以图$H$ 为$k\left(k-1\right)$ 正则图。另外图$H$ 中顶点的度最大为$n-1$ ，所以$k\left(k-1\right)\le n-1$ ，解得$0\le k\le \lfloor \frac{1+\sqrt{4n-3}}{2}\rfloor$ 。定理得证。

根据上述定理，下面我们对$k$ 取特殊值，考虑可以使得$f\left(A\right)$ 为邻接矩阵的图$G$ 。

当$k=1,2$ 时，我们找到了满足多项式$f\left(x\right)=x^2-k$ ，且$f\left(A\right)$ 仍对应某个图的邻接矩阵的所有图。

$k=1$ 时，图$G$ 为完美匹配。

$f\left(A\right)=A^2-I$ ，一方面，$f\left(A\right)$ 的主对角线元素$f{\left(A\right)}_{ii}=A_{ii}^2-1=\mathrm{deg}\left(i\right)-1=0$ ，所以$\forall i\in V\left(G\right)$ ，$\mathrm{deg}\left(i\right)=1$ 。另一方面，完美匹配中任意两点之间没有公共邻点，$f\left(A\right)$ 的非主对角线元素$f{\left(A\right)}_{ij}=A_{ij}^2=N\left(i,j\right)=0$ 。所以$f\left(A\right)=0$ ，$f\left(A\right)$ 所对的图为空图。

$k=2$ 时，图$G$ 为不含$C_4$ 的不相交圈的并。

$f\left(A\right)=A^2-2I$ ，一方面，$f\left(A\right)$ 的主对角线元素$f{\left(A\right)}_{ii}=A_{ii}^2-2=\mathrm{deg}\left(i\right)-2=0$ ，所以$\forall i\in V\left(G\right)$ ，$\mathrm{deg}\left(i\right)=2$ 。另一方面，$f\left(A\right)$ 的非主对角线元素$f{\left(A\right)}_{ij}=A_{ij}^2$ 。$f{\left(A\right)}_{ij}=1$ 当且仅当$i,j$ 之间存在长为2的路径，否则，$f{\left(A\right)}_{ij}=0$ 。$\forall i\in V\left(G\right)$ ，与顶点$i$ 距离为2的点有且仅有两个，所以$f\left(A\right)$ 所对的图是2正则图，即不交圈的并。

$k=3$ 时，我们研究了广义彼得森图$P\left(n,k\right)$ ，首先给出$P\left(n,k\right)$ 包含4圈作为子图的条件。

定理3.2 若广义彼得森图$P\left(n,k\right)$ 含$C_4$ 作为子图，则$n,k$ 满足：$n=4k$ 或$k=1$ 。

证明：记由顶点$x_i,i\in \left\{1,2,\cdots ,n\right\}$ 导出的子图记为$X$ ，由顶点$y_i,i\in \left\{1,2,\cdots ,n\right\}$ 导出的子图记为$Y$ 。

下面讨论$P\left(n,k\right)$ 含$C_4$ 作为子图的情况。

• $C_4$ 包含于$X$ 。$\forall x_i\in V\left(G\right)$ ，$x_{i-1}~x_i~x_{i+1}$ ，其中下标均进行模$n$ 运算。子图$X$ 为$n$ 个顶点的圈。所以有

$C_4\subseteq X$ $\iff$ $n=4$ 。

• $C_4$ 包含于$Y$ 。$\forall y_i\in V\left(G\right)$ ，$y_i~y_{i+k}~y_{i+2k}~y_{i+3k}~y_{i+4k}$ ，其中下标均进行模$n$ 运算。当$y_{i+4k}=y_i\left(\mathrm{mod}n\right)$ 时，$Y$ 中出现$C_4$ 。

$C_4\subseteq Y$ $\iff$ $n=4k$ 。

另外子图$Y$ 为生成集为$k$ 的循环图，因为任意顶点$y_i$ 的度均为3，故$1\le k\le \lfloor \frac{n-1}{2}\rfloor$ 。

• $V\left(C_4\right)\cap V\left(X\right)\cancel{=}\varnothing$ 且$V\left(C_4\right)\cap V\left(Y\right)\cancel{=}\varnothing$ 。

可能的连接方式为$x_i~x_{i+1}~y_{i+1}~y_{i+1-k}~x_{i+1-k}$ 和$x_i~x_{i+1}~y_{i+1}~y_{i+1+k}~x_{i+1+k}$ ，其中下标均进行模$n$ 运算。当$x_{i+1-k}=x_i\left(\mathrm{mod}n\right)$ ，即$k=1$ 时，图中存在$C_4$ 。而当$1\le k\le \lfloor \frac{n-1}{2}\rfloor$ 时，不存在$k$ 使得$x_{i+1+k}=x_i\left(\mathrm{mod}n\right)$ 。故

$C_4\subseteq P\left(n,k\right)\iff k=1$ 。

综上，当$n=4k$ 或$k=1$ 时，$P\left(n,k\right)$ 含$C_4$ 作为子图。

定理3.3 设广义彼得森图$P\left(n,k\right)$ ，邻接矩阵为$A$ 。给定多项式$f\left(x\right)=x^2-3$ ，若$f\left(A\right)$ 仍对应某个图的邻接矩阵，则$n,k$ 满足：$n\ne 2k$ ，$n\ne 4k$ 且$k\ne 1$ 。

证明：由定理3.1得，若多项式$f\left(x\right)=x^2-k$ 使得$f\left(A\right)$ 为邻接矩阵，则图$G$ 是不含$C_4$ 作为子图的$k$ 正则图，因此$k=3$ ，$P\left(n,k\right)$ 为3正则图。

当$n=2k$ 时，$x_i~y_i~y_{i+k}$ 且$x_i~y_i~y_{i-k}$ ，因为，$y_{i-k}=y_{i+k}\left(\mathrm{mod}n\right)$ ，顶点$y_i$ 的度均为2，与$P\left(n,k\right)$ 为3正则图矛盾。所以$n\ne 2k$ 。

由定理3.2可得，当$n=4k$ 或$k=1$ 时，$P\left(n,k\right)$ 含$C_4$ 作为子图，故$n\ne 4k$ ，$k\ne 1$ 。

综上，当$f\left(A\right)$ 对应某个图的邻接矩阵，有$n\ne 2k$ ，$n\ne 4k$ 且$k\ne 1$ 。

下面讨论情形3)。

定理3.4 设$G$ 是一个简单图其邻接矩阵为$A$ ，给定多项式 $f\left(x\right)=x^2+x-k$ ，若$f\left(A\right)$ 仍为某个图的邻接矩阵，则$G$ 是不含$C_3$ 和$C_4$ 的$k$ 正则图。

证明：因为$f\left(A\right)=A^2+A-kI$ 仍是某个图的邻接矩阵，$f\left(A\right)$ 为主对角线元素均为0的对称$\left(0,1\right)$ 矩阵。一方面，$f\left(A\right)$ 的主对角线元素$f{\left(A\right)}_{ii}=A_{ii}^2+A_{ii}-k=\mathrm{deg}\left(i\right)-k=0$ ，所以$\mathrm{deg}\left(i\right)=k$ ，即$G$ 为$k$ 正则图。另一方面，$f\left(A\right)$ 的非主对角线元素$f{\left(A\right)}_{ij}=A_{ij}^2+A_{ij}\in \left\{0,1\right\}$ ，若$i,j$ 相邻，则有$A_{ij}=1$ ，那么必有$A_{ij}^2=0$ ，也就是$i,j$ 之间不存在长为2的路径，即图$G$ 不含$C_3$ 作为子图。若$i,j$ 不相邻，则有$A_{ij}=0$ ，那么$A_{ij}^2\le 1$ ，即图$G$ 不含$C_4$ 作为子图。

综上，若$f\left(A\right)$ 是一个邻接矩阵，则图$G$ 是不含$C_3$ 和$C_4$ 的$k$ 正则图。

下面我们研究了经多项式$f\left(x\right)=x^2-k$ 变换哪些图与原图同构，得到下面定理。

定理3.5 设$G$ 是$n$ 个点的简单图，邻接矩阵为$A$ ，给定多项式$f\left(x\right)=x^2-k$ ，若$f\left(A\right)$ 所对应的图$H$ 同构于图$G$ ，则图$G$ 只能是奇圈。

证明：若$f\left(A\right)$ 仍是邻接矩阵，则图$G$ 是不含$C_4$ 的$k$ 正则图。由定理3.1可知：$f\left(A\right)$ 所对应的图$H$ 是$k\left(k-1\right)$ 正则图。因为$H$ 同构于$G$ ，其正则度相同，故$k\left(k-1\right)=k$ ，解得$k=2$ 。所以图$G$ 只能是圈$C_n$ 或不相交圈的并。

当图$G$ 为奇圈时，即$n=2k+1$ 时，因为$\gcd \left(2,2k+1\right)=1$ ，2是$Z_{2k+1}$ 的生成元，且可以生成$Z_{2k+1}$ 中的所有元素，所以生成的图$H$ 也是一个圈，$H$ 同构于$G$ 。

当图$G$ 为偶圈时，即$n=2k$ 时，因为$\gcd \left(2,2k\right)=2$ ，2不是$Z_{2k}$ 的生成元，只能生成$Z_{2k}$ 中的$k$ 个偶数元素。从任意顶点$i$ 出发，与$i$ 奇偶性相同的点构成一个圈，故$H$ 是两个不相交圈的并，与$G$ 不同构。

以下设$f\left(x\right)=x^3+b{x}^2+cx+d$ ，我们给出了两类特殊图：彼得森图$P\left(5,2\right)$ 和树$W_n$ 经该多项式变换仍为简单图邻接矩阵的一个参数条件。

定理3.6 设$A$ 彼得森图$P\left(5,2\right)$ (见图1)的邻接矩阵，$f\left(x\right)=\frac{1}{3}\left(x^3+x^2-5x-3\right)$ ，则$f\left(A\right)$ 仍为某个6正则图的邻接矩阵。

Figure 1. Petersen graph $P\left(5,2\right)$

图1. 彼得森图$P\left(5,2\right)$

证明：因为$f\left(A\right)=\frac{1}{3}\left(A^3+A^2-5A-3I\right)$ 。一方面，$f\left(A\right)$ 的主对角线元素$f{\left(A\right)}_{ii}=\frac{1}{3}\left(A_{ii}^3+A_{ii}^2-5A_{ii}-3\right)$ ，其中$A_{ii}^2$ 为顶点$i$ 在图$P\left(5,2\right)$ 中的度，$A_{ii}^3$ 表示以$i$ 为顶点的三角形的数目的$2$ 倍，因为图$P\left(5,2\right)$ 中不存在三角形，所以有$A_{ii}^3=0$ 。因此有$f{\left(A\right)}_{ii}=\frac{1}{3}\left(\mathrm{deg}\left(i\right)-3\right)=0$ 。

另一方面，$f\left(A\right)$ 的非主对角线元素$f{\left(A\right)}_{ij}=\frac{1}{3}\left(A_{ij}^3+A_{ij}^2-5A_{ij}\right)$ 。因为彼得森图$P\left(5,2\right)$ 的直径$diam\left(G\right)=2$ 。下面根据$d\left(i,j\right)$ 分类讨论：

i) $d\left(i,j\right)=1$ ，此时$f{\left(A\right)}_{ij}=\frac{1}{3}\left(A_{ij}^3+A_{ij}^2-5A_{ij}\right)=\frac{1}{3}\left[\left(\mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)-1\right)-5\right]=0$ 。

ii) $d\left(i,j\right)=2$ ，因为彼得森图$P\left(5,2\right)$ 中任意两个不相邻的顶点均有一个公共邻点，此时

$f{\left(A\right)}_{ij}=\frac{1}{3}\left(A_{ij}^3+A_{ij}^2-5A_{ij}\right)=\frac{1}{3}\left(2+1\right)=1$ 。

因为彼得森图$P\left(5,2\right)$ 为3正则图，由i)，ii)得，

$f\left(A_{ij}\right)=10-3-1=6$

故$f\left(A\right)$ 为某个6正则图的邻接矩阵。

接下来，我们一个三次多项式$f\left(x\right)$ ，使得无穷类树图$W_n$ 的邻接矩阵$A$ 经该多项式中变换仍为某个图的邻接矩阵$f\left(A\right)$ 。

定理3.7 设$W_n\left(n>6\right)$ 为路$P_{n-2}$ 在其顶点$2,n-3$ 分别添加两个悬挂点$n-1,n$ 得到的树(见图2)其邻接矩阵为$A$ ，$f\left(x\right)=x^3-3x$ ，则$f\left(A\right)$ 均对应某个图的邻接矩阵。

Figure 2. A class of infinite trees $W_n$ with spectral radius 2

图2. 一类谱半径为2的无穷树$W_n$

证明：$f\left(A\right)=A^3-3A$ ，一方面，$f\left(A\right)$ 的主对角线元素$f{\left(A\right)}_{ii}=A_{ii}^3-3A_{ii}$ ，$\forall i\in V\left(G\right)$ ，$A_{ii}=0$ ，$A_{ii}^3$ 表示图$W_n$ 中以$i$ 为顶点的三角形的数目的2倍，因为$W_n$ 为树，不含三角形，故$f{\left(A\right)}_{ii}=0$ 。

另一方面，$f\left(A\right)$ 的非主对角线元素$f{\left(A\right)}_{ij}=A_{ij}^3-3A_{ij}$ 。该图的直径$diam\left(G\right)=n-3$ ，当顶点数$n>6$ 时，对$i,j$ 之间的距离$d\left(i,j\right)$ 分三类讨论：

i) $d\left(i,j\right)=1$ ，此时$f{\left(A\right)}_{ij}=A_{ij}^3-3A_{ij}=A_{ij}^3-3\in \left\{0,1\right\}$ 。且$\forall i,j\in V\left(G\right)$ ，

若$f{\left(A\right)}_{ij}=0$ ，$A_{ij}^3=3$ ，得$\forall i,j\in V\left(G\right)$ ，$\mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)-1=3$ ，即

$\mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)=4$ 。

若$f{\left(A\right)}_{ij}=1$ ，$A_{ij}^3=4$ ，得$\forall i,j\in V\left(G\right)$ ，$\mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)-1=4$ ，即

$\mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)=5$ 。

故当$d\left(i,j\right)=1$ ，

$f{\left(A\right)}_{ij}=\{\begin{array}{l}0,\mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)=4\\ 1,\mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)=5\end{array}$

ii) $d\left(i,j\right)=2$ ，此时$f{\left(A\right)}_{ij}=A_{ij}^3-3A_{ij}=0$ 。

iii) $d\left(i,j\right)=3$ ，此时$f{\left(A\right)}_{ij}=A_{ij}^3-3A_{ij}=1$ 。

iv) $3<d\left(i,j\right)\le n-3$ ，此时$f{\left(A\right)}_{ij}=A_{ij}^3-3A_{ij}=0$ 。

所以当$n>6$ 时，如果$i~j$ ，均有$4\le \mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)\le 5$ 成立。特别地，当$n=6$ 时，$\exists i,j\in V\left(G\right)$ ，使得

$\mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)=6\iff \mathrm{deg}\left(i\right)+\mathrm{deg}\left(j\right)-1=5\iff A_{ij}^3=5\iff f{\left(A\right)}_{ij}=2$

与$f\left(A\right)$ 为邻接矩阵矛盾，定理得证。

下面例子通过$W_8$ 验证定理3.7。

例3.1 设$W_8$ (见图3)的邻接矩阵为$A$ ，$f\left(x\right)=x^3-3x$ ，则$f\left(A\right)$ 对应某个图的邻接矩阵。

Figure 3. Trees $W_8$ with 8 vertices and spectral radius 2

图3. 8个点的谱半径为2的树$W_8$

将$W_8$ 的邻接矩阵$A$ 带入多项式$f\left(x\right)$ 中，得$f\left(A\right)$ 如下：

$A=\left(\begin{array}{cccccccc}0& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 1& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\end{array}\right)$ ，$f\left(A\right)=\left(\begin{array}{cccccccc}0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 1\\ 1& 0& 0& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\end{array}\right)$

4. 结语

传统图谱理论关注矩阵的特征值(谱)。本文从谱过渡到了矩阵本身，将图的邻接矩阵代入多项式所得矩阵仍为邻接矩阵的图。这直接探究图的结构与其矩阵的代数表示之间最本质的联系。如果一个图$G$ 的某个多项式$f\left(A\right)$ 恰好是它自身(或同构图)的邻接矩阵，这揭示了$G$ 的对称性——它的结构使得其不受该代数变换的影响，仅表现为顶点的重新标号。寻找具有这种性质的图类，这为图的结构分类提供了新方法。同时，在实际应用中，为网络科学、量子计算和编码理论等应用领域，提供了有力的理论工具。后续研究可以沿此方向，探索更一般的线性变换，而不仅限于多项式变换，例如研究矩阵函数、幂级数，其次，可将研究对象从邻接矩阵$A$ 转向其他重要的图关联矩阵，如图的拉普拉斯矩阵$L$ ，距离矩阵等，研究经过怎样的多项式变换所得矩阵仍对应某个图的邻接矩阵，持续推动这一研究的深度与广度。