Kp和Kp＋1的具有最多Hamilton圈的定向图-论文.pdf

《Kp和Kp＋1的具有最多Hamilton圈的定向图-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第30卷哈尔滨师范大学自然科学学报Vo1．30，No．42014第4期NATURALSCIENCESJOURNALOFHARBINNORMALUNIVERSITY和+的具有最多Hamilton圈的定向图魏慧敏(大同大学)【摘要】在文献[3]中，Hofman等人证明了完全图中最多边不交的Ham．i1t。n圈个数为[]．这说明K存在一个定向，使得具有[]个弧不相交的Hamilton圈．给出了当n=p和P+1(其中P是一个奇素数)时，一种构造的方法，使用这种方法，可以直接写出To的所有弧不相交的Hamilton圈．【关键词】完全图；定向；弧不相交的Ha

2、milton圈[]个弧不相交Hamilton圈的竞赛图的一种0引言称无向图G的一个定向图为在G的每条边较简便的方法．上指定一个方向后得到的有向图．一个n个顶点1主要结果及证明的竞赛图是指完全图K的一个定向图．一个图厂的Hamilton圈是指包含厂的每个顶点的圈．设P是一个奇素数，下面对和+寻求称两个有向圈C和C：是弧不相交的，如果A一种定向，使得所得到的竞赛图具有最多的弧不(C)nA(C)=．一个图的Hamilton圈问题一相交的Hamilton圈，并且给出这个竞赛图的弧不直是图论中一个活跃的研究课题，也是网络工程相交Hamilton圈的具体形式

3、．中经常遇到的问题之一．许多学者对完全图K定理1设P是一个奇素数，是一个顶点的边不相交的Hamilton圈做了讨论．在文献[3]为{1，2，⋯，P}的完全图，则一定存在一个中Hofman等人已经证明了在完全图K中存在定向，使得中存在最多的弧不相交Hamil．一个具有m个边不相交的Hamilton圈的极大集ton圈，并且的弧不相交Hamilton圈为C，C，⋯当且仅当[]≤m≤[]．这表明中最，c，其中对每个1≤≤来说，C=ili：二⋯isip+1满足il，i2，⋯，i∈{1，2，⋯P}，is+1=il多边不交的Hamilton圈个数为[]，也说明

4、二且对任意的t=1，2，⋯，P，有⋯一i；k(modP)．K存在一个定向rn，使得具有[]个弧不二证明由于中最多边不交的Hamilton圈相交的Hamilton圈．然而根据已有的证明方法，个数为[]，所以对设。的任意一个定向T，要具体写出这[]个弧不相交的Hamilton圈二T的弧不相交Hamilton圈的个数不超过．下是非常复杂的．将对n=p和P+1(其中P是一个厶奇素数)的情形，给出了构造n个顶点的具有面对作如下定向：设i√，k都是正整数，且收稿日期：2014—03—24第4期和+1的具有最多Hamilton圈的定向图271≤，≤p，1≤≤卫

5、，如果一i-k(too@)，则(2)当p；3(m。d4)It-,j，是奇数，故令叫，所得的定向图记为．则每固定一个k，和均为整数．中所有满足—i三k(mo@)的顶点及相应的U43：k弧构成一个Hamilton圈C，而且由于P是一个素一数，所以k取不同的值，所得的Hamilton圈不同，U4一2p一+1其中=l，2，⋯，p4+l‘且这个Hamilton圈cl，c2，⋯，c的弧互不令：⋯，相交，定理得证．=一例如P=3时，有一个弧不相交Hamilton圈1231；p=5时，有两个弧不相交Hamilton圈=1，2，⋯，．123451和135241；p

6、=7时，有三个弧不相交+3Hamilton圈12345671，13572461和14736251．≤≤，≤p一p≤2为讨论／／,=P+1的情形，先给出下面的引理．一引理设P是一个奇数，则在1，2，⋯，P中存在p一1个数a1，a2，⋯，Up-1使得U1一U2≤一．1(modp)，U2一U3-=2(modP)，⋯，所以上面定义的U。，U，⋯，a一是1，2，⋯，P一一UP一2一UP一1(mod@p)中互不相同的P一1个数，且r。43a4k一-2=一(p-k+1)E2一l(m。dp)证明由于p是一个奇数，所以是一个la4t-1=a2+A一((m。如)整数

7、．(1)当p=lm。da)时，卫是偶数，故即当取遍1，2，⋯，，f取遍1，2，⋯，是整数．时，有口。一021(modp)，0一03—2U4k一3U42p—k+1一m。dp)，⋯，一一ap_1；m。dp)令：其中‘，．综上所述(1)和(2)，引理得证．定理2设P是一个奇素数，和C，Cz，p+l口4=一孟⋯2，C如定理1中所述，口，口z，⋯，一如引理≤≤-1中所述，+是一个完全图，则+一定存在一，≤p一孚≤个定向+。，使得+存在最多的弧不相交+≤Hamilton圈，并且+的弧不相交Hamilton圈为C，c，⋯，c其中c是由C中nz与a2i+l之间≤

8、插入顶点P+1所得．证明设是+。的任意一个定向，显然所以上面定义的U，Uz，⋯，Up一是1，2，⋯，P中互不相同的P一1个数且的弧不相交