一類非負矩陣對的本原指數(shù)

羅美金,侯宗毅

(河池學院 數(shù)學系,廣西 宜州 546300)

一類非負矩陣對的本原指數(shù)

羅美金,侯宗毅

(河池學院 數(shù)學系,廣西 宜州 546300)

研究了一類特殊的雙色有向圖,它的未著色圖中含有 3n-2個頂點,包含一個(2n+1)-圈和一個n-圈的圖,給出了本原條件和指數(shù)的上、下界,并對極圖進行了刻劃.

本原指數(shù);本原圖;雙色圖;指數(shù)界;極圖

0 引言

設D是一個有向圖,D的一條長為l的途徑是指連續(xù)的頂點序列v1,v2,……,vl+1,其中對所有的i=1,2,……,l,D中都有從vi到vi+1的弧.如果v1,v2,……,vl+1,互不相同,則稱該途徑是一條長為l的路.如果vi=vi+1,則稱為一條閉路或圈.如果D是包含紅弧和藍弧的有向圖,則稱D是一個雙色有向圖[1].

非負矩陣對(A,B)同樣與其伴隨有向圖存在一一對應關系,其伴隨有向圖記為D(A,B),顯然D(A,B)具有頂點 1,2,……,n.非負矩陣對與其伴隨有向圖建立了對應關系,即可從非負矩陣對(A,B)中元素的數(shù)值來判斷其伴隨有向圖D(A,B)中對應弧存在與否.如:從矩陣A=(aij)中元素的數(shù)值可判斷D(A,B)中是否存在對應的紅弧,若aij>0,則從頂點i到頂點j存在一條紅弧;同樣從矩陣B=(bij)中元素的數(shù)值可判D(A,B)中是否存在對應的藍弧,若bij>0,則從頂點i到頂點j存在一條藍弧[2].

如果雙色有向圖對應的非負矩陣對(A,B)是本原的,則稱雙色有向圖D(A,B)是本原的,且D(A,B)的本原指數(shù) exp(D(A,B)),即為(A,B)的本原指數(shù) exp(A,B).由非負矩陣對的本原性及其本原指數(shù)的概念,可將雙色有向圖的本原性及其本原指數(shù)的概念定義為:

一個雙色有向圖D是本原的,當且僅當存在非負整數(shù)h和k,且h+k>0,使得D中的每一對頂點(i,j)都存在從i到j的(h,k)—途徑,h+k的最小值定義為雙色有向圖D的本原指數(shù),記為 exp(D).(h,k)—途徑是指從i到j的途徑中包含h條紅弧和k條藍弧[3].

引理 1:[4]一個至少包含一條紅弧和一條藍弧的雙色有向圖D是本原的,當且僅當D是強連通的,且content(M)=1.

目前對雙色本原有向圖(非負本原矩陣對)的研究只得到了一些初步的結(jié)果.在國內(nèi),關于非負本原矩陣對的研究也取得了一些成果[1,2,3,5,6,7].本文研究一類特殊的雙色有向圖D,它的未著色有向圖如圖1所示.

顯然,D中僅包含兩個圈,圈長分別為 2n+1和n,且兩個圈有公共弧 2n-1→2n→2n+1,則D的圈矩陣可寫為

其中a,b為正整數(shù).

1 本原條件

=1,且

定理 1: 雙色有向圖D是本原的,當且僅當an-b(2n+1)

證明:顯然,D是強連通的,det(M)=an-b(2n+1),故由引理1得,D是本原的當且僅當 det(M)=±1,要使a,b都為正整數(shù),容易驗證,當an-b(2n+1)=1時,a=2n-1,b=n-1;當an-b(2n+1)=-1時,a=2,b=1.定理得證.

2 指數(shù)上界

定理 2: 設雙色有向圖D是本原的,且an-b(2n+1)=1,則 exp(D)≤12n2-12n-4.

類型一:弧 2n-1→2n→2n+1不包含藍弧.

只需證明對D的任意一對頂點(i,j),都有一條(12n2-24n+11,12n-15)-途徑.取ρ1=3n-4-s+(n-1)t,ρ2=3(2n-1)-4+2s-(2n-1)t.因此,從頂點i出發(fā),沿pij到頂點j,轉(zhuǎn)(2n+1)-圈ρ1次,轉(zhuǎn)n-圈ρ2次的途徑有分解

顯然,s≤3n-4,t≤3且ρ1≥0,ρ2≥0.當s=3n-4時,t≥0;t=3時,s≥2.此時,ρ1=0或ρ2=0時,Pij必包含公共弧 2n-2→2n→2n+1.所以

exp(D)≤12n2-24n+11+12n-15=12n2-12n-4.

類型二:弧 2n-1→2n→2n+1包含一條藍弧.

只需證明對D的任意一對頂點(i,j),都有一條(10n2-17n+6,10n-9)—途徑.取ρ1=3n-4-s+(n-1)t,ρ2=2(2n-1)+2s-(2n-1)t.因此,從頂點i出發(fā),沿Pij到頂點j,轉(zhuǎn)(2n+1)圈 ρ1次,轉(zhuǎn)n-圈ρ2次的途徑有分解

顯然,s≤3n-3,t≤2,且ρ1≥0,ρ2≥0.當s=3n-3時,t≥1;t=2時,s≥0.此時,Pij必包含公共弧 2n-1→2n→2n+1.所以

exp(D)≤10n2-17n+6+10n-9=10n2-7n-3.

類型三:弧 2n-1→2n→2n+1包含兩條藍弧.

只需證明對D的任意一對頂點(i,j),都有一條(8n2-12n+4,8n-6)-途徑.取ρ1=3n-4-s+(n-1)t,ρ2=2(2n-1)+2s-(2n-1)t.因此,從頂點i出發(fā),沿Pij到頂點j,轉(zhuǎn)(2n+1)-圈ρ1次,轉(zhuǎn)n-圈ρ2次的途徑有分解

顯然,s≤3n-2,t≤2,且ρ1≥0,ρ2≥0.當s=3n-2時,t=2;t=2時,s≥0.此時,Pij必包含公共弧 2n-1→2n→2n+1.所以

比較類型一、二、三 exp(D)的大小,顯然得 exp(D)≤12n2-12n-4.定理得證.

定理 3: 設雙色有向圖D是本原的,且an-b(2n+1)=-1,則 exp(D)≤12n2-12n-4.

證明:與定理 2類似可證.

3 指數(shù)下界

定理 5: 設雙色有向圖D是本原的,且an-b(2n+1)=-1,則 exp(D)≥4n2+n.

證明:與定理 4類似可證.

4 指數(shù)上界的極圖刻劃

定理 6: 設雙色有向圖D是本原的,且an-b(2n+1)=1,則 exp(D)=12n2-12n-4當且僅當D中存在一條 3n-4長的紅路.

證明:充分性:由定理 3,只需證明 exp(D)≥12n2-12n-4.

必要性:利用反正法.設雙色有向圖D是本原的,且an-b(2n+1)=1.若不存在一條 3n-4長的紅路,只需證明 exp(D)<12n2-12n-4即可.

只需證明對D的任意一對頂點(i,j),都有一條(12n2-26n+12,12n-17)-途徑.取ρ1=3n-5-s+(n-1)t,ρ2=3(2n-1)-4+2s-(2n-1)t.因此,從頂點i出發(fā),沿Pij到頂點j,轉(zhuǎn)(2n+1)-圈ρ1次,轉(zhuǎn)n-圈ρ2次的途徑有分解

顯然,s≤3n-4,t≤3且ρ1≥0,ρ2≥0.當s=3n-4時,t≥1;t=3時,s≥2.此時,ρ1=0或ρ2=0時,Pij必包含公共弧 2n-1→2n→2n+1.所以,

exp(D)≤12n2-26n+12+12n-17=12n2-14n-5<12n2-12n-4.定理得證.

定理 7: 設雙色有向圖D是本原的,且an-b(2n+1)=-1,則 exp(D)=12n2-12n-4當且僅當D中存在一條 3n-4長的藍路.

證明:與定理 6類似可證.

5 指數(shù)下界的極圖刻劃

定理 8: 設雙色有向圖D是本原的,且an-b(2n+1)=1,則 exp(D)=4n2-3n-1當且僅當D中(2n+1)-圈上同時存在兩條連續(xù)紅路,路長分別為n-1和n.

類型一:弧 2n-1→2n→2n+1不包含藍弧.

只需證明對D的任意一對頂點(i,j),都有一條(4n2-3n,4n)-途徑.取ρ1=n-s+(n-1)t,ρ2=2n+2s-(2n-1)t.因此,從頂點i出發(fā),沿pij到頂點j,轉(zhuǎn)(2n+1)-圈ρ1次,轉(zhuǎn)n-圈ρ2次的途徑有分解

考慮以下兩種情形:

情形 1 頂點i到頂點j在(2n+1)-圈上,且不包含n-圈上的點.此時,0≤s≤2n-4,0≤t≤2.

i)當t=0時,0 ≤s≤n,ρ1≥0,ρ2>0;

ii)當t=1時,0 ≤s≤2n-4,ρ1>0,ρ2>0;

iii)當t=2時,n-1 ≤s≤2n-5,ρ1>0,ρ2≥0.

情形 2 頂點i到頂點j上包含n-圈上的點.此時,0≤s≤3n-4,0≤t≤3.顯然,滿足ρ1≥0,ρ2≥0.

故對D的任意一對頂點(i,j),都有一條(4n2-7n+3,4n-4)-途徑.當ρ1=0或ρ2=0時,必含弧2n-1→2n→2n+1.所以

類型二:弧 2n-1→2n→2n+1包含一條藍弧.

類型三:弧 2n-1→2n→2n+1包含兩條藍弧.

類型二、三與類型一類似可證.

綜上所述得 exp(D)≤4n2-7n+3+4n-4=4n2-3n-1.定理得證.

定理 9:設雙色有向圖D是本原的,且an-b(2n+1)=-1,則 exp(D)=4n2+n當且僅當D中(2n+1)圈上同時存在兩條連續(xù)藍路,路長分別為n-1和n.

[1]羅美金,高玉斌.一類雙色有向圖的本原指數(shù)[J].中北大學學報 (自然科學版),2008,29(2):95-100.

[2]Shao Yanling,Gao Yubin,Liang Sun.Exponents of a class of two-colored digraphs[J].LinearAlgebra and itsApplacations,2005,(53):175-188.

[3]Gao Yubin,Shao Yanling.Exponents of two-colored digraphswith two cycles[J].LinearAlgebra and itsApplacations,2005,(407):263-276.

[4]B L Shader,S Suwilo Exponents of nonnegative matrix pairs[J].LinearAlgebra Appl.,2003,(363):275-293.

[5]羅美金,高玉斌.一類恰含三個圈的三色有向圖的本原指數(shù)[J].山東大學學報 (理學版),2008,43(1):65-72.

[6]羅美金,高玉斌.一類含有兩個圈的雙色有向圖本原指數(shù)[J].中北大學學報 (自然科學版),2007,(5):377-382.

[7]汪榮,邵燕靈,高玉斌.一類雙色有向圖本原指數(shù)的上界[J].吉林大學學報 (理學版),2008,(4):601-606.

The Exponent of a Class of NonnegativeMatrix Pa irs

LUO M ei-jin,HOU Zong-yi

(Depart ment ofMathematics,Hechi Un iversity,Y izhou,Guangxi546300,China)

In this article,we study a type of special two-colored digraphs whose uncolored digraph has 3n-2 vertices and consists of one(2n+1)-cycle and one n-cycle.We give some primitive conditions and the bound on the exponents.Finally,we give the characterizations of extremal two-colored digraphs.

exponent;primitive digraph;two-colored digraph;bound;extremal digraph

O157.5

A

1672-9021(2010)02-0015-05

羅美金 (1981-),女,江西廣豐人,碩士,河池學院數(shù)學系教師,主要研究方向:組合數(shù)學.

河池學院《應用數(shù)學》重點學科 (200725)

2010-3-20

[責任編輯普梅笑 ]