论文部分内容阅读
中图分类号：O157.5 文献标识码：A
摘要：本文是对带有三个圈的不可幂的定号有向图进行了研究，通过分析此图的特点，综合运用指数、SSSD途径对、Frobenius数的相关性质，给出了有向图的基。
关键词：有向图； 基； SSSD途径对
Abstract： In the paper，we study the non-powerful signed digraph with three simple cycles. By analyzing this kind of digraphs and using the properties of exponents、SSSD walks、Frobeniusnumber，we obtain the equality cases of the base.
Keywords： signed digraph；base； a pair of SSSD walks
1.引 言
实数a的符号记为sgna，当a>0，a<0，a=0时，sgna定义为+，-，0。由{+，-，0}中的元组成的矩阵称为符号模式矩阵，简称符号模式[1]。设A=（aij）是n阶符号模式，以v={1，2，...，n}为顶点集，以E={（i，j）|aij≠0}为弧集的有向图D称为A的伴随有向图，记为D（A）.将D（A）中的每一条弧（i，j）赋予aij得到的图称为A的伴随定号有向图D（A）。
定义1.1[3]. 若定号有向图中的两个途径W1和W2有相同的起点、终点和长度，但有不同的符号，则称W1和W2为SSSD途径对。
定义1.2[2]. 若定号有向图S不包含SSSD途径对，则S是可幂的，否则S是不可幂的。
设 a1，...，ak是正整数.定义Frobenius的集合S（a1，...，ak）为S（a1，...，ak）={r1a1 +...+rkak|r1，...，rk是非负整数}[4]。若g.c.d.（a1，...，ak）=1，则S（a1，...，ak）包含所有足够大的非负整数，定义Frobenius数φ（a1，...，ak）为对于所有整数m≥φ都有使得m∈S（a1，...，ak）成立的最小正整数φ.故φ（a1，...，ak）-1不属于S（a1，...，ak）。若g.c.d.（a，b）=1，则φ（a，b）=（a-1）（b-1）。
S是带有三个圈的本原不可幂的定号有向图（见下图S）。
2.预备知识
引理2.1[5]. 设S是本原定号有向图，S是不可幂的充要条件是S包含长度分别为p1和p2的两个圈C1和C2满足下面两个条件之一
（B1） pi是奇数，pj是偶数且有sgn（Cj）=-1（i，j=1，2 且i≠j）；
（B2） p1和p2都是奇数，且有sgn（C1）=-sgn（C2）.
方便起见，满足（B1）或（B2）的一对圈C1和C2称为“异圈对”。若C1和C2是长度分别为p1和p2的异圈对，则闭路W1=p2C1，W2=p1C2有相同的长度p1p2，但符号不同。则
（sgn（C1））p2=-（sgn（C2））p1（2.1）
本原有向图D的圈长集合R={l1，...，lr），则g.c.d.（l1，...，lr）=1。对于D中的任意两点x和y，d（x，y）为从x到y的距离。dR（x，y）为从x到y至少接触圈长li（i=1，...，r）的圈的最短路径的长度，设φR{l1，...，lr）为Frobenius数，则[3]
expD（u）≤φR+maxv∈V（D）dR（u，v）；（2.2）
exp（D）≤φR+maxx，y∈V（D）dR（x，y）.（2.3）
定义2.1[3].设S是本原不可幂的定号有向图，则S的模糊指数r（S）被定义为最小正整数r，r是S中的SSSD途径对。
引理2.2[3]. 设S是本原不可幂的定号有向图，W1和W2是从点u到点v长为ru，v的SSSD途径对，d（S）是S的直径，则
L（S）≤d（S）+ru，v+expS（v）；（2.4）
L（S）≤d（S）+r+exp（S）.（2.5）
3.主要结果
定理3.1 设S是n（n≥8）阶本原不可幂定号有向图，D是S的基础图，若m=5，则
（1）若S中的两个n-5圈符号不同，则L（S）=n2-11n+36.
（2）若S中的两个n-5圈符号相同，则L（S）=2n2-23n+71.
证明 （1） 设
Q1=（n-5，n-4）+（n-4，n-3）+（n-3，n-2）+（n-2，n-1）+（n-1，n）+（n，6）
Q2=（n-5，1）+（1，2）+（2，3）+（3，4）+（4，5）+（5，6）
是两条从n-5到6的6长途径，则sgnQ1=-sgnQ2，故r（S）≤6.由（2.3）和引理2.2得d（S）=n-7，exp（S）≤φ（n-5，n-6）+maxx，y∈V（D）dR（x，y）≤（n-6）（n-7）+n-5=n2-12n+37.
故L（S）≤d（S）+r+exp（S）≤n-7+6+n2-12n+37=n2-11n+36.
下面证明不存在从n-3到9长为k=n2-11n+35的SSSD途径对。设W1和W2是两条从n-3到9长为k的途径，P是从n-3到9长为6的最短途径，W1（或W2）是路径P和圈Cn-5和Cn-6的连接，则有 k=l（Wi）=ai（n-5）+bi（n-6）+6（ai≥0，bi≥1）（i=1，2）.所以（b2-b1）（n-6）=（a1-a2）（n-5），若a1-a2=（n-6）x，则b2-b1=（n-5）x. 若x≥1 ，则b2≥n-2，所以k=a2（n-5）+b2（n-6）+6=a2（n-5）+（b2-2）（n-6）+2n-6.又因S是本原不可幂，由引理2.1知S中的两个n-5圈必有一个与n-6圈形成异圈对，则g.c.d.（n-5，n-6）=1，所以φ（n-5，n-6）-1=k-2n+6=a2（n-5）+（b2-2）（n-6）∈S（n-5，n-6）.和Frobenius数φ（n-5，n-6）的定义矛盾。
同理若x≤-1，也得出矛盾。则x=0，所以a1=a2，b1=b2且sgn（W1）=sgn（W2），因此L（S）≥n2-11n+36.故L（S）=n2-11n+36。
（2）若S中的两个n-5圈符号相同，则sgnQ1=sgnQ2，又因为S是本原不可幂，由引理2.1知S中的两个n-5圈必有一个与n-6圈形成异圈对，由（2.1）知（n-6）Cn-5和（n-5）Cn-6的符号不同。
设P1=（n-5，n-4）+（n-4，n-3）+（n-3，n-2）+（n-2，n-1）+（n-1，n）+（n，6）和P2=（n-5，n-4）+（n-4，n-3）+（n-3，4）+（4，5）+（5，6）是从n-5到6长分别为6和5的途径，P=（6，7）+…+（n-6，n-5）是从6到n-5长为n-11的途径。设W1=P1+（n-7）Cn-5； W2=P2+（n-6）Cn-6.
则W1+P=（n-6）Cn-5；W2+P=（n-5）Cn-6，所以W1和W2的符号不同且形成长度为n2-12n+41的SSSD途径对。则有r（S）≤n2-12n+41，故
L（S）≤d（S）+r+exp（S）≤n-7+n2-12n+41+n2-12n+37=2n2-23n+71
如（1）的证明，同样得出不存在从n-3到7的长度为k=2n2-23n+70的SSSD途径对。所以L（S）≥2n2-23n+71.故L（S）=2n2-23n+71
参考文献：
[1]Zhongshan Li，Frank Hall，and Carolyn Eschenbach，On the period and base of a sign pattern matrix，Linear Algebra Appl.212/213（1994），pp.101-120.
[2]Lihua You，Jiayu Shao and Haiying Shan，Bounds on the bases of irreducible generalized sign pattern matrices，Linear Algebra Appl.427（2007），pp.285-300.
[3]Bolian Liu and Lihua You，Bound on the base of primitive nearly reducible sign pattern matrices.Linear Algebra Appl.418（2006），pp.863-881.
[4]Yubin Gao，Yanling Shao ang Jian Shen，Bounds on the local bases of primitive nonpowerful nearly reducible sign patterns， Linear and Multilinear Algebra（2008），pp.1-11，iFirst.
[5]Longqin Wang，Zhengke Miao and Chao Yan， Local bases of primitive nonpowerful signed digraphs ，Discrete Mathematics（2008），pp.1-7.
摘要：本文是对带有三个圈的不可幂的定号有向图进行了研究，通过分析此图的特点，综合运用指数、SSSD途径对、Frobenius数的相关性质，给出了有向图的基。
关键词：有向图； 基； SSSD途径对
Abstract： In the paper，we study the non-powerful signed digraph with three simple cycles. By analyzing this kind of digraphs and using the properties of exponents、SSSD walks、Frobeniusnumber，we obtain the equality cases of the base.
Keywords： signed digraph；base； a pair of SSSD walks
1.引 言
实数a的符号记为sgna，当a>0，a<0，a=0时，sgna定义为+，-，0。由{+，-，0}中的元组成的矩阵称为符号模式矩阵，简称符号模式[1]。设A=（aij）是n阶符号模式，以v={1，2，...，n}为顶点集，以E={（i，j）|aij≠0}为弧集的有向图D称为A的伴随有向图，记为D（A）.将D（A）中的每一条弧（i，j）赋予aij得到的图称为A的伴随定号有向图D（A）。
定义1.1[3]. 若定号有向图中的两个途径W1和W2有相同的起点、终点和长度，但有不同的符号，则称W1和W2为SSSD途径对。
定义1.2[2]. 若定号有向图S不包含SSSD途径对，则S是可幂的，否则S是不可幂的。
设 a1，...，ak是正整数.定义Frobenius的集合S（a1，...，ak）为S（a1，...，ak）={r1a1 +...+rkak|r1，...，rk是非负整数}[4]。若g.c.d.（a1，...，ak）=1，则S（a1，...，ak）包含所有足够大的非负整数，定义Frobenius数φ（a1，...，ak）为对于所有整数m≥φ都有使得m∈S（a1，...，ak）成立的最小正整数φ.故φ（a1，...，ak）-1不属于S（a1，...，ak）。若g.c.d.（a，b）=1，则φ（a，b）=（a-1）（b-1）。
S是带有三个圈的本原不可幂的定号有向图（见下图S）。
2.预备知识
引理2.1[5]. 设S是本原定号有向图，S是不可幂的充要条件是S包含长度分别为p1和p2的两个圈C1和C2满足下面两个条件之一
（B1） pi是奇数，pj是偶数且有sgn（Cj）=-1（i，j=1，2 且i≠j）；
（B2） p1和p2都是奇数，且有sgn（C1）=-sgn（C2）.
方便起见，满足（B1）或（B2）的一对圈C1和C2称为“异圈对”。若C1和C2是长度分别为p1和p2的异圈对，则闭路W1=p2C1，W2=p1C2有相同的长度p1p2，但符号不同。则
（sgn（C1））p2=-（sgn（C2））p1（2.1）
本原有向图D的圈长集合R={l1，...，lr），则g.c.d.（l1，...，lr）=1。对于D中的任意两点x和y，d（x，y）为从x到y的距离。dR（x，y）为从x到y至少接触圈长li（i=1，...，r）的圈的最短路径的长度，设φR{l1，...，lr）为Frobenius数，则[3]
expD（u）≤φR+maxv∈V（D）dR（u，v）；（2.2）
exp（D）≤φR+maxx，y∈V（D）dR（x，y）.（2.3）
定义2.1[3].设S是本原不可幂的定号有向图，则S的模糊指数r（S）被定义为最小正整数r，r是S中的SSSD途径对。
引理2.2[3]. 设S是本原不可幂的定号有向图，W1和W2是从点u到点v长为ru，v的SSSD途径对，d（S）是S的直径，则
L（S）≤d（S）+ru，v+expS（v）；（2.4）
L（S）≤d（S）+r+exp（S）.（2.5）
3.主要结果
定理3.1 设S是n（n≥8）阶本原不可幂定号有向图，D是S的基础图，若m=5，则
（1）若S中的两个n-5圈符号不同，则L（S）=n2-11n+36.
（2）若S中的两个n-5圈符号相同，则L（S）=2n2-23n+71.
证明 （1） 设
Q1=（n-5，n-4）+（n-4，n-3）+（n-3，n-2）+（n-2，n-1）+（n-1，n）+（n，6）
Q2=（n-5，1）+（1，2）+（2，3）+（3，4）+（4，5）+（5，6）
是两条从n-5到6的6长途径，则sgnQ1=-sgnQ2，故r（S）≤6.由（2.3）和引理2.2得d（S）=n-7，exp（S）≤φ（n-5，n-6）+maxx，y∈V（D）dR（x，y）≤（n-6）（n-7）+n-5=n2-12n+37.
故L（S）≤d（S）+r+exp（S）≤n-7+6+n2-12n+37=n2-11n+36.
下面证明不存在从n-3到9长为k=n2-11n+35的SSSD途径对。设W1和W2是两条从n-3到9长为k的途径，P是从n-3到9长为6的最短途径，W1（或W2）是路径P和圈Cn-5和Cn-6的连接，则有 k=l（Wi）=ai（n-5）+bi（n-6）+6（ai≥0，bi≥1）（i=1，2）.所以（b2-b1）（n-6）=（a1-a2）（n-5），若a1-a2=（n-6）x，则b2-b1=（n-5）x. 若x≥1 ，则b2≥n-2，所以k=a2（n-5）+b2（n-6）+6=a2（n-5）+（b2-2）（n-6）+2n-6.又因S是本原不可幂，由引理2.1知S中的两个n-5圈必有一个与n-6圈形成异圈对，则g.c.d.（n-5，n-6）=1，所以φ（n-5，n-6）-1=k-2n+6=a2（n-5）+（b2-2）（n-6）∈S（n-5，n-6）.和Frobenius数φ（n-5，n-6）的定义矛盾。
同理若x≤-1，也得出矛盾。则x=0，所以a1=a2，b1=b2且sgn（W1）=sgn（W2），因此L（S）≥n2-11n+36.故L（S）=n2-11n+36。
（2）若S中的两个n-5圈符号相同，则sgnQ1=sgnQ2，又因为S是本原不可幂，由引理2.1知S中的两个n-5圈必有一个与n-6圈形成异圈对，由（2.1）知（n-6）Cn-5和（n-5）Cn-6的符号不同。
设P1=（n-5，n-4）+（n-4，n-3）+（n-3，n-2）+（n-2，n-1）+（n-1，n）+（n，6）和P2=（n-5，n-4）+（n-4，n-3）+（n-3，4）+（4，5）+（5，6）是从n-5到6长分别为6和5的途径，P=（6，7）+…+（n-6，n-5）是从6到n-5长为n-11的途径。设W1=P1+（n-7）Cn-5； W2=P2+（n-6）Cn-6.
则W1+P=（n-6）Cn-5；W2+P=（n-5）Cn-6，所以W1和W2的符号不同且形成长度为n2-12n+41的SSSD途径对。则有r（S）≤n2-12n+41，故
L（S）≤d（S）+r+exp（S）≤n-7+n2-12n+41+n2-12n+37=2n2-23n+71
如（1）的证明，同样得出不存在从n-3到7的长度为k=2n2-23n+70的SSSD途径对。所以L（S）≥2n2-23n+71.故L（S）=2n2-23n+71
参考文献：
[1]Zhongshan Li，Frank Hall，and Carolyn Eschenbach，On the period and base of a sign pattern matrix，Linear Algebra Appl.212/213（1994），pp.101-120.
[2]Lihua You，Jiayu Shao and Haiying Shan，Bounds on the bases of irreducible generalized sign pattern matrices，Linear Algebra Appl.427（2007），pp.285-300.
[3]Bolian Liu and Lihua You，Bound on the base of primitive nearly reducible sign pattern matrices.Linear Algebra Appl.418（2006），pp.863-881.
[4]Yubin Gao，Yanling Shao ang Jian Shen，Bounds on the local bases of primitive nonpowerful nearly reducible sign patterns， Linear and Multilinear Algebra（2008），pp.1-11，iFirst.
[5]Longqin Wang，Zhengke Miao and Chao Yan， Local bases of primitive nonpowerful signed digraphs ，Discrete Mathematics（2008），pp.1-7.