资源描述：
《定向图中的路和回路.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、定向图中的路和回路张存锉曲阜师范学院数学系)(,,.一个没有环的任意两个顶点之间最多只存在一条弧的有向图称作为定向图定向图D~V,A,V,A.()其中是刀中的顶点集合是D中的弧集合令D中各顶点的出度和人度不.2.,小于互JacksonlL证明了D中存在一条长度至少为互的通路在本文中将给出一个更好的结果.刀2.定理中存在一个长度至少为2友+2的通路或长度至少为左十1的回路,:在证明之前先定义一些符号Ieu,,〔Vc,,,“〔才,()~{l()()}ocu,,`Vc,u,t,`A,()~{{()()},c,“,,,“,“,.c其中是
2、D的一个子图都是顶点(心表示一个从指向的弧如果V()~,c,c“.,F(刀)则可以略去表示顶点集合的下标记I()为,(u)如果c是一个回路c~,。,,:,外,。。,{……}I,u,`,`一:〔Ie“,r.言()~{I()mod(+l)}.,证令刀为一个满足上述条件的定向图很明显对D中一切顶点都有I“,ou,l}()})友】()1)左()..,令D中最长通路的长度为1令少为D中所有长度是l的通路的集合如通路产”〔少记,,,,,.~{,,:砂沪沪……岭}砂有如下二个性质I,`,)V`,,o,`,V`,,2(;g(产)(l)g(产)(
3、)产`〕`,:,`,〔I,`,,r)友1.3中必存在一个顶点必二(;)并且+(),.,因为产。是D中的一条最长通路(2)式的成立是明显的如果(3)式不成立则有,1,,`,,`,.`,t,`,,`,,,`,`t,`,,,`,{以l}门I(忍)~曰又因为此,l厦z(各)所以I(吞)二F(产,){{盖}……,1,`,.,“,,`,,,`,,1,,`,,,`,U{思……l}但是!V。){l1}U{以……l}1~反一l而{I(;)】)左,.可见矛盾221,我们假定刀中不存在长度至少为2友十的通路和友十的回路则我们将在这同一,,.:个假
4、定之下可以得到二个截然相反的结果从而证明定理成立一个结果是D中不存在长:.度至少是l的回路;另一个结果是D中存在长度至少是l的回路由假设:l毛2及十1.(4)O)D中不存在长度至少是l的回路,假如D中存在一条长度至少是l的回路我们就可以通过这条回路来找到一条长l+1的,.cl,`,。,,,,通路从而与l为最长通路之长度矛盾令是一条长度至少为的回路~{….本文1979年11月26日收到第2斗期科学通报1113,`,.内}由假设l一l毛h成l(5),,。,方l(由于1约……}也是一条通路所以簇.)h+1簇2左.(6)下面将分情况证明
5、这个矛盾.,寿~l,.情况一即c为l十1长的回路l、6,1,。2lh+l~.,由()()两式1(约)Uo()Ul内}{)咬+>!V(c)!于是必有一,,0,0.,,。。,个顶点u,存在:,〔F(c)。〔I()或者。〔o()这样我们得到了一条通路枷…,,,;,,:,,。,,,l+1.}或{……}其长度为,情况二h~l一.1,、,。,。.同样由(l)(6)两式:11(内)UO()U{}l)2友+l>h+1~!V(c)},。:u,,。〔z内,〔o,0.,。〔I内.于是必有一个顶点存在运F(c)()或()不失一般性可令(),。,,,,一
6、,.。,,这样获得一条通路产~1。t,0…}由产为最长通路以及(2)式有I(留)g.,,``,,:。V(C)同时即有一个顶点存在:,〔V(C)〔I(,)于是又获得另一条最长通路洲2).{t,`+:,,卜,,,。,,1,,`,,,以及。,Vc2.因此,由I。………}()g()(由()式)()o。,1,O2,Vc石+l,U()gV(c)从而1()U(,)l)友I()」~毛2左可见I(。)Uo(留).,c,,一:,,:,,一、,,,.’~V(c)于是V()中存在这样二个顶点和〔I(。)〔o(,)则c~,一:,,,,一1,,.{内…价约
7、……约喻为l+l长的一条回路这已在情况一中处理过了(1)D中存在长度至少是l的回路,,`’F`),由(2)式I(毛)g(产)则可令r“,~max{51,二`,〔I(,盏`,)}(7)和。,~max{r“)8}()P`〔尹,犷.由(3)式显然)受+1(9)。~{,`,t,`,,`,,,`,〔z,`,.令产轰…李…}}其中l(后)l,犷l一21假定D中不存在长度至少是的回路则《(的:c,,,,;,l一将V(产勺分成两个部分~{岭…冲岭l和T~{砰梦…t,l5}(其中{IT~,.》2:)我们将得到下面的结果aT,犷,T,1,.)lo(
8、l。)l《l一一zII(卿)l提l一2(11)一,,,1、,`,.,:,,。。。,:,。因为(z一2即有卿{〔V(T)但是l些l〔o(l)所以。(l)gF(T八、..{,:,l。}于是JoT(,}。),成l一r一2得证l旦.对于!Ir(,l一犷一2也类似地证明黔
