含三个圈的本原不可幂定号有向图的基

王 宁,邵燕灵

(中北大学数学系,山西太原030051)

1 引 言

非负矩阵的组合理论是研究那些仅依赖于矩阵的零位模式,而与本元素的数值无关的性质,它与图的某些性质有密切联系,在信息科学、通信网络、计算机科学等许多方面有具体的应用背景.上世纪年代以来,有关本原矩阵 (本原有向图)的本原指数的研究进展非常迅速,许多问题已经圆满解决.

定义1[1]如果 n阶有向图D是某个n阶本原矩阵的伴随有向图,则称D为n阶本原有向图,简称n阶本原图.称A的本原指数ν(A)为本原有向图D的本原指数,记为ν(D).

本原指数的研究最早开始于1950年Wielandt的工作,给出了n阶本原指数的一般性上界

1964年,Dulmage和M endelsohn创造性的运用有向图理论,得出了 n阶本原指数的一般性上界的另一种形式

其中s是A的伴随有向图D(A)的最小圈长.

概括起来,对ν(A)的研究主要集中于以下四个方面:

1)对ν(A)上界的估计,称为M I问题 (Maximun index).

2)对ν(A)指数集的刻划,称为IS问题 (Set of indicies).

3)极矩阵集合的描述,称为EM问题 (Extremal matrix).

4)具有指数ν0的某一类本原矩阵集合的描述,称为M S问题 (Set of matrices).

本文主要是利用图论和矩阵理论的方法,对含有三个圈的本原不可幂定号有向图的基进行了研究.通过运用对图的特点和规律进行分析的方法,即有两个圈长度相同,且都与第三个圈长度不同.首先通过利用有关本原不可幂定号有向图的引理及定义得到基的上界再运用反证法并综合运用 Frobenius集、本原指数、“异圈对”、SSSD途径、歧义指数、图的直径等相关理论知识,讨论了在这两类图中是否存在所需的SSSD途径对,从而得出了含有三个圈的本原不可幂定号有向图的基的精确值.

2 基本概念

设D是有向图 (允许有环但不能有重复弧),将D中的每条弧标记为1或-1所得到的图称为定号有向图.定号有向图D中的一条途径W是由一系列的弧e1,e2,…,ek组成的,并且ei的终点与ei+1的始点相同 (i=1,2,…,k-1).途径W中弧的条数称为是途径W的长度,记为l(W).途径W的符号定义为记为sgn W.

定义2[2]设D是一个有向图,如果存在一个正整数k,使得 D中任意一对顶点νi和νj(可以相同)都有从νi到νj的长为k的途径,则称 D是本原的,最小的 k就是D的本原指数,记作exp(D).

定义3[2]设 D是一个本原有向图,对于νi∈D,存在正整数 m,使得对任意 t≥m,从νi到D中任意一点都有长为t的途径,满足上述条件的最小的 m就是νi的点指数,记作expD(νi).

定义4[3]在定号有向图中的两条途径W1和W2,如果它们有相同的起点、终点、长度,但有不同的符号,则称为SSSD途径对.

定义5[3]设 S是定号有向图,如果s中不含SSSD途径对,则称 S是可幂的;否则,称 S是不可幂的.

定义6[4]设S是一个本原不可幂定号有向图,存在正整数l,使得对任意正整数 t≥l,及 S中任意顶点νi和νj(可以相同),从νi到νj都有长为t的SSSD途径对,则称最小的 l是定号有向图S的基,记作l(S).

3 预备知识

引理1[5-7]如果S是一个本原定号有向图,那么S是不可幂的充分必要条件是S S中存在一对长度分别为 p1和 p2的圈 C1和 C2满足下面两个条件之一:

(Ⅰ)p1是奇数,p2是偶数,且sgn C2=-1.

(Ⅱ)p1和 p2都是奇数,且sgn C1=-sgn C2.

为了方便起见,满足 (Ⅰ)或 (Ⅱ)的圈对 C1和 C2我们称之为“异圈对”.很容易看到,此时,闭途径对W1=p2C1和W2=p1C2有相同的长度 p1p2,但有不同的符号:

设 a1,…,ak是非负整数,定义 Frobenius集[8]为 S(a1,…,ak)={r1a1+…+rkak|r1,…,rk是非负整数}.由Schur引理,如果gcd(a1,…,ak)=1,那么则有S(a1,…,ak)包含所有足够大的非负整数.在这种情况下,定义 Frobenius数φ(a1,…,ak)为对于所有整数m≥φ,使得 m∈S(a1,…,ak)成立的最小整数φ.

根据上述定义,有φ(a1,…,ak)-1不属于 S(a1,…,ak).此外,如果 a,b是互素的非负整数,那么:

设R={l1,…,lr}为本原有向图D的圈长集合,且gcd(l1,…,lr)=1.用 d(D)表示 D的直径.对于D中的每一对顶点x和y,设 d(x,y)为从 x到y的距离,且 dR(x,y)(关于集合R,从 x到y的相对距离)为从 x到y至少接触长为li(对于每个 i=1,…,r)的一个圈的最短途径的长度.记φR=φ(l1,…,lr)为 Frobenius数,那么对于本原指数和点指数有以下式子成立:

定义7[9]设S是一个本原不可幂定号有向图,S的歧义指数 (ambiguous index)被定义为S中最短的SSSD途径对的长度,记为 r(S).

引理2[10]设S是一个本原不可幂定号有向图,W1和W2是从点 u到点ν的长度为r的SSSD途径对.则有:

证明 设 x ,y,z是图S中的任意三个顶点 (可以相同),设 P是S中从z到u的长为 d (z,u)的最短的路,显然有, 所以, 所以从ν到 y 存在长为的途径 Q ,所以 P +W1+Q和 P +W2+Q形成了从x到y的长为xm∈Va(xD)d(x,u)+r+expS(ν)的 S SSD途径对,所以上式成立.

本文对一类本原不可幂定号有向图的基进行了研究,其基础图为图1.并且综合运用 Frobenius集、本原指数、“异圈对”、SSSD途径、歧义指数、图的直径和反证法等相关知识,得出了此图的基的精确值.

4 主要结果

定理1 设 S是n(m≥2,s≥4,t≥0且 m+s+t阶本原不可幂定号有向图,D是它的基础图 (如图1所示).

(Ⅰ)若S中的两个n-t-m-s-1圈具有不同的符号,则l(S)=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.

(Ⅱ)若S中的两个n-t-m-s-1圈具有相同的符号,则l(S)=2n2+2m2+4s2+2 t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-7.

证明 (Ⅰ)在图1中,令 Q1=(n-m-2t-2s-1,n-m-2 t-2s)+…+(n-m-t-2s-1,n-m-t-2s)+(n-m-t-2s,n-s)+…+(n-2,1)+(1,2)+…+(m-1,m),Q2=(n-m-2 t-2s-1,n-m-t-2s+1)+(n-m-t-2s+1,n-m-t-2s+2)+…+(n-s-2,n-s-1)+(n-s-1,m)是从n-m-2 t-2s-1到 m的长度为m+s+t的两条途径.由于S中 (仅有的)两个 n-t-m-s-1圈具有不同的符号,则一定有sgn Q1=-sgn Q2,故 r ≤m+s+t,又≤n-t-m-s-2, 由公式(4)得:

图1 本原不可幂定号有向图D

对任意的 i,jòV(D),从i到n-m-2 t-2s-1的途径的长度 d≤n-t-m-s-2.又注意到 m在两个n-t-m-s-1圈上,由expD(m)≤n2-2nt+2m t-2nm+m2-3sn+3sm+3st+t2+2s2+2s-4可知对任意a≥n2-2nt+2m t-2nm+m2-3sn+3sm+3st+t2+2s2+2s-4,存在从 m到j的一条a长途径,那么存在一对从i到j的长为d+r+expD(m)=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6的 SSSD途径对.因此,l(S)≤n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.

接下来证明l(S)≥n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.用反证法证明从 n-m-t-2s+1到 n-s-1不存在长为 n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-7的SSSD途径对.假设Wi(i=1,2)是任意两条从 n-m-t-2s+1到 n-s-1的长为 k=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-7的途径.

那么每个 Wi是由若干个 Cn-t-m-s-1圈和若干个 Cn-m-t-2s+2圈和长为 n-3的路径组成(其中Cn-m-t-2s+2,Cn-t-m-s-1分别表示n-m-t-2s+2圈与n-t-m-s-1圈).即 k=l(Wi)=ai(n-m-t-2s+2)+bi(n-t-m-s-1)+n-3(ai≥0,bi≥0),所以有

化简为 (n-m-t-2s+2-b)(n-t-m-s-1)=(a+1)(n-m-t-2s+2).

因为此图是本原有向图,所以 n-t-m-s-1与 n-m-t-2s+2互素,所以n-m-t-2s+2|n-m-t-2s+2-b而n-m-t-2s+2＞n-m-t-2s+2-b所以n-m-t-2s+2-b=0或 b=0

当 n-m-t-2s+2-b=0时,得 a=-1(与 ai≥0矛盾).当 b=0时,到 n-m-t-2s+1到 n-s-1只绕 n-m-t-2s+2圈,不绕 n-t-m-s-1圈,那么sgn W1=sgn W2(矛盾).

所以S中不存在长为k的SSSD途径对.从而得出l(S)≥n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.

综合上述讨论得出l(S)=n2+m2+t2+2s2-2nt+2m t-2nm-3sn+3sm+3st+2s+n-6.

(2)若S中 (仅有的)两个 n-t-m-s-1圈具有相同的符号,则sgn Q1=sgn Q2.由于S是本原不可幂的,且S中仅有的3个圈是两个 n-t-m-s-1圈和一个 n-m-t-2s+2圈,由引理1知,每个 n-t-m-s-1圈与 n-m-t-2s+2圈构成一个“异圈对”.所以由公式 (1)知 (n-m-t-2s+2)Cn-t-m-s-1与(n-t-m-s-1)Cn-m-t-2s+2有不同的符号.令 P1=(n-m-2 t-2s-1,n-m-t-2s+1)+(n-m-t-2s+1,n-m-t-2s+2)+…+(n-s-1,m),P2=(n-m-2 t-2s-1,n-m-2 t-2s)+…+(n-m-t-2s-1,n-m-t-2s)+(n-m-t-2s,n-1)+(n-1,n)+(n,1)+(1,2)+…+(m-1,m)分别是从n-m-2 t-2s-1到m的长为m+s+t,m+t+3的途径.令W1=P1+(n-m-t-2s+1)Cn-t-m-s-1,W2=P2+(n-m-t-s-2)Cn-m-t-2s+2是从 n-m-2 t-2s-1到 m的长为n2+m2+t2+2s2-2nm-2nt+2m t-3sn+3sm+3st+m+2s+t-1的途径对.再令 P是从m到n-m-2 t-2s-1的长为 n-2m-2 t-2s-1的唯一途径.那么有W1+P=(n-m-t-2s+2)Cn-t-m-s-1,W2+P=(n-t-m-s-1)Cn-m-t-2s+2,从而W1与W2符号不同.因此W1与W2是一对从n-m-2 t-2s-1到m的长为n2+m2+t2+2s2-2nm-2nt+2m t-3sn+3sm+3st+m+2s+t-1的SSSD途径对.类似 (1)的证明,得出

接下来证明

l(S)≥2n2+2m2+4s2+2t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-7用反证法证明从 n-m-t-2s+1到n-s-1不存在长为2n2+2m2+4s2+2 t2+4m t-4nm-4nt=6st-6sn+6sm+3s+n-8的SSSD途径对.假设Wi(i=1,2)是任意两条从n-m-t-2s+1到 n-s-1的长为 k=2n2+2m2+4s2+2t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-8的途径.那么每个Wi是由若干个Cn-t-m-s-1圈和若干个 Cn-m-t-2s+2圈和长为 n-3的路径组成,即 k=l(Wi)=ai(n-m-t-2s+2) +bi(n-t-m-s-1)+n-3(ai,bi≥0),故有 (a2-a1)(n-m-t-2s+2)=(b1-b2)(n-t-m-s-1).设a2-a1=(n-t-m-s-1)x,下证x=0.用反证法,如果 x≥1,则 a2≥n-t-m-s-1(由 a1≥0),所以有

φ(n-m-t-2s+2,n-t-m-s-1) -1=n2+m2+t2+2s2-2nt-2nm+2m t-3sn+3sm+3st-n+m+3s+t-3=-n2-m2-t2-2s2+2nt-2m t+2nm+3sn-3sm-3st-n+m+t+1+a2(n-m-t-2s+2)+b2(n-t-m-s-1)+n-3=[a2-(n-t-m-s-1)](n-m-t-2s+2)+b2(n-t-m-s-1).这与φ(n-m-t-2s+2,n-t-m-s-1)的定义矛盾.同理可证 x≤-1也与φ(n-m-t-2s+2,n-t-m-s-1)的定义矛盾.所以 x=0成立,即有a1=a2,b1=b2.那么有sgnW1=sgnW2,所以S中不存在长为k的SSSD途径对.从而得出l(S)≥2n2+2m2+4s2+2 t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-7

综合以上讨论得出

l(S)=2n2+2m2+4s2+2 t2+4m t-4nm-4nt+6st-6sn+6sm+3s+n-7.定理得证.

[1] Shen J,Neufeld S.Local exponents of primitive digraphs[J].Linear Algebra Appl,1998,268：117-129

[2] Li Z,Hall F,Eschenbach C.On the period and base of a sign pattern matrix[J].Linear A lgebra App l,1994,212/213：101-120

[3] Brualdi RA,Liu B.Generalized exponents of primitive directed graphs[J].J Graph Theory,1990(14)：483-499

[4] You LH,Shao JY,Shan H Y.Bounds on the bases of irreducible generalize sign pattern matrix[J].Linear A lgebra App l,2007,427：285-300

[5] Shao JY.On the exponent of a primitive digraph[J].Linear Algebra Appl,1985,64：21-31

[6] Liu BL.Boundson the base of primitive nearly reducible sign pattern matrices[J].Linear Algebra Appl,2006,418：863-881

[7] Gao YB,Shao YL,Shen J.Bounds on the local bases of primitive non-powerful nearly reducible sign patterns[J].Linear Multilin Algebra,2009,57(2)：205-215

[8] 胡红萍.图与矩阵的组合理论及其网络应用 [D].太原：中北大学,2009

[9] 霍丽芳,高玉斌.两个围长为2的本原不可幂定号有向图的广义基 [J].数学的实践与认识,2010,(10)：235-239

[10] Wang LQ,Miao ZK,Yan C.Local bases of primitive non-powerful signed digraphs[J].Discr Math,2009,309(4)：748-754