刘海琴

(山西农业大学文理学院,山西太谷 030801)

一类含有两个m-圈的三色有向图的本原指数

刘海琴

(山西农业大学文理学院,山西太谷 030801)

对于一个三色有向图D,其本原的定义是指当且仅当存在非负整数h,k,l,并且有h+k+l＞0,使得对于D中的每一对顶点(i,j)都存在从i到j的(h,k,l)-途径,定义h+k+l的最小值为D的本原指数。研究了一类特殊的三色有向图,其未着色图恰含一个bm-1-圈、二个m-圈,并且研究了该图在一种本原条件下的三色有向图的本原指数。

三色有向图;本原条件;本原指数

非负矩阵组合理论是组合数学的一个重要内容,主要研究那些仅依赖于矩阵的零位模式,而与矩阵元素本身数值大小无关的性质,它与图的一些性质有密切联系,在信息科学、通信网络、计算机科学等许多学科中都有具体的应用。本原矩阵的本原指数及广义本原指数是非负矩阵组合理论的重要研究内容,许多问题已得到解决。而在新的背景下,对非负矩阵对以及矩阵簇的本原指数的研究应运而生。事实上,非负矩阵对可以与一个双色有向图建立一一对应关系,而矩阵簇则可以与一个多色有向图建立联系,这样就可以把矩阵的问题转化为图的问题来进行研究。近年来,有关双色有向图的本原指数的文章比较多,而对多色有向图的研究则较少。本文研究了一类特殊的三色有向图的本原指数。

设D为一个有向图,图D中的一条长为l的途径w,指的是一个连续的顶点序列ν1ν2…νlνl+1,其中对所有的i=1,2,…,l,D中都有从顶点νi到νi+1的弧。称w为一条长为l的路,如果在某一途径w中顶点互不相同。如果在这条路中νl+1=ν1,我们则称这条途径是一条闭途径。如果在这条闭途径中顶点ν1,…,νl+1互不相同,我们则称这条闭途径为圈。一个三色有向图,指的是一个其弧被着色为红,蓝,黄三种颜色(或者其他三种颜色)的有向图。三色有向图D中从i到j的一条(h,k,l)-途径,是指从i到j的一条包含h条红弧,k条蓝弧和l条黄弧的途径。如果对D中任意的顶点对(i,j),在D中均存在一条从i到j的途径,则称三色有向图D是强连通的。

给定D中的一条途径w,其中红弧、蓝弧和黄弧的条数分别用r(w),b(w)和y(w)来表示,称w为一条(r(w),b(w),y(w))途径,w的分解为向量

一个三色有向图D是本原的,如果存在满足条件h+k+l＞0的非负整数h,k,l,使得对于D中的每一对顶点(i,j)之间都存在从i到j的(h,k,l)-途径。我们把非负整数和h+k+l的最小值定义为三色有向图D的本原指数,记为exp(D)。

设C={γ1,γ2,…,γl}是D的圈的集合 ,定义D的圈矩阵M是一个3×l矩阵,其第i列是γi的分解。如果M的秩小于3,M的content(记为content(M))定义为0,否则M的content定义为M的所有非零3阶子式的最大公因数。

引理1[1]一个至少包含一条红弧、一条蓝弧和一条黄弧的三色有向图D是本原的,当且仅当D是强连通的,且content(M)=1。

在文献[2]～[10]中已经给出一些有向图的本原指数,本文研究一类特殊的三色有向图Dbm-1,m,m(b≥2,m≥3),它的未着色图如图1所示。对任意的D∈Dbm-1,m,m,D中恰有三个圈,圈长分别为bm-1,m,m,此类三色有向图的本原情况较为复杂。本文仅研究在一种本原条件下的特殊有向图的本原指数。记D∈Dbm-1,m,m,且D中两个m-圈的着色情况分别为:其中一个m-圈中有m-1条红弧,1条蓝弧;另外一个m-圈中有m-2条红弧,蓝弧,黄弧各一条。

1 三色有向图的本原性

图1 未着色有向图Fig.1 Uncolored digraph

证明:很明显,此类三色有向图所对应的圈矩阵为

2 本原指数

下面将讨论当x=b时的本原指数。

定理2 设D∈Dbm-1,m,m,且在D中bm-1-圈中蓝弧条数为b,则D是本原的,且

证明:由于D的圈矩阵为

此时,可以得到

由题意知,2m-6≤a≤bm-b-2(当m=3时2m-5≤abm-b-2)。对D中的任意一对顶点(i,j),记pij是从i到j的最短路,r(pij)=~r,b(pij)=~b,y(pij)=~y则0≤~r≤a,0≤~b≤b,0≤~y≤bm-1-a-b,可以找到一条分解如下的途径

其中

显然 ,ρ1≥0,ρ2≥0,ρ3≥0。此时 ,exp(D)≤2b2m2-(2b2+2b)m+b,定理得证 。

定理3 设D∈Dbm-1,m,m,且在D中bm-1-圈中蓝弧条数为b,则D是本原的,且当bm-1-圈中b条蓝弧连续时

证明:当bm-1-圈中b条蓝弧连续时,有2m-5≤a≤bm-b-2,当2m-5≤a≤bm-2b-1时,由定理2知,只需证明exp(D)≥2b2m3-(4b2+2ab+2b)m2+(2b2+2ab+2b)m+b。

[1]Shader B L,Suwilo S.Exponents of nonnegative matrix pairs[J].Linear Algebra App l,2003:275-293.

[2]Gao Yubin,Shao Yanling.Exponent of two-colo red double directed cycles[J].Journal of Natural Science of Heilongjiang University,2004(4):55-58.

[3]Shao Yanling,Gao Yubin,Sun Liang.Ex ponent of a class of two-colo red digraph s[J].Linear and M-ultilinear Algebra,2005,53(3):175-188.

[4]周慧玲,邵燕灵.两个双向圈的双色有向图的本原指数[J].中北大学学报,2007(6),471-474.

[5]林建青,高玉斌.含有两个三圈的三色有向图的本原指数[J].太原师范学院学报:自然科学版,2008,7(4):1-4.

[6]李娟,邵燕灵.一类特殊的三色有向图的本原指数[J].太原师范学院学报:自然科学版,2008,7(2):1-5.

[7]罗美金,高玉斌.一类恰含三个圈的三色有向图的本原指数[J].山东大学学报:理学版,2008,43(1):65-72.

[8]Yanling Shao,Yubin Gao.On the exponents of two-colored digraphs with two cycles[J].Linear and Multilinear Algebra,2009,57(2):185-199.

[9]Yanling Shao,Yubin Gao.Exponents of 2-colorings of loopless,symmetric dig raphs[J].Linear and Multilinear Algebra,2009,57(1):65-74.

[10]Yanling Shao,Yubin Gao.Exponents of 2-coloring of symmetric digraphs[J].Linear Algebra and Applications,2008,428:1538-1550.

Primitive Exponents of a Class of Three-colored Digraphs with Twom-cycles

LIU Hai-qin
(College of Arts and Sciences,Shanxi Agricultural University,Taigu Shanxi 030801,China)

For a three-colored digraphD,it is primitive if and only if there exists nonnegative integersh,k,lwithh+k+l＞0 such that for each pair(i,j)of vertices there exists a(h,k,l)walk inDfromitoj.We define the minimum value ofh+k+las the exponent of the primitive three-colored digraphD.Special three-colored digraphs were studied,whose uncolored digraph consists of onebm-1-cycle,twom-cycle,and the paper gave the exponents for one kind of three-colored primitive digraph.

Three-colored digraph;Primitive conditions;Primitive exponent

O157

A

1671-8151(2010)04-0380-05

2010-03-01

2010-04-25

刘海琴(1981-),女(汉),山西大同人,硕士,主要从事应用数学方面的研究。

(编辑:马荣博)