基于弧行列式的有向图中的有向圈数

基于弧行列式的有向图中的有向圈数 基于弧行列式的有向图中的有向圈数 第23卷第11期 Vo1.23No.1l 重庆工学院(自然科学) JournalofChongqingInstituteofTechnology(NaturalScience) 2009年11月 NOV.20Cl9 基于弧行列式的有向图中的有向圈数 谢挺 重庆400050) (重庆理工大学数理学院, 摘要:利用弧行列式对有向图中的有向圈数展开讨论,得出了n阶有向图,严格单连通有 向图中的有向圈数值以及n阶二分有向图,有向图中有向圈数的上界. 关键词:有向图;弧行列式;有向圈 中图分类号:O157.5文献标识码:A文章编号:1671—0924(2009)11—0173—03 TheNumberofDirectedCyclesinaDirected GraphBasedontheArcDeterminant XIETing (SchoolofMathsandPhysics,ChongqingUniversityofTechology,Chongqing400050,Chi na) AbstactThispaperusesarcdeterminanttodiscussthedirectedcycle,thengetsthenumberof directedcyclesinn—orderdirectedgraphandstrictlysimply—connectedgraph.aswellastheupper boundofdirectedcyclesinaHamiltongraph. Keywordsdirectedgraph;arcdeterminant;directedcycle 1基本概念和定义 对于有向图G=(,A,),任意的?V(G)的出度和入度分别记为d()和d一().用a=(,)? A(G)表示图中从u到的一条弧.对G中的任意2顶点u和,若u与V可以互相到达,则称G为强连通 图;若"可到达或可到达",则称G为单向连通图;若与是连接的,则称G为弱连通图.在有向图 G中去掉弧的方向之后得到的图称为G的底图,记为G.若.G无环和重复的弧,则称G为简单有向图.若 对Vu,?V(G)有(u,)?A(G),则称G为完全有向图.按照有向图的不同特征,可以定义不同类型的有 向图.记C(G)为图G中的有向圈数.在讨论C(G)之先给出如下的有关定义: 定义1对有向图G的顶点序列(1)1…)和(u:…)为其有向路径,定义有向路径的乘法 r(l2…I)kM2…M,),若=I且(l…"1…M1)是新的有向路 (V12…)×(M1M2…uj)={(ulM2…UiV2…),若=l且(M1…uiv2…)是新的有向路【 0,其他 收稿日期:2009—09—05 基金项目:重庆市教委科技基金资助项目(KJ090623). 作者简介:谢挺(1981一),男,湖北仙桃人,硕士,讲师,主要从事理论研究. 174重庆工学院 定义2设有向图G的n条有向路径(… ),…,(.…定义有条有向路径的加法法 则为 (V12…)+…+(/Z1n2…",) 仅表示在有向图G中存在对应n条有向路径 (12…),…,(H1H2…). ' 定义3有向图G=(,A,),其中V={, :,…,},定义G的弧行列式P(G)为 PllP12 p21p22 Pn1Pn2 = ?Pb'lP2/2""砜. tt/2, 其中p={':;三且p…p为有向 路径的乘法结果(或称弧行列式的项). 定义4将有向图G的弧行列式中主对角线 上P置为1,其他项P(i)不变,所得的行列式 称为对角置1弧行列式,记为P(G)]. 本文中讨论的图均为连通的简单有向图,所 有未给出的概念和记号见文献[2—3]. 2引理 引理1设V(G)={l,:,…,},则有向图 G的弧行列式P(G)的项与G中所有有向 Hamilton圈中的圈是一一对应的. 引理2JP(G)的某k级主子式的项与经过 有向图G的某k个顶点的所有有向k圈中的圈一一 对应 引理3设是尸(G)的k级主子式,则划 去余下的p(G)的—k级行列式是P(G)的 n一.i}级主子式,其项与经过有向图G的某n—k个 顶点的所有有向n—k圈中的圈一一对应.有以上 的3个引理可知,对有向图G的有向圈的讨论可 以转化为对其弧行列式P(G)的讨论. 3主要结果 定理1有向图C的对角置1弧行列式P (G)的项(除去//,个对角元素的乘积1)与G中所 有有向圈中的圈是一一对应的. 证明 由P(G)的定义及P(G)的定义有 P(G)= 1P12 P211 P1Pn2 : ?pu.P2.j2".JL/2..," 若P?砜各元素均不为1,即J,?1,…,?1,则 P.^…p是取自P(G)的非对角元的不同行不同 列的个元素之积,而:.7"n(?)中的下标 ?? 包括1,2,…,的全部排列,根据引理1 有:p??与G中所有有向n圈是一一对应的. 若P…p含k个为1(0<k<n)的元素,可 设1=1,J2=2,…,Jk=Ij},贝0P.=p=…=p茸,此 时p.…P=p++,…p等价在P(G)中删除1, 2,…,k行和1,2,…,k列后余下的n—k级行列式 中除主对角线元素外的不同行不同列的n—k个 顶点的所有有向/7,一k圈中的圈一一对应. 有了定理1之后,可以将对有向圈的讨论直 接转化为对P.(G)的讨论. 定理2对n阶有向图G,若V口?V(G)有 d()=k,则C(G)=(k+1)!一1. 证明 由d(口)=k,贝0对Vi?I,(G)有(,)? A(G).对于P(G),其中t=1,2,…,k,有 P(G): 1P12 P2l1 ???-?? P1''' 当除去其中主对角线上的元素的乘积项1, P.(G)行列式可展开为[(k+1)!一1]项.由引理 3可知 C(G)=(k+1)!一1 对n阶完全有向图G,有d()=n一1,再利用定 理2,易得如下推论: 推论1对n阶完全有向图G,有c(G)=n!一1. 定理3若G为严格单连通有向图,则c(G)=Q 证明 若G严格单连通,则对V,?V(G)存在 nn ??? ??? ??? Rnn 12ppp ??? ??? ??? .. 1 ??? h毗 谢挺:基于弧行列式的有向图中的有向圈数数175 一有向路径(或弧)而不存在一的有向路 径(或弧),从而P(G)可以通过行列式变换之后 变成一个主对角线元素为1的三角阵,即 P(G)一 1Pl2 1 则有P.(G)=1,即不存在非1项,从而由定理1 有C(G)=0. 推论2若G为弱连通有向图,则C(G)=0. 据弱连通有向图的定义及定理3,容易证明以 上推论. 定理4设阶有向图G为二分有向图,令其2 部A,B?V(G)的顶点数分别为Ot,,则C(G)? Ol!!. 证明 由于G为二分有向图,且其2部的顶点数分 别为Ol和,则有 P(G)= 10…0Pl1…Pl 01…0P2l…P2 00…1PB1… q1…q胡0…1 将P(G)进行分块有 G):IPll Q,ll 其中,0,,,为单位矩阵,从而P(G)=lPI?IQ1. 又由于fPf和fQf分别含有Ot和项,则P(G)有 Ot!!项(除去主对角线元素的乘积1),故 C(G)?Ol!!. 定理5对有向H图G=(,A,),若有 lV(G)I=11,,IA(G)l=1l,+k,则C(G)?2?一1. 证明 设C为有向图G的有向圈,则G可由 C添加某些弧得到,为了方便描述可以假设所添 加的弧均在有向圈C的内部,如图1所示. 令={.,,…,),贝0有 P.()= cHG 图1有向圈C内部添加的弧 1(U1,)00 01(,)0 (,1)011 而P(G)可以由P(C)将其中某些0元素替换 为相应的弧.由于IA(G)I=+k,lG日I=n,则 P(G)比P(C)多k个非零元素,且每增加一个 非零元素至少比原来的有向圈数增加一倍,则有 ccG?-+2(:)+2()+…+2()=2?一. 参考文献: [1]朱秀丽.有向图正则覆盖的特征多项式[J].哈尔滨 理工大学,2006,11(5):51—54. [2]BondyJA,MurtyUS.GraphTheoryandApplication [M].NewYork:MacmillanPress,1987. [3]徐兵,贾仁安.有向图的行列式算法及H图条件 [J].数学的实践与认识,2002,32(4):643—650. [4]YongbingShi.ThenumberofcyclesinaHamihion graph[J].DiscreteMathematics,1994,133(1):249 — 257. [5]单秀玲.完全对称有向图D—n的偶长圈分解[J].高 校应用数学:A辑,2003,18(1):115—124. [6]梁志和.完全图循环分解成2一正则图[J].应用数 学,2008,31(6):1137—1141. 责任编辑(刘舸) n ;?