霍麗芳,高玉斌

(1.中北大學(xué)理學(xué)院,山西太原030051;2.河北建筑工程學(xué)院數(shù)理系,河北張家口075024)

一類恰含兩個(gè)圈的本原不可冪定號(hào)有向圖的廣義基

霍麗芳1,2,高玉斌1

(1.中北大學(xué)理學(xué)院,山西太原030051;2.河北建筑工程學(xué)院數(shù)理系,河北張家口075024)

研究了一類恰含兩個(gè)圈的本原不可冪定號(hào)有向圖,通過分析圖形特點(diǎn),綜合利用 SSSD途徑對(duì)和Frobenius指數(shù)的特性推導(dǎo)出這類圖的廣義基.

本原圖;定號(hào)有向圖;SSSD途徑對(duì);廣義本原指數(shù);廣義基

1 基本概念

定義1.1 設(shè)D是一個(gè)有向圖 (允許有環(huán)但不能有重弧),如果存在一個(gè)正整數(shù) k,使得 D中任意兩個(gè)頂點(diǎn)vi和vj(可以相同)都有長(zhǎng)為 k的途徑,則稱 D是本原的,最小的 k就是D的本原指數(shù),記作exp (D).

定義1.2 設(shè) D是一個(gè)有向圖,對(duì)于 vi∈D,存在正整數(shù) m,從 vi到D中任意一點(diǎn)都有長(zhǎng)為t≥m的途徑,滿足條件的最小的m就是vi的點(diǎn)指數(shù),記作expD(vi).

為方便,令V(D)= {v1,v2,…,vn},可將 D中頂點(diǎn)適當(dāng)調(diào)序使得expD(v1) ≤expD(v2) ≤…≤expD(vn),稱expD(vk)為D的第k個(gè)廣義本原指數(shù),記為expD(k).

定義1.3 設(shè)D是有向圖,將 D中的每條弧被標(biāo)記1為-1,則稱為定號(hào)有向圖,記為S.定號(hào)有向圖S中的一條途徑W是由一系列的弧e1,e2,…,ek組成的,并且ei的終點(diǎn)與ei+1的始點(diǎn)相同 (i=1,2,…,k-1).途徑中弧的條數(shù)就是途徑W的長(zhǎng)度,記為 l(W).途徑W的符號(hào)被定義為∏ki=1sgn {ei},記為sgn W.

定義1.4 在定號(hào)有向圖中的兩條途徑W1和W2,如果它們有相同的起始點(diǎn),相同的長(zhǎng)度,不同的符號(hào),則稱它們?yōu)镾SSD途徑對(duì).

定義1.5 設(shè)S是定號(hào)有向圖,如果S中不含SSSD途徑對(duì),則S是可冪的;否則,是不可冪的.

定義1.6 設(shè) S是一個(gè)本原不可冪定號(hào)有向圖,使得對(duì)任意t≥l及S中任意兩個(gè)頂點(diǎn)vi和j(可以相同),從 vi到vj都有長(zhǎng)為t的SSSD途徑對(duì),則稱最小的 l是定號(hào)有向圖S的基,記作 l(S).

定義1.7 設(shè)S是一個(gè)本原不可冪定號(hào)有向圖,對(duì)于 vi∈S,存在正整數(shù)m,從vi到S中任意一點(diǎn)都有長(zhǎng)為t≥m的SSSD途徑對(duì),滿足條件的最小m的就是vi的點(diǎn)基,記作lS(vi).

為方便,令V(S)= {v1,v2,…,vn},則 S中頂點(diǎn)適當(dāng)調(diào)序后可得lS(v1)≤lS(v2) ≤…≤lS(vn),稱lS(vk)為S的第k個(gè)廣義基,記作lS(k).

2 相關(guān)知識(shí)與理論

命題2.1[1]如果S是一個(gè)本原定號(hào)有向圖,那么S是不可冪的充分必要條件是S中包含的一對(duì)長(zhǎng)度分別為 p1和 p2的圈和 C1和 C2滿足下面兩個(gè)條件之一:

(A)p1是奇數(shù),p2是偶數(shù),并且有sgnC2=-1.

(B) p1和 p2都是奇數(shù),并且有sgnC1=-sgnC2.

為方便起見,滿足(A)或(B)的圈對(duì) C1和 C2成為“異圈對(duì)”.容易看到若 C1和 C2是長(zhǎng)分別為 p1和p2的異圈對(duì),則閉途徑對(duì)W1=p2C1和W2=p1C2有相同的長(zhǎng)度 p1p2,但有不同的符號(hào):

設(shè)a1,…,ak是非負(fù)整數(shù),定義 Frobenius集為:S (a1,…,ak) = {r1a1+…+rkak|r1,…,rk是非負(fù)整數(shù)}.根據(jù)Schur引理,如果gcd(a1,…,ak) =1,那么 S(a1,…,ak)包含所有足夠大的非負(fù)整數(shù).在這種情況下,定義 Frobenius數(shù)φ (a1,…,ak)為對(duì)于所有整數(shù) m≥φ,使得 m∈S(a1,…,ak)成立的最小整數(shù)φ.

根據(jù)上述定義,有φ (a1,…,ak) -1不屬于 S(a1,…,ak).另外,如果 a,b是互素的非負(fù)整數(shù),那么

引理2.1[2]設(shè)D是一個(gè)本原有向圖,L是圈長(zhǎng)集合.設(shè) {p,q} ?L,gcd(p,q) =1,且 p＜q.若D中包含長(zhǎng)為p,q的兩個(gè)交叉的圈,則當(dāng)1≤k≤n時(shí)有expD(k) ≤p(q-2) +n-q+k.

引理2.2[3]設(shè) S是本原不可冪定號(hào)有向圖,且 u∈V (S),若從 u→u有一對(duì)長(zhǎng)為r的SSSD的途徑對(duì),則 lS(u)≤expS(u)+r.

引理2.3[4]設(shè) S是n階本原不可冪定號(hào)有向圖,x,y是S中不同的兩個(gè)點(diǎn)且Rt(x) = {y}(其中Rt(x)表示從 x出發(fā)經(jīng)過t長(zhǎng)途徑到達(dá)頂點(diǎn)的集合).若從 x→y的所有t長(zhǎng)途徑都有相同的符號(hào),則 ls(x) =lS(y) +t.

特殊地,若R1(k+1) = {k},則 lS(k+1) =lS(k)+1 (3)本文主要是對(duì)一類本原不可冪定號(hào)有向圖S進(jìn)行研究,通過研究我們得出如下主要結(jié)果.

3 主要結(jié)論

定理:設(shè)S是一個(gè)本原不可冪定號(hào)有向圖,D是其基礎(chǔ)圖,如圖1所示,則

圖1 有向圖 D

[1] You LH,Shao JY,Shan HY.Boundson the basesof irreducible generalized sign pattern matrices[J].Linear A lgebra App l,427(2007)：285-300

[2] Shen J,Neufeld S.Local exponents of p rimitive digraphs[J].Linear A lgebra App l.1998,268：117-129

[3] Gao YB,Shao YL,Shen J.Bounds on the local bases of p rimitive non-powerful nearly reducible sign patterns[J].Linear M ultil A lgebra,2009,57(2)：205-215

[4] Ma HP.Boundson the local basesof p rimitive,non-powerful,minimally strong signed digraphs[J].Linear A lgebra App l,2009,430：718-731

Generalized Bases of a Class of Prim itive Non-powerful Signed Nearly Reducible Digraphs with Two Cycles

HUO Li-fang1,2,GAO Yu-bin1
(1.College of Science,No rth University of China,Taiyuan 030051,Shanxi,China;2.Department of Mathematics and Physics,Hebei Institute of A rchitecture and Civil Engineering,Zhangjiakou 075024,Hebei,China)

The generalized bases of a class of prim itive non-pow erful nearly reducible signed digraphs w ith two cycles are discussed.With the analysisof this digragh and the characteristicsof SSSD walks and Frobenius,the generalized bases of this class digraphs are concluded.

p rimitive digraph;signed digraph;SSSD walks;generalized exponent;generalized base

O 157.5

A

1673-1492(2010)01-0006-03

來稿日期：2009-11-04

山西省自然科學(xué)基金資助項(xiàng)目 (2007011017,2008011009)

霍麗芳(1979-),女,河北萬全人,河北建筑工程學(xué)院講師,碩士研究生.

劉守義]