1. 引言
将普通图的每条边标上符号(+或者−),所得到的图称为符号图。符号图最早是在1953年Harary [1] 提出的。设
为n阶符号图,其中
表示顶点集,
表示边集,
是顶点集的二元子集,
为符号函数,
称为符号图
的底图,因此也可将符号图记为
。
对任意的顶点
,记
为顶点i的度,
和
分别表示i的正顶点度和负顶点度(即分别表示与顶点i相连的正边个数和负边个数),易知
。网度
。对任意的顶点i和j,若i和j相邻,记为
;若称i和j不相邻,记为
;若i和j通过正边相邻,记为
;若i和j通过负边相邻,记为
。
表示与顶点i相邻的顶点集合,
表示与顶点i通过正边相邻的顶点集合,
表示与顶点i通过负边相邻的顶点集合。关于符号图的其它记号,读者可以参考 [2] 。
符号图
的网拉普拉斯矩阵定义为
,其中
为符号图
的邻接矩阵,
为符号图
的网度对角矩阵,
,
。
在符号图谱理论中,邻接矩阵和拉普拉斯矩阵受到了广泛的关注。与之相比,网拉普拉斯矩阵(net Laplacian matrix)是近几年才出现的,关于它的结果很少。(本文将net Laplacian matrix直接翻译成网拉普拉斯矩阵。注意:由于该矩阵是近几年才开始被陆陆续续进行研究,并未统一名称)。文献 [3] [4] 指出了符号图网拉普拉斯特征值在控制理论当中的应用。文献 [5] 给出了更多关于
的谱的详细介绍,同时通过对
谱的详细分析,强调了用网拉普拉斯代替符号图的拉普拉斯的一些优点,它们大多是基于这样一个事实,即关于(无符号)图的拉普拉斯的一些结果可以推广到网拉普拉斯上,但不能推广到符号图拉普拉斯上。若一些结果对网拉普拉斯成立,那么它也在图的拉普拉斯的特殊情况下成立。符号图网拉普拉斯矩阵在控制理论当中有着重要的应用,尤其是符号图网拉普拉斯谱。由于近几年才开始陆续研究符号图网拉普拉斯矩阵,因此关于符号图网拉普拉斯最大特征值的上界相关结论很少。下面给出了已知的上界。记
为
的最大特征值。
在2021年,Ramezani和Stanić [6] 给出了符号图网拉普拉斯最大特征值的上界:
, (1.1)
其中
,
,
;
以及
。 (1.2)
下面将会给出符号图网拉普拉斯最大特征值的一个上界以及推导过程,在这一过程中需要使用一些相关的引理。
在符号图中把边符号的乘积为正的路径称为正路径,边符号的乘积为负的路径称为负路径。
表示从顶点i到顶点j长为l的正路径的个数,
表示从顶点i到顶点j长为l的负路径的个数。
引理1.1 ( [7] )
为n阶符号图,
为符号图
的邻接矩阵,则矩阵
的第
项为
.
引理1.2 若
为n阶符号图,
为符号图
的邻接矩阵,x为n维列向量,
是x中最大的分量且
,则
证明 由引理1.1可知
对等式右边的每一项分别进行放缩,可得
同理可得:
最后将每一项进行相加,可得
注:引理1.2借鉴了文献 [8] 中定理3.3的证明过程。
2. 符号图网拉普拉斯最大特征值的一个新上界
由于符号图网拉普拉斯矩阵的特征值(尤其是最大特征值)在控制理论当中有着重要的应用,本文研究了符号图网拉普拉斯最大特征值的上界,给出了网拉普拉斯最大特征值的一个新上界。
引理1.3 设
为
阶符号图,
为
的网拉普拉斯最大特征值,则
(1.3)
其中
,
,
。
.
证明 令
是矩阵
的属于特征值
的特征向量,设
为x中绝对值最大的分量.不失一般性,假设
。
由
,
,
,可得
(1.4)
等式
两边同时左乘
,得到
,将
代入且取第i个分量,可得
(1.5)
将(1.4)式的两边同时乘以
代入(1.5)式,可得
对任意顶点j,由于
,则
,因此
,
。
再由引理1.2可得
令
,则有
因为
,所以
又因为
,取
,因此
取所有顶点的最大值,可得
□
3. 上界的比较
上一节给出了符号图网拉普拉斯最大特征值的一个新上界,下面将该上界与已知的上界进行比较。首先将本文的上界(1.3)与上界(1.2)进行比较。上界(1.3)与上界(1.2)相比,相差了
,观察到
因此本文的上界(1.3)改进上界(1.2)。
接下来将上界(1.3)与上界(1.1)进行比较。下面通过具体例子说明对于某些符号图而言,本文的上界(1.3)要优于上界(1.1)。
令
为上图1所示的符号图
的网拉普拉斯矩阵,由上图1可知
,
通过Maple计算可得
。利用上界(1.1)计算符号图
的网拉普拉斯最大特征值的上界为
,利用本文的上界(1.3)计算
的网拉普拉斯最大特征值的上界为
,从而对于符号图
来说本文的上界(1.3)优于上界(1.1)。