劉海琴

(山西農(nóng)業(yè)大學(xué)文理學(xué)院,山西太谷 030801)

一類(lèi)含有兩個(gè)m-圈的三色有向圖的本原指數(shù)

劉海琴

(山西農(nóng)業(yè)大學(xué)文理學(xué)院,山西太谷 030801)

對(duì)于一個(gè)三色有向圖D,其本原的定義是指當(dāng)且僅當(dāng)存在非負(fù)整數(shù)h,k,l,并且有h+k+l＞0,使得對(duì)于D中的每一對(duì)頂點(diǎn)(i,j)都存在從i到j(luò)的(h,k,l)-途徑,定義h+k+l的最小值為D的本原指數(shù)。研究了一類(lèi)特殊的三色有向圖,其未著色圖恰含一個(gè)bm-1-圈、二個(gè)m-圈,并且研究了該圖在一種本原條件下的三色有向圖的本原指數(shù)。

三色有向圖;本原條件;本原指數(shù)

非負(fù)矩陣組合理論是組合數(shù)學(xué)的一個(gè)重要內(nèi)容,主要研究那些僅依賴于矩陣的零位模式,而與矩陣元素本身數(shù)值大小無(wú)關(guān)的性質(zhì),它與圖的一些性質(zhì)有密切聯(lián)系,在信息科學(xué)、通信網(wǎng)絡(luò)、計(jì)算機(jī)科學(xué)等許多學(xué)科中都有具體的應(yīng)用。本原矩陣的本原指數(shù)及廣義本原指數(shù)是非負(fù)矩陣組合理論的重要研究?jī)?nèi)容,許多問(wèn)題已得到解決。而在新的背景下,對(duì)非負(fù)矩陣對(duì)以及矩陣簇的本原指數(shù)的研究應(yīng)運(yùn)而生。事實(shí)上,非負(fù)矩陣對(duì)可以與一個(gè)雙色有向圖建立一一對(duì)應(yīng)關(guān)系,而矩陣簇則可以與一個(gè)多色有向圖建立聯(lián)系,這樣就可以把矩陣的問(wèn)題轉(zhuǎn)化為圖的問(wèn)題來(lái)進(jìn)行研究。近年來(lái),有關(guān)雙色有向圖的本原指數(shù)的文章比較多,而對(duì)多色有向圖的研究則較少。本文研究了一類(lèi)特殊的三色有向圖的本原指數(shù)。

設(shè)D為一個(gè)有向圖,圖D中的一條長(zhǎng)為l的途徑w,指的是一個(gè)連續(xù)的頂點(diǎn)序列ν1ν2…νlνl+1,其中對(duì)所有的i=1,2,…,l,D中都有從頂點(diǎn)νi到νi+1的弧。稱w為一條長(zhǎng)為l的路,如果在某一途徑w中頂點(diǎn)互不相同。如果在這條路中νl+1=ν1,我們則稱這條途徑是一條閉途徑。如果在這條閉途徑中頂點(diǎn)ν1,…,νl+1互不相同,我們則稱這條閉途徑為圈。一個(gè)三色有向圖,指的是一個(gè)其弧被著色為紅,藍(lán),黃三種顏色(或者其他三種顏色)的有向圖。三色有向圖D中從i到j(luò)的一條(h,k,l)-途徑,是指從i到j(luò)的一條包含h條紅弧,k條藍(lán)弧和l條黃弧的途徑。如果對(duì)D中任意的頂點(diǎn)對(duì)(i,j),在D中均存在一條從i到j(luò)的途徑,則稱三色有向圖D是強(qiáng)連通的。

給定D中的一條途徑w,其中紅弧、藍(lán)弧和黃弧的條數(shù)分別用r(w),b(w)和y(w)來(lái)表示,稱w為一條(r(w),b(w),y(w))途徑,w的分解為向量

一個(gè)三色有向圖D是本原的,如果存在滿足條件h+k+l＞0的非負(fù)整數(shù)h,k,l,使得對(duì)于D中的每一對(duì)頂點(diǎn)(i,j)之間都存在從i到j(luò)的(h,k,l)-途徑。我們把非負(fù)整數(shù)和h+k+l的最小值定義為三色有向圖D的本原指數(shù),記為exp(D)。

設(shè)C={γ1,γ2,…,γl}是D的圈的集合 ,定義D的圈矩陣M是一個(gè)3×l矩陣,其第i列是γi的分解。如果M的秩小于3,M的content(記為content(M))定義為0,否則M的content定義為M的所有非零3階子式的最大公因數(shù)。

引理1[1]一個(gè)至少包含一條紅弧、一條藍(lán)弧和一條黃弧的三色有向圖D是本原的,當(dāng)且僅當(dāng)D是強(qiáng)連通的,且content(M)=1。

在文獻(xiàn)[2]～[10]中已經(jīng)給出一些有向圖的本原指數(shù),本文研究一類(lèi)特殊的三色有向圖Dbm-1,m,m(b≥2,m≥3),它的未著色圖如圖1所示。對(duì)任意的D∈Dbm-1,m,m,D中恰有三個(gè)圈,圈長(zhǎng)分別為bm-1,m,m,此類(lèi)三色有向圖的本原情況較為復(fù)雜。本文僅研究在一種本原條件下的特殊有向圖的本原指數(shù)。記D∈Dbm-1,m,m,且D中兩個(gè)m-圈的著色情況分別為:其中一個(gè)m-圈中有m-1條紅弧,1條藍(lán)弧;另外一個(gè)m-圈中有m-2條紅弧,藍(lán)弧,黃弧各一條。

1 三色有向圖的本原性

圖1 未著色有向圖Fig.1 Uncolored digraph

證明:很明顯,此類(lèi)三色有向圖所對(duì)應(yīng)的圈矩陣為

2 本原指數(shù)

下面將討論當(dāng)x=b時(shí)的本原指數(shù)。

定理2 設(shè)D∈Dbm-1,m,m,且在D中bm-1-圈中藍(lán)弧條數(shù)為b,則D是本原的,且

證明:由于D的圈矩陣為

此時(shí),可以得到

由題意知,2m-6≤a≤bm-b-2(當(dāng)m=3時(shí)2m-5≤abm-b-2)。對(duì)D中的任意一對(duì)頂點(diǎn)(i,j),記pij是從i到j(luò)的最短路,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。此時(shí) ,exp(D)≤2b2m2-(2b2+2b)m+b,定理得證 。

定理3 設(shè)D∈Dbm-1,m,m,且在D中bm-1-圈中藍(lán)弧條數(shù)為b,則D是本原的,且當(dāng)bm-1-圈中b條藍(lán)弧連續(xù)時(shí)

證明:當(dāng)bm-1-圈中b條藍(lán)弧連續(xù)時(shí),有2m-5≤a≤bm-b-2,當(dāng)2m-5≤a≤bm-2b-1時(shí),由定理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]周慧玲,邵燕靈.兩個(gè)雙向圈的雙色有向圖的本原指數(shù)[J].中北大學(xué)學(xué)報(bào),2007(6),471-474.

[5]林建青,高玉斌.含有兩個(gè)三圈的三色有向圖的本原指數(shù)[J].太原師范學(xué)院學(xué)報(bào):自然科學(xué)版,2008,7(4):1-4.

[6]李娟,邵燕靈.一類(lèi)特殊的三色有向圖的本原指數(shù)[J].太原師范學(xué)院學(xué)報(bào):自然科學(xué)版,2008,7(2):1-5.

[7]羅美金,高玉斌.一類(lèi)恰含三個(gè)圈的三色有向圖的本原指數(shù)[J].山東大學(xué)學(xué)報(bào):理學(xué)版,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-),女(漢),山西大同人,碩士,主要從事應(yīng)用數(shù)學(xué)方面的研究。

(編輯:馬榮博)