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

羅美金，侯宗毅，喬友付

（河池學院 數學系，廣西 宜州 546300）

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

羅美金，侯宗毅，喬友付

（河池學院 數學系，廣西 宜州 546300）

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

雙色；有向圖；指數；上界；極圖

1 引言

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

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

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

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

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

圖1 未著色有向圖D

2 本原條件及指數上界

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

證明 顯然，D是強連通的，則

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

下面對D分三種類型討論：類型1，弧m-2→m-1→m是紅的；類型2，弧m-2→-m-1→m是藍的；類型3，弧m-2→m-1是紅的，弧m-1→m是藍的(或弧m-2→m-1是藍的，弧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 指數上界的極圖刻畫

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

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

當且僅當D中存在一條a+b-2長的紅路.

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

設存在一對非負整數(h,k)，使對D中所有頂點對(i,j)，都有一條從i到j的(h,k)-途徑.取i=j=m，則存在非負整數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).

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

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

對D中所有頂點對(i,j)，記pij從i到j的最短路，r(pij)=s,b(pij)=t.只需證明對D的任意一對頂點 (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.因此，從頂點i出發，沿pij到頂點j，轉m-圈ρ1次，轉n-圈ρ2次的途徑有分解

顯然，ρ1≥0,ρ2≥0. 當 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

當且僅當存在一條m+n-a-b的連續藍路.

定理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）當弧m-2→m-1是紅的，弧m-1→m是藍的時，當且僅當m-a-1→m-a→L→m-1是紅的，弧m→m+1→L→m+b是紅的，其余弧為藍的；或，弧m→1→L→a是紅的，弧m+n-a-b→m+n-b→L→m+n-3→m-2→m-1 是紅的，其余弧為藍的.

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

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

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

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

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

O157.5

A

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

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