等能量树的新判定方法.pdf

Operations Research and Fuzziology 运筹与模糊学运筹与模糊学,2024,14(1),921-927 Published Online February 2024 in Hans.https:/www.hanspub.org/journal/orf https:/doi.org/10.12677/orf.2024.141085 文章引用文章引用:苏柯,申悦.等能量树的新判定方法J.运筹与模糊学,2024,14(1):921-927.DOI:10.12677/orf.2024.141085 等能量树的新判定方法等能量树的新判定方法 苏苏 柯柯，申申 悦悦 长安大学理学院，陕西 西安 收稿日期：2023年12月15日；录用日期：2024年1月5日；发布日期：2024年2月29日 摘摘 要要 设设G和和G是一对非同谱图，当它们的特征值不能用根式表达的时候，证明它们等能量是一个非常具有挑战是一对非同谱图，当它们的特征值不能用根式表达的时候，证明它们等能量是一个非常具有挑战性的问题。但是对于树而言，此问题可借助韦达定理将其转换为证明一个代数方程有唯一的正实根。性的问题。但是对于树而言，此问题可借助韦达定理将其转换为证明一个代数方程有唯一的正实根。关键词关键词 图能量，等能量树，根式图能量，等能量树，根式 A New Criterion for Determining Equienergetic Trees Ke Su,Yue Shen School of Science,Changan University,Xian Shaanxi Received:Dec.15th,2023;accepted:Jan.5th,2024;published:Feb.29th,2024 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 Vietas theorem.Keywords Graph Energy,Equienergetic Trees,Radicals Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).苏柯，申悦 DOI:10.12677/orf.2024.141085 922 运筹与模糊学 http:/creativecommons.org/licenses/by/4.0/1.引言引言 设 n 阶简单图(),GV E=，其中()1,2,V Gn=表示点集，()E G表示边集。ijn nAa=表示图 G邻接矩阵，其中1ija=当且仅当()ijE G，否则0ija=。()()(),detG xxIA G=定义为图 G 的特征多项式，其中 I 表示单位矩阵。(),G x的根称为图 G 的特征值。图 G 特征值的多重集称为 G 的谱。两个图如果有相同的谱，则成它们同谱。设12m是图 G 不同特征值，图 G 的能量定义为()1miiiGk=，其中ik(1,2,im=)为特征值i的重数。李学良，史永堂，Gutman 1提出这样一个问题：对于特征值不能用根式表示的非同谱等能量图 G和 G，能否用数学的方法证明它们等能量。Miljkovi 等人2也遇到了这样一个问题，树 T1(见图 1)和树T2(见图 2)尽管利用数学软件进行数值运算可以确定它们等能量，但是却不能利用数学方法严格证明。对于这个问题的研究，几乎没有文献有所提及，近几年有关图能量的研究几乎都是对能求出图的能量，并借此来构造一系列等能量的图，例如文献3给出了所有树,n kD的特征值和能量计算公式，文献4探讨了图的算术几何谱半径和能量在化学应用中的一些应用，文献5则找出了顶点数介于 710 的等能量连通图及 22 个顶点以下的等能量化学树，并构造出了一类等能量图。Figure 1.T1 图图 1.T1 Open AccessOpen Access苏柯，申悦 DOI:10.12677/orf.2024.141085 923 运筹与模糊学 Figure 2.T2 图图 2.T2 在构造等能量的图过程中，不可避免的会出现图的特征值不能用根式表达，因此我们希望找到一种方法能够避开这种问题，从而能够构造一系列的等能量图。现如今我们已经找到一种方法来证明两棵树等能量。这种方法利用特征多项式和韦达定理来确定它们等能量，而不用求它们各自的特征值，这样就规避了树的特征值不能用根式表达而无法求能量的问题，也为后面构造或寻找一系列等能量的树打下基础。2.预备知识预备知识 定理定理 2.1.(笛卡尔符号法则6)设()11nnnfxxa xa=+，0,1,2,iina=，那么函数()fx的正根个数(包含重数)等于111,nnaaa中变号的次数。定理定理 2.2.(零点存在定理7)设函数()fx在区间,a b上连续，且()()0f a f b，则存在点(),ca b 成立()0f c=。定理定理 2.3.(韦达定理8)设()11nnnfxxa xa=+是 n 阶多项式，对应的根为12,nx xx，设11niix=，121221iiiinx x=，12121rrriiiiiinx xx=，12nnx xx=，那么成立()()1122,1,1.iniinnaaaa=3.利用特征多项式证明等能量利用特征多项式证明等能量 在证明树等能量之前，我们先给出如下两个定理。定理定理 3.1.设()4321234fxxa xa xa xa=+，其中13,0a a，则()fx由 4 个正根，设为1234,x xx x，记41iiex=，那么有 苏柯，申悦 DOI:10.12677/orf.2024.141085 924 运筹与模糊学 ()22124341222eaaaeaaea=+证明：根据定理 2.1 可知()fx有 4 个正根，设为1234,x xx x，记41iiex=。根据定理 2.3 可得到111niixa=，221iij njx xa =，133iinjjkkx xax=，341244x x x xa=，那么有 4211141422iijijiijijexx xx x=+=+即有21142ijijx xe =，进一步有 24123414141412414222ijijijkiijijij kiijkij kx xx xx x xxx x x xex x x =+=+()2212343411414142ijkijkijij kij kijx x xx x xx x x xx xe =+=+则()234114ijkij kx x xe =+，因此()2243411422ijijx xee =+故有()22124341222eee=+，即()22124341222eaaaeaaea=+值得注意的是，如果上述多项式()fx有一个零根，那么这个多项式就退化为3阶多项式，此时40a=，上述结论依然成立。随着多项式次数的增加，运算复杂度也会加大，但是在实际计算过程中，4 阶多项式完全能够处理20 阶以下的等能量树。因此后面的研究主要是 20 以下的等能量树的证明。由于树的特征值正负成对出现的，那么它的能量可以看作所有正特征值和的两倍，如果两棵树所有的正特征值的和相等，那么它们一定等能量，在此基础上，如果再删掉它们相同的特征值，保证两棵树不同特征值的和相同，同样可以得到它们的能量相同，基于这个原理，我们给出以下定理。定理定理 3.2.设()4321234fxxa xa xa xa=+，13,0a a，()4321234g yya ya ya ya=+，13,0a a，()1,2,3,4iix y i=分别是()(),fxg x的所有非零根。而411iiex=，124iiey=满足定理 3.1，那么当方程有唯一正实根是12ee=的充分条件。()()2212434122124341222222xaaaxaaxaaaaaaxxxa=+=+(1)现在我们可以根据以下步骤来证明树 T 和树 T等能量：消去树 T 和树 T特征多项式的最大公因式，剩下的多项式一定是偶次，分别用()2fx和()2g x表苏柯，申悦 DOI:10.12677/orf.2024.141085 925 运筹与模糊学 示；令2tx=，得到多项式()f t和()g t，如果定理 3.2 成立，那么可以确定()()TT=。步骤的目的是消去树 T 和树 T的相同特征值，保留剩下不同的特征值；由于剩下的特征值一定是正负成对出现的，而步骤的目的就是只考虑所有正特征值的和，只要正特征值的和相等，那么树 T 和树 T必定等能量。下面我们给出一个例子来具体说明这个过程。4.应用应用 例 1：证明树 T1(见图 1)和树 T2(见图 2)等能量。证明：证明：树 T1和树 T2的特征多项式分别为()()()()224286421,35571481T xxxxxxxxx=+()()()864284226,8147171481T xxxxxxxxx=+最大公因式为864271481xxxx+，消去最大公因式后得到树 T1和树 T2剩下的多项式为()()()22242355f xxxxx=+()2864281471g xxxxx=+令2tx=，得到()43281015f ttttt=+()43281471g ttttt=+根据定理 2.1 可知，()f t和()g t的所有根均为正数，不妨设123,0t t t和4567,t t t t分别为()f t和()g t的所有根，记311iiet=，724iiet=，下面证明方程(2)有唯一正实根。()()222282 202 02150882 142 12718xxxxxx=+=+(2)化简得到 211540 x xx=构造辅助函数()22221611544,11151xh xx xxxxx=+，显然当14x时，有()0h x，即()h x在()4,+上严格单调增加，故()h x在()4,+上存在唯一的正实根，那么定理 3.2 成立，因此()()12TT=。例 2：证明树 T3(见图 3)和树 T4(见图 4)等能量。苏柯，申悦 DOI:10.12677/orf.2024.141085 926 运筹与模糊学 Figure 3.T3 图图 3.T3 Figure 4.T4 图图 4.T4 证明：证明：树 T3和树 T4的特征多项式分别为()()()()()()52286423,11321238349T xxxxxxxxxx=+()()()()()()52286424,11321244464T xxxxxxxxxx=+最大公因式为()()()()5221132xxxxx+，消去最大公因式后得到树 T3和树 T4剩下的多项式为()286421238349f xxxxx=+()286421244464g xxxxx=+令2tx=，得到()4321238349f ttttt=+()4321244464g ttttt=+苏柯，申悦 DOI:10.12677/orf.2024.141085 927 运筹与模糊学 根据定理 2.1 可知，()f t和()g t的所有根均为正数，不妨设1234,t t t t和5678,t t t t分别为()f t和()g t的所有根，记411iiet=，825iiet=，下面证明方程(3)有唯一正实根。()()2222122 382 9234912122 442 4246412xxxxxx=+=+(3)化简得到 223222240 xxxx+=构造辅助函数()222222423222244,322232xh xxxxxxxx=+=+，显然当 22 63x时，有()0h x，即()h x在()2 6,+上严格单调增加，故()h x在()2 6,+上存在唯一的正实根，那么定理 3.2 成立，因此()()34TT=。参考文献参考文献 1 Li,X.,Shi,Y.and Gutman,I.(2012)Graph Energy.Springer,New York.https:/doi.org/10.1007/978-1-4614-4220-2 2 Miljkovi,O.,Furtula,B.,Radenkovic,S.,et al.(2009)Equienergetic and Almost-Equienergetic Trees.Match Com-munications in Mathematical and in Computer Chemistry,61,451-461.3 Xu,H.and Yan,W.(2022)On Eigenvalues and the Energy of Dendrimer Trees.Applied Mathematics and Computa-tion,424,Article ID:127051.https:/doi.org/10.1016/j.amc.2022.127051 4 Dorel,L.and Openhaim,E.(2022)Developing Mathematical Proof:Back to the Future with Vieta Extended Theorem.Creative Education,13,3298-3310.https:/doi.org/10.4236/ce.2022.1310211 5 Zheng,R.,Su,P.and Jin,X.(2023)Arithmetic-Geometric Matrix of Graphs and Its Applications.Applied Mathemat-ics and Computation,442,Article ID:127764.https:/doi.org/10.1016/j.amc.2022.127764 6 Wang,X.(2004)A Simple Proof of Descartess Rule of Signs.The American Mathematical Monthly,111,Article No.525.https:/doi.org/10.1080/00029890.2004.11920108 7 Zorich,V.A.and Paniagua,O.(2016)Mathematical Analysis II.Springer,Berlin.https:/doi.org/10.1007/978-3-662-48993-2 8 Stankovic,I.,Milosevic,M.and Stevanovic,D.(2009)Small and Not so Small Equienergetic Graphs.Match,61,Ar-ticle No.443.