一類雙色有向圖的極圖刻畫

羅美金，侯宗毅，喬友付

（河池學(xué)院 數(shù)學(xué)系，廣西 宜州 546300）

一類雙色有向圖的極圖刻畫

羅美金，侯宗毅，喬友付

（河池學(xué)院 數(shù)學(xué)系，廣西 宜州 546300）

考慮一類雙色有向圖，它的未著色圖中含一個m-圈和一個n-圈，且兩圈有兩條公共弧，給出了本原條件和并對達(dá)到指數(shù)上界的極圖進(jìn)行了刻畫.

雙色；有向圖；指數(shù)；上界；極圖

1 引言

設(shè)D是一個有向圖，如果D是包含紅弧和藍(lán)弧的有向圖，則稱D是一個雙色有向圖.雙色有向圖D是強(qiáng)連通的，如果D中每一對頂點(diǎn)(i,j)都存在從i到j(luò)的途徑.給定D中的一條途徑ω，用r(ω)和b(ω)分別表示ω中紅弧和藍(lán)弧的條數(shù)，稱 ω 為一條(r(ω),b(ω))- 途徑，ω 的分解為向量 r(ω),b(ω)或(r(ω),b(ω))T.

一個雙色有向圖D是本原的，當(dāng)且僅當(dāng)存在非負(fù)整數(shù)h和k，且h+k>0，使得D中的每一對頂點(diǎn)(i,j)都存在從i到j(luò)的 (h,k)途徑，h+k的最小值定義為雙色有向圖D的本原指數(shù)，記為exp(D).

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

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

近幾年對本原雙色有向圖的本原指數(shù)的研究已經(jīng)取得了一些重要成果，見文獻(xiàn)[1-7].本文在文獻(xiàn)[4]的基礎(chǔ)上，做了進(jìn)一步的研究，研究一類雙色有向圖D，它的未著色有向圖如圖1所示.D中僅包含兩個圈，圈長分別為m和n，且兩圈有兩條公共弧，則D的圈矩陣可寫為矩陣可寫為

圖1 未著色有向圖D

2 本原條件及指數(shù)上界

定理2 若D是本原的,當(dāng)且僅當(dāng)|an-bm|=1.

證明 顯然，D是強(qiáng)連通的，則

由引理1可得，D是本原的當(dāng)且僅當(dāng)content(M)=1，即|M|=±1.定理得證.

下面對D分三種類型討論：類型1，弧m-2→m-1→m是紅的；類型2，弧m-2→-m-1→m是藍(lán)的；類型3，弧m-2→m-1是紅的，弧m-1→m是藍(lán)的(或弧m-2→m-1是藍(lán)的，弧m-1→m是紅的).

定理3[4]若an-bm=1，D屬于類型1，且本原，則

exp(D)≤m(a+b-2)(n-b)+an(m+n-a-b)-2n(m-a)；

定理4[4]若an-bm=-1，D屬于類型2，且本原，則

ecp(D)≤bm(m+n-a-b-2)+n(m-a)(a+b)-2am.

定理5[4]若an-bm=1，D屬于類型3，且本原，則

exp(D)≤m(n-b)(a+b-1)+an(m+n-a-b-1)-n(m-a)-bm；

3 指數(shù)上界的極圖刻畫

定理6 設(shè)雙色有向圖D是本原的,且an-bm=1，則

exp(D)=m(a+b-2)(n-b)+an(m+n-a-b)-2n(m-a)

當(dāng)且僅當(dāng)D中存在一條a+b-2長的紅路.

證明 充分性：由定理3，只需證明exp(D)≥m(a+b-2)(n-b)+an(m+n-a-b)-2n(m-a).

設(shè)存在一對非負(fù)整數(shù)(h,k)，使對D中所有頂點(diǎn)對(i,j)，都有一條從i到j(luò)的(h,k)-途徑.取i=j=m，則存在非負(fù)整數(shù)u和 v，有

所以，u≥(n-b)(a+b-2).

所以，v≥2(-m+a)+a(m+n-a-b).

=m(a+b-2)(n-b)+an(m+n-a-b)-2n(m-a).

結(jié)合定理3,則得exp(D)=m(a+b-2)(n-b)+an(m+n-a-b)-2n(m-a).

必要性:利用反證法.設(shè)雙色有向圖D是本原的,且an-bm=1.若不存在一條a+b-2長的紅路,只需證明exp(D)

對D中所有頂點(diǎn)對(i,j)，記pij從i到j(luò)的最短路，r(pij)=s,b(pij)=t.只需證明對D的任意一對頂點(diǎn) (i,j)，都有一條(a(a+b-2)(n-b)-2ab+ab(m+n-a-b)-2b(m-a),(m-a)(a+b-2)(n-b)-2(m-a)b+d(n-b)(m+n-a-b)-2(n-b)(m-a))-途徑.取ρ1=(n-b)(a+b-2)-2b-(n-b)s+bt，ρ2=a(m+n-a-b)-2(m-a)+(m-a)s-at.因此，從頂點(diǎn)i出發(fā)，沿pij到頂點(diǎn)j，轉(zhuǎn)m-圈ρ1次，轉(zhuǎn)n-圈ρ2次的途徑有分解

顯然，ρ1≥0,ρ2≥0. 當(dāng) s=a+b-2 時,t≥2;t=m+n-a-b 時，s≥2.此時，ρ1=0 或 ρ2=0 時，pij必包含公共弧 m-2→m-1→m.所以,

定理得證.

定理7 若an-bm=-1，D屬于類型2，且本原，則

exp(D)=bm(m+n-a-b-2)+n(m-a)(a+b)-2am

當(dāng)且僅當(dāng)存在一條m+n-a-b的連續(xù)藍(lán)路.

定理8 若an-bm=1，D屬于類型3，且本原，則

exp(D)=m(n-b)(a+b-1)+an(m+n-a-b-1)-n(m-a)-bm，

（1）當(dāng)弧m-2→m-1是紅的，弧m-1→m是藍(lán)的時，當(dāng)且僅當(dāng)m-a-1→m-a→L→m-1是紅的，弧m→m+1→L→m+b是紅的，其余弧為藍(lán)的；或，弧m→1→L→a是紅的，弧m+n-a-b→m+n-b→L→m+n-3→m-2→m-1 是紅的，其余弧為藍(lán)的.

（2）當(dāng)弧m-2→m-1是藍(lán)的，弧m-1→m是紅的時，當(dāng)且僅當(dāng)m-a-2→m-a-1→L→m-2是紅的，弧m-1→m→L→m+b-1是紅的，其余弧為藍(lán)的；或，弧m-1→m→1→L→a-1是紅的，弧m+n-2-b→m+n-1-b→L→m+n-3→m-2是紅的，其余弧為藍(lán)的.

〔1〕B.L.Shader,S.Suwilo,Exponents ofnonnegative matrix pairs[J].Linear Algebra Appl. 363(2003),275-293.

〔2〕Shao Yanling,Gao Yubin,Liang Sun.Exponentsofa class of two-colored digraphs[J].Linear Algebra and its Applacations.2005,53:175-188.

〔3〕Gao Yubin,Shao Yanling.Exponents of two-colored digraphs with two cycles[J].Linear Algebra and its Applacations.2005,407:263-276.

〔4〕羅美金,侯宗毅,喬友付.一類含有兩條公共弧的雙色有向圖的指數(shù)上界 [J].Information Technology and Scientific Management.vo2.(2011):683-687.

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

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

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

O157.5

A

1673-260X（2012）06-0008-02

廣西自治區(qū)教育廳項目(NO.201010LX468)；河池學(xué)院科研項目(NO.2010QS-N007,NO.2010A-N004)