图的ABC矩阵的Sachs定理与能量

常彩冰 邓 波,2),3),4),5) 邓梓健 付 凤 尹浩佳

(1) 青海师范大学数学与统计学院,810008,西宁； 2) 藏文信息处理教育部重点实验室，810008, 西宁；3) 青海省藏文信息处理与机器翻译重点实验室,810008,西宁； 4)高原科学与可持续发展研究院, 810008,西宁；5)广东石油化工学院理学院，525000，广东茂名 )

1 引 言

对简单图G, 分别用E(G)和V(G)来表示图G的边集和顶点集.记V(G)={v1,v2,…,vn}, 则图G的邻接矩阵A(G)[1]可以定义为一个n阶方阵，其中A(G)中的元素aij满足如下条件：

(1)

(2)

Ω(G)=AD-1+D-1A-2D-1AD-1，

其中A和D分别是图G的邻接矩阵和度对角矩阵.

本文将继续对ABC矩阵进行研究, 通过在有向图与无向图之间建立一个对应关系, 给出一个图G的ABC矩阵对应的特征多项式的各项系数与图G的结构之间的关系,然后根据所给的图确定特征多项式的系数，从而给出对应的特征多项式及其ABC矩阵的能量对应的积分公式.利用能量积分公式可以比较两个图的ABC矩阵的能量.

2 图的ABC矩阵的Sachs定理

如果一个图的每一个分支都是圈, 则这个图称为是线性的[10].基于任意有向图和无向图的邻接矩阵,易知如下的定理1成立.

定理1[11]设PD(λ)=|λI-A(D)|=λn+a1λn-1+…+an, 是任意有向图D的特征多项式, 则

(3)

其中li是图D中所有恰有i个点的线性有向子图L的集合，p(L)表示L中的分支的个数(即L中含有的有向圈的个数).

一个图称为基本图, 如果该图是图K2或者任意长度的圈Cq(q≥1,当q=1时是一个环). 一个图U称为基础图, 如果它的每一个分支都是由基本图构成.

定理2[11]设PG(λ)=|λI-A(G)|=λn+a1λn-1+…+an,对任意无向图G的特征多项式,有

(4)

其中p(U)和c(U)分别表示U中含有的分支个数和圈的个数; li是图G中所有恰有i个点的基础子图U的集合.

引理1设G=(V,E)是一个以V(G)为顶点集,E(G)为边集的图， 其中|V(G)|=n. 图G有一个生成子图H且H是由两两点不交的圈构成的, 当且仅当存在一个圈置换P使得P中的不交的子圈置换与生成子图H的不交圈之间形成一一对应.

取每个圈Ci的点对应的下标构成的一个子圈置换, 则这些子圈置换的乘积即为所求的圈置换P, 即

此时得到的圈置换P中的子圈置换与生成子图H中的圈形成一一对应, 故必要性成立.

然后证明充分性. 如果存在圈置换P, 不妨令P表示成如下形式:

那么可以根据P中子圈置换的顺序构造k个圈, 使得每个圈的标号如下：

这样的圈显然存在, 且构造出来的每个圈Ci与圈置换P中的子圈置换一一对应.

此时可得一个线性子图H, 其中H是由这些两两不交的圈C1,C2,…,Ck构成的. 对于图G, 如果线性子图H是图G的生成子图, 则图G即为满足条件的图, 即图G中有一个生成子图H, 且H由两两点不交的圈构成的.

引理1说明, 对于一个圈置换P, 存在一个包含图G所有点的两两不交圈的并与之对应(例如线性生成子图H). 相反地, 对于每一个线性生成子图H, 也都会存在一个圈置换P与之对应. 例如, 有向图D0(图1)含有线性生成子图H={C1,C2}, 其中C1={v1,v2,v3,v4},C2={v5,v6,v7}. 则存在一个圈置换P=(1234)(567)，使得子圈置换P1=(1234)和P2=(567)分别与线性生成子图H中的两个圈C1和C2一一对应.

图1 有向图D0

注1令I(P)和e(P)分别表示上面引理1 中所给的圈置换P的反序数和偶子圈置换(可以分解成偶数个对换的乘积的子圈置换)的个数, 则有I(P)≡e(P)(mod2). 由引理1知, 圈置换P中的每一个偶子圈置换都对应着线性生成子图H中的一个偶圈, 故圈置换P的偶子圈置换的个数与线性生成子图H中偶圈的个数相同. 因此,I(P)≡e(H)(mod2), 其中e(H)是线性生成子图H中的偶圈的个数.

其中vi,vj∈V(D),di是指点vi在有向图中的入度与出度之和, 即di(v)=di+(v)+di-(v).

接下来,将证明关于有向图D的ABC 矩阵的Sachs 定理.

定理3设 Ω(D)=(ωij)n×n是有向图D的ABC矩阵，假设 Ω(D)对应的特征多项式为

PD(λ)=|λI-Ω(D)|=λn+a1λn-1+…+an, 则对应的系数ai满足

(5)

其中ξi是有向图D中所有恰有i个点的线性有向子图H的集合,A(H)是线性有向子图H中的弧集,p(H)表示H中的分支个数(即H中包含的圈的个数).

证首先考虑最后一项系数an, 即

an=PD(0)=(-1)n|Ω(D)|=(-1)n|(ωij)n×n|.

根据行列式的定义, 展开得

SP=(-1)n+I(P)ω1i1ω2i2…ωnin,

则SP≠0当且仅当所有的弧(1,i1),(2,i2),…,(n,in)都包含在A(D)中. 由于对于任意非单位置换都能表示成若干不相交的子圈置换的乘积, 且表示方法唯一, 故置换P可以表示成若干不相交子圈置换的乘积. 由引理1知, 置换P中包含的子圈置换与线性子图H中的圈一一对应. 由上面的注1可知I(P)≡e(H)(mod2),其中e(H)是H中所包含的偶圈的个数，因此

显然,n+e(H)≡p(H)(mod2)，故可得

例1考虑有向图D1(图2)的ABC矩阵对应的特征多项式. 由定理3可算出D1的ABC矩阵的对应特征多项式的系数分别为

图2 有向图D1

则D1的ABC矩阵对应的特征多项式为

现在考虑任意无向图G及其对应的ABC矩阵的系数定理. 如果图G是一个无向图, 可以把图G考虑成有向图G':G中所有的边(不是环)都对应成图G'中的一个有向2-圈(长度为2的圈),G中的每一个无向圈都对应成G'中的一对方向相反且长度相同的有向圈. 因此, 定理3可以推广到无向图.

定理4设Ω(G)=(ωij)n×n是无向图G的ABC矩阵. 设Ω(G)对应的特征多项式为

PG(λ)=|λI-Ω(G)|=λn+a1λn-1+…+an, 则对应的系数ai满足

(6)

其中li是无向图G中所有恰好有i个点的基础子图L的集合,E(L)是基础子图L中的边的集合,C(L)表示L中的圈的集合.p(L)和c(L)分别表示L中的分支个数和L中包含的圈的个数.

证给定基础子图L中的任意一条边e=vivj(且e不在L中的圈上), 则e对应于线性有向子图H中的一个2-圈c2=vivjvi,易知

类似地, 对于任意L中圈上的边e=vivj, 每条边对应一个有向2-圈c2=vivjvi, 因此,c(L)中的每个圈都对应着线性有向子图H中的两个方向相反且点数相同的有向圈. 对于每个恰有i基础子图的L∈li,都对应着线性有向子图H中的 2c(L)个有向圈. 故根据定理3可知结论成立.

例2考虑无向图G1(图3)的 ABC矩阵对应的特征多项式. 由定理4可算出G1的ABC矩阵的对应特征多项式的系数分别为

图3 无向图G1

则G1的 ABC 矩阵对应的特征多项式为

根据定理4可得到如下推论1.

推论1设图G是任意一个具有n顶点的树, Ω(G)=(ωij)n×n是图G的 ABC 矩阵. 设Ω(G)对应的特征多项式为PG(λ)=|λI-Ω(G)|=λn+a1λn-1+…+an, 则对应的特征多项式系数表达式为

(7)

其中l2i是无向图G中所有恰有2i个点的匹配的集合,E(L)是匹配L中的边的集合,p(L) 表示匹配集L中的边数.

3 关于图G的ABC矩阵Ω(G)的能量积分公式

在这部分,将利用Ω(G)的特征多项式给出图G的ABC矩阵的能量的积分表示形式.由于此积分形式只含有特征多项式的系数,所以利用这个积分公式可以直接计算出ABC矩阵的能量, 从而可以比较两个图的ABC矩阵能量的大小.

定理5设G为任意n个顶点的图, 其对应的ABC矩阵为Ω(G),并且PG(λ)为Ω(G)的特征多项式, 则矩阵Ω(G)的能量积分公式为

(8)

定理6设图G的ABC矩阵为Ω(G)，令PG(λ)=λn+a1λn-1+…+an为矩阵Ω(G)的特征多项式, 则矩阵Ω(G)的能量积分公式的另一种表示形式为

(9)

给定图G, 分别令b2k(G)=|a2k(G)|,b2k+1(G)=|a2k+1(G)|.如果图G是二部图, 则其ABC矩阵Ω(G)的特征多项式为

结合定理6和二部图的ABC矩阵Ω(G)的特征多项式, 可以得到关于二部图G的ABC矩阵能量积分公式.

(10)

给定两个二部图G1和G2, 定义它们之间的一个拟序关系≤. 对于所有的正整数k, 如果b2k(G1)≤b2k(G2),则称G1≤G2, 其中b2k(G1),b2k(G2)分别是ABC矩阵Ω(G1) 和Ω(G2)的特征多项式的系数. 如果至少存在一个k, 使得不等号严格成立, 即存在一个k，使得b2k(G1)

定理8设二部图G1和G2对应的ABC矩阵分别为Ω(G1)和Ω(G2). 若G1

4 结 语

若图G为二部图, 则其能量积分公式的形式为

利用上述积分公式可以比较两个二部图的ABC能量.