等能量树的新判定方法

A New Criterion for Determining Equienergetic Trees

摘要: 设G和G'是一对非同谱图，当它们的特征值不能用根式表达的时候，证明它们等能量是一个非常具有挑战性的问题。但是对于树而言，此问题可借助韦达定理将其转换为证明一个代数方程有唯一的正实根。

Abstract: Let G and G' be a pair of noncospectral graphs. It is a challenge problem to prove G and G' are equienergetic when their eigenvalues cannot be expressed in radicals. But for trees, this problem can be deduced to proving a specific algebraic equation with a positive root by Vieta’s theorem.

1. 引言

设n阶简单图 $G=\left(V,E\right)$ ，其中 $V\left(G\right)=\left\{1,2,\cdots ,n\right\}$ 表示点集， $E\left(G\right)$ 表示边集。 $A={\left[a_{ij}\right]}_{n\times n}$ 表示图G邻接矩阵，其中 $a_{ij}=1$ 当且仅当 $ij\in E\left(G\right)$ ，否则 $a_{ij}=0$ 。 $\varphi \left(G,x\right)=\det \left(xI-A\left(G\right)\right)$ 定义为图G的特征多项式，其中I表示单位矩阵。 $\varphi \left(G,x\right)$ 的根称为图G的特征值。图G特征值的多重集称为G的谱。两个图如果有相同的谱，则成它们同谱。设 ${\lambda }_1>{\lambda }_2>\cdots >{\lambda }_m$ 是图G不同特征值，图G的能量定义为

$\mathcal{E}\left(G\right)={\displaystyle \underset{i=1}{\overset{m}{\sum }}{k}_i\left|{\lambda }_i\right|}$ ，其中 $k_i$ ( $i=1,2,\cdots ,m$ )为特征值 ${\lambda }_i$ 的重数。

李学良，史永堂，Gutman [1] 提出这样一个问题：对于特征值不能用根式表示的非同谱等能量图G和G'，能否用数学的方法证明它们等能量。Miljković等人 [2] 也遇到了这样一个问题，树T₁ (见图1)和树T₂ (见图2)尽管利用数学软件进行数值运算可以确定它们等能量，但是却不能利用数学方法严格证明。对于这个问题的研究，几乎没有文献有所提及，近几年有关图能量的研究几乎都是对能求出图的能量，并借此来构造一系列等能量的图，例如文献 [3] 给出了所有树 $D_{n,k}$ 的特征值和能量计算公式，文献 [4] 探讨了图的算术–几何谱半径和能量在化学应用中的一些应用，文献 [5] 则找出了顶点数介于7~10的等能量连通图及22个顶点以下的等能量化学树，并构造出了一类等能量图。

Figure 1. T₁

图1. T₁

Figure 2. T₂

图2. T₂

在构造等能量的图过程中，不可避免的会出现图的特征值不能用根式表达，因此我们希望找到一种方法能够避开这种问题，从而能够构造一系列的等能量图。现如今我们已经找到一种方法来证明两棵树等能量。这种方法利用特征多项式和韦达定理来确定它们等能量，而不用求它们各自的特征值，这样就规避了树的特征值不能用根式表达而无法求能量的问题，也为后面构造或寻找一系列等能量的树打下基础。

2. 预备知识

定理2.1. (笛卡尔符号法则 [6] )设 $f\left(x\right)=x^n+a_1{x}^{n-1}+\cdots +a_n$ ， $a_i\ne 0,i=1,2,\cdots ,n$ ，那么函数 $f\left(x\right)$ 的正根个数(包含重数)等于 $1,a_1,\cdots ,a_{n-1},a_n$ 中变号的次数。

定理2.2. (零点存在定理 [7] )设函数 $f\left(x\right)$ 在区间 $\left[a,b\right]$ 上连续，且 $f\left(a\right)f\left(b\right)<0$ ，则存在点 $c\in \left(a,b\right)$

成立 $f\left(c\right)=0$ 。

定理2.3. (韦达定理 [8] )设 $f\left(x\right)=x^n+a_1{x}^{n-1}+\cdots +a_n$ 是n阶多项式，对应的根为 $x_1,x_2,\cdots ,x_n$ ，设 ${\sigma }_1={\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_i}$ ， ${\sigma }_2={\displaystyle \underset{1\le i_1<i_2\le n}{\sum }{x}_{i_1}{x}_{i_2}}$ ， $\cdots$ ， ${\sigma }_r={\displaystyle \underset{1\le i_1<i_2<\cdots <i_r\le n}{\sum }{x}_{i_1}{x}_{i_2}\cdots x_{i_r}}$ ， $\cdots$ ， ${\sigma }_n=x_1{x}_2\cdots x_n$ ，那么成立

$-a_1={\sigma }_1,a_2={\sigma }_2,\cdots ,{\left(-1\right)}^i{a}_i={\sigma }_i,\cdots ,{\left(-1\right)}^n{a}_n={\sigma }_n.$

3. 利用特征多项式证明等能量

在证明树等能量之前，我们先给出如下两个定理。

定理3.1. 设 $f\left(x\right)=x^4+a_1{x}^3+a_2{x}^2+a_{3}x+a_4$ ，其中 $a_1,a_3<0$ ， $a_2,a_4>0$ ，则 $f\left(x\right)$ 由4个正根，设为 $x_1,x_2,x_3,x_4$ ，记 $e={\displaystyle \underset{i=1}{\overset{4}{\sum }}\sqrt{x_i}}$ ，那么有

$e^2=-a_1+2\sqrt{a_2-2\sqrt{a_4}+2e\sqrt{-a_3+\sqrt{a_4}\left(e^2+a_1\right)}}$

证明：根据定理2.1可知 $f\left(x\right)$ 有4个正根，设为 $x_1,x_2,x_3,x_4$ ，记 $e={\displaystyle \underset{i=1}{\overset{4}{\sum }}\sqrt{x_i}}$ 。根据定理2.3可得到 ${\sigma }_1={\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_i}=-a_1$ ，， ${\sigma }_3={\displaystyle \underset{1\le i<j<k\le n}{\sum }{x}_i{x}_j{x}_k}=-a_3$ ， ${\sigma }_4=x_1{x}_2{x}_3{x}_4=a_4$ ，那么有

$e^2={\displaystyle \underset{i=1}{\overset{4}{\sum }}{x}_i}+2{\displaystyle \underset{1\le i<j\le 4}{\sum }\sqrt{x_i{x}_j}}={\sigma }_1+2{\displaystyle \underset{1\le i<j\le 4}{\sum }\sqrt{x_i{x}_j}}$

即有 $2{\displaystyle \underset{1\le i<j\le 4}{\sum }\sqrt{x_i{x}_j}}=e^2-{\sigma }_1$ ，进一步有

$\begin{array}{c}{\left({\displaystyle \underset{1\le i<j\le 4}{\sum }\sqrt{x_i{x}_j}}\right)}^2={\displaystyle \underset{1\le i<j\le 4}{\sum }{x}_i{x}_j}+2\left({\displaystyle \underset{1\le i<j<k\le 4}{\sum }\sqrt{x_i{x}_j{x}_k}}\cdot {\displaystyle \underset{i=1}{\overset{4}{\sum }}\sqrt{x_i}}-\sqrt{x_1{x}_2{x}_3{x}_4}\right)\\ ={\sigma }_2-2\sqrt{{\sigma }_4}+2e{\displaystyle \underset{1\le i<j<k\le 4}{\sum }\sqrt{x_i{x}_j{x}_k}}\end{array}$

${\left({\displaystyle \underset{1\le i<j<k\le 4}{\sum }\sqrt{x_i{x}_j{x}_k}}\right)}^2={\displaystyle \underset{1\le i<j<k\le 4}{\sum }{x}_i{x}_j{x}_k}+2\sqrt{x_1{x}_2{x}_3{x}_4}\cdot {\displaystyle \underset{1\le i<j\le 4}{\sum }\sqrt{x_i{x}_j}}={\sigma }_3+\sqrt{{\sigma }_4}\left(e^2-{\sigma }_1\right)$

则 ${\displaystyle \underset{1\le i<j<k\le 4}{\sum }\sqrt{x_i{x}_j{x}_k}}=\sqrt{{\sigma }_3+\sqrt{{\sigma }_4}\left(e^2-{\sigma }_1\right)}$ ，因此

${\displaystyle \underset{1\le i<j\le 4}{\sum }\sqrt{x_i{x}_j}}=\sqrt{{\sigma }_2-2\sqrt{{\sigma }_4}+2e\sqrt{{\sigma }_3+\sqrt{{\sigma }_4}\left(e^2-{\sigma }_1\right)}}$

故有 $e^2={\sigma }_1+2\sqrt{{\sigma }_2-2\sqrt{{\sigma }_4}+2e\sqrt{{\sigma }_3+\sqrt{{\sigma }_4}\left(e^2-{\sigma }_1\right)}}$ ，即

$e^2=-a_1+2\sqrt{a_2-2\sqrt{a_4}+2e\sqrt{-a_3+\sqrt{a_4}\left(e^2+a_1\right)}}$

值得注意的是，如果上述多项式 $f\left(x\right)$ 有一个零根，那么这个多项式就退化为3阶多项式，此时 $a_4=0$ ，上述结论依然成立。

随着多项式次数的增加，运算复杂度也会加大，但是在实际计算过程中，4阶多项式完全能够处理20阶以下的等能量树。因此后面的研究主要是20以下的等能量树的证明。由于树的特征值正负成对出现的，那么它的能量可以看作所有正特征值和的两倍，如果两棵树所有的正特征值的和相等，那么它们一定等能量，在此基础上，如果再删掉它们相同的特征值，保证两棵树不同特征值的和相同，同样可以得到它们的能量相同，基于这个原理，我们给出以下定理。

定理3.2. 设 $f\left(x\right)=x^4+a_1{x}^3+a_2{x}^2+a_{3}x+a_4$ ， $a_1,a_3<0$ ， $a_2,a_4>0$ ， $g\left(y\right)=y^4+{a^{\prime }}_1{y}^3+{a^{\prime }}_2{y}^2+{a^{\prime }}_{3}y+{a^{\prime }}_4$ ， ${a^{\prime }}_1,{a^{\prime }}_3<0$ ， ${a^{\prime }}_2,{a^{\prime }}_4>0$ ， $x_i,y_i\left(i=1,2,3,4\right)$ 分别是 $f\left(x\right),g\left(x\right)$ 的所有非零根。而 $e_1={\displaystyle \underset{i=1}{\overset{4}{\sum }}\sqrt{x_i}}$ ， $e_2={\displaystyle \underset{i=1}{\overset{4}{\sum }}\sqrt{y_i}}$ 满足定理3.1，那么当方程有唯一正实根是 $e_1=e_2$ 的充分条件。

$\{\begin{array}{l}{x}^2=-a_1+2\sqrt{a_2-2\sqrt{a_4}+2x\sqrt{-a_3+\sqrt{a_4}\left(x^2+a_1\right)}}\\ x^2=-{a^{\prime }}_1+2\sqrt{{a^{\prime }}_2-2\sqrt{{a^{\prime }}_4}+2x\sqrt{-{a^{\prime }}_3+\sqrt{{a^{\prime }}_4}\left(x^2+{a^{\prime }}_1\right)}}\end{array}$ (1)

现在我们可以根据以下步骤来证明树T和树T'等能量：

① 消去树T和树T'特征多项式的最大公因式，剩下的多项式一定是偶次，分别用 $f\left(x^2\right)$ 和 $g\left(x^2\right)$ 表示；

② 令 $t=x^2$ ，得到多项式 $f\left(t\right)$ 和 $g\left(t\right)$ ，如果定理3.2成立，那么可以确定 $\mathcal{E}\left(T\right)=\mathcal{E}\left(T^{\prime }\right)$ 。

步骤①的目的是消去树T和树T'的相同特征值，保留剩下不同的特征值；由于剩下的特征值一定是正负成对出现的，而步骤②的目的就是只考虑所有正特征值的和，只要正特征值的和相等，那么树T和树T'必定等能量。下面我们给出一个例子来具体说明这个过程。

4. 应用

例1：证明树T₁ (见图1)和树T₂ (见图2)等能量。

证明：树T₁和树T₂的特征多项式分别为

$\varphi \left(T_1,x\right)=x^2\left(x^2-3\right)\left(x^4-5x^2+5\right)\left(x^8-7x^6+14x^4-8x^2+1\right)$

$\varphi \left(T_2,x\right)=\left(x^8-8x^6+14x^4-7x^2+1\right)\left(x^8-7x^6+14x^4-8x^2+1\right)$

最大公因式为 $x^8-7x^6+14x^4-8x^2+1$ ，消去最大公因式后得到树T₁和树T₂剩下的多项式为

$f\left(x^2\right)=x^2\left(x^2-3\right)\left(x^4-5x^2+5\right)$

$g\left(x^2\right)=x^8-8x^6+14x^4-7x^2+1$

令 $t=x^2$ ，得到

$f\left(t\right)=t^4-8t^3+10t^2-15t$

$g\left(t\right)=t^4-8t^3+14t^2-7t+1$

根据定理2.1可知， $f\left(t\right)$ 和 $g\left(t\right)$ 的所有根均为正数，不妨设 $t_1,t_2,t_3,0$ 和 $t_4,t_5,t_6,t_7$ 分别为 $f\left(t\right)$ 和 $g\left(t\right)$ 的所有根，记 $e_1={\displaystyle \underset{i=1}{\overset{3}{\sum }}\sqrt{t_i}}$ ， $e_2={\displaystyle \underset{i=4}{\overset{7}{\sum }}\sqrt{t_i}}$ ，下面证明方程(2)有唯一正实根。

$\{\begin{array}{l}{x}^2=8+2\sqrt{20-2\sqrt{0}+2x\sqrt{15+\sqrt{0}\left(x^2-8\right)}}\\ x^2=8+2\sqrt{14-2\sqrt{1}+2x\sqrt{7+\sqrt{1}\left(x^2-8\right)}}\end{array}$ (2)

化简得到

$x\sqrt{x^2-1}-\sqrt{15}x-4=0$

构造辅助函数 $h\left(x\right)=x\sqrt{x^2-1}-\sqrt{15}x-4=\frac{x^2-16}{\sqrt{1-\frac{1}{x^2}}+\sqrt{\frac{15}{x^2}}}-4,x\ge 1$ ，显然当 $1\le x\le 4$ 时，有 $h\left(x\right)<0$ ，并且 $\underset{x\to +\infty }{\lim }h\left(x\right)=+\infty$ ，根据定理2.2可知至少存在一点 $c\in \left(4,+\infty \right)$ ，成立 $h\left(c\right)=0$ 。另一方面，有

$h^{\prime }\left(x\right)=\sqrt{x^2-1}-\sqrt{15}+\frac{x^2}{\sqrt{x^2-1}}=\frac{x^2-16}{\sqrt{x^2-1}+\sqrt{15}}+\frac{x^2}{\sqrt{x^2-1}}.$

即对 $\forall x\in \left(4,+\infty \right)$ ，成立 $h^{\prime }\left(x\right)>0$ ，即 $h\left(x\right)$ 在 $\left(4,+\infty \right)$ 上严格单调增加，故 $h\left(x\right)$ 在 $\left(4,+\infty \right)$ 上存在唯一的正实根，那么定理3.2成立，因此 $\mathcal{E}\left(T_1\right)=\mathcal{E}\left(T_2\right)$ 。

例2：证明树T₃ (见图3)和树T₄ (见图4)等能量。

Figure 3. T₃

图3. T₃

Figure 4. T₄

图4. T₄

证明：树T₃和树T₄的特征多项式分别为

$\varphi \left(T_3,x\right)=\left(x-1\right)x^5\left(x+1\right)\left(x^2-3\right)\left(x^2-2\right)\left(x^8-12x^6+38x^4-34x^2+9\right)$

$\varphi \left(T_4,x\right)=\left(x-1\right)x^5\left(x+1\right)\left(x^2-3\right)\left(x^2-2\right)\left(x^8-12x^6+44x^4-46x^2+4\right)$

最大公因式为 $\left(x-1\right)x^5\left(x+1\right)\left(x^2-3\right)\left(x^2-2\right)$ ，消去最大公因式后得到树T₃和树T₄剩下的多项式为

$f\left(x^2\right)=x^8-12x^6+38x^4-34x^2+9$

$g\left(x^2\right)=x^8-12x^6+44x^4-46x^2+4$

令 $t=x^2$ ，得到

$f\left(t\right)=t^4-12t^3+38t^2-34t+9$

$g\left(t\right)=t^4-12t^3+44t^2-46t+4$

根据定理2.1可知， $f\left(t\right)$ 和 $g\left(t\right)$ 的所有根均为正数，不妨设 $t_1,t_2,t_3,t_4$ 和 $t_5,t_6,t_7,t_8$ 分别为 $f\left(t\right)$ 和 $g\left(t\right)$ 的所有根，记 $e_1={\displaystyle \underset{i=1}{\overset{4}{\sum }}\sqrt{t_i}}$ ， $e_2={\displaystyle \underset{i=5}{\overset{8}{\sum }}\sqrt{t_i}}$ ，下面证明方程(3)有唯一正实根。

$\{\begin{array}{l}{x}^2=12+2\sqrt{38-2\sqrt{9}+2x\sqrt{34+\sqrt{9}\left(x^2-12\right)}}\\ x^2=12+2\sqrt{44-2\sqrt{4}+2x\sqrt{46+\sqrt{4}\left(x^2-12\right)}}\end{array}$ (3)

化简得到

$x\sqrt{3x^2-2}-x\sqrt{2x^2+22}-4=0$

构造辅助函数 $h\left(x\right)=x\sqrt{3x^2-2}-x\sqrt{2x^2+22}-4=\frac{x^2-24}{\sqrt{3-\frac{2}{x^2}}+\sqrt{2+\frac{22}{x^2}}}-4,x\ge \sqrt{\frac{2}{3}}$ ，显然当 $\sqrt{\frac{2}{3}}\le x\le 2\sqrt{6}$ 时，有 $h\left(x\right)<0$ ，并且 $\underset{x\to +\infty }{\lim }h\left(x\right)=+\infty$ ，根据定理2.2可知至少存在一点 $c\in \left(2\sqrt{6},+\infty \right)$ ，成立 $h\left(c\right)=0$ 。另一方面，有

$\begin{array}{c}{h}^{\prime }\left(x\right)=\sqrt{3x^2-2}-\sqrt{2x^2+22}+\left(\frac{3x^2}{\sqrt{3x^2-2}}-\frac{2x^2}{\sqrt{2x^2+22}}\right)\\ =\frac{x^2-24}{\sqrt{3x^2-2}+\sqrt{2x^2+22}}+\frac{x^2}{\sqrt{3x^2-2}\sqrt{2x^2+22}}\frac{6x^2+206}{\sqrt{3x^2-2}+\sqrt{2x^2+22}}\end{array}$

即对 $\forall x\in \left(2\sqrt{6},+\infty \right)$ ，成立 $h^{\prime }\left(x\right)>0$ ，即 $h\left(x\right)$ 在 $\left(2\sqrt{6},+\infty \right)$ 上严格单调增加，故 $h\left(x\right)$ 在 $\left(2\sqrt{6},+\infty \right)$ 上存在唯一的正实根，那么定理3.2成立，因此 $\mathcal{E}\left(T_3\right)=\mathcal{E}\left(T_4\right)$ 。