（运筹学与控制论专业论文）与无向图及有向图中距离有关的三个问题.pdf

学位论文独创性声明 本人郑重声明t 1 、坚持以“求实、创新”的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意。 作者签名，兰越 日期；鱼丝：生：至兰 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆被查阅；有权将学位论文的内容编人有关数据库进行检 索；有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后 适用本规定 作者签名：玺堕 日期；塑! ：垡：圭圣 a b s t r a c t 2 a b s t r a c t i nt h i sp a p e r ，w er e s t r i c to u ra t t e n t i o nt ot h r e ep r o b l e m sa b o u td i s t a n c e si ng r a p h s a n dd i g r a p h s ：( 1 ) m i n i m u md i a m e t e ro r i e n t a t i o n so f v 瓦( 仇1 ，n 1 ) ，( 2 ) d i s j o i n t q u a s i - k e r n e li nd i g r a p h s ，( 3 ) e c c e n t r i cd i g r a p h s f o rag r a p hg 1 e tdd e n o t e 蛆o r i e n t a t i o no fgh a v i n gm i n i m u md i a m e t e r d e f t n e ( a ) = d i a m d i nt h i sp a p e r ，w ec o n c e n t r a t eo ne x p l o r i n gt h em i n i m u md i a m e t e ro f v 】巧( m l ，n 1 ) s o m es p e c i a lc a 瞄a r ek n o w n ：，( v 】翰= o 。，2 ，3 ，w h e r em l a n dn 1 ，m = 2o rm24a n dn = 1 ，m = 3a n dn = 1 ，r e s p e c t i v e l y s ow eo n l yc o n s i d e r t h ec a s ew h e nm 2a n dr i 2 t h ef o u o w i n gr e s u l t sa r eo b t a i n e d ：( 1 ) ，( 耳赢v 霹0 3 ， w h e r em 一2 ，3 ，n 2a n dm = n 一4 ；( 2 ) ，( v 确= 2 ，w h e r em 5a n dmi so d d ， 2 7 l ( 【乳) 一m ；( 3 ) ，( v 两= 3 ，w h e r em 5 a n dmi so d d ，n ( 1 蟊) 一吲“； ( 4 ) ，( 尺mv 胃：) ；2 ，w h e r em 4a n dm 兰0 ( r o o d4 ) t2sn s ( 霉) 一( 警+ 1 ) ；( 5 ) ，( v _ ) = 2 ，w h e r em 6a n dm - 2 ( m 。d4 ) ，2s ，l ( 攀) 一号；( 6 ) ，v 硒一3 ， w h e m 4 a n d m i s e v e l l ，n ( 霉) 一等+ 1 av e r t e xs e txo fad i g r a p hd = ( v a ) i saq u a s i - k e r n e li fx i si n d e p e n d e n ta n df o r e v e r y v x t h e r ee x i s t 加v x ，$ xs u c h t h a te i t h e r t ，霉ao r 可叫叫o a i n t h i sp a p e r ，w ep r o v i d ean e c e s s a r yc o n d i t i o na n ds e v e r a ls u f f i c i e n tc o n d i t i o n sf o rad i g r a p h t oh a v eap a i ro fd i s j o i n tq u a s i k e r n e l s t h e e c c e n t r i c i t ye 和) o fv e r t e x i st h em a x i m u md i s t a n c eo f t oa n yo t h e rv e r t e xo f d av e r t e xui sa ne c c e n t r i cv e r t e xo fv e r t e xui ft h ed i s t a n c ef r o m 廿t oui se q u a l 乞ot h e e c c e n t r i c i t yo f t h ee c c e n t r i cd i g r a p he d ( d 1o fad i g r a p hdi st h ed i g r a p ht h a th a st h e s a m ev e r t e xs e ta sda n dt h ea r cs e td e f i n e db y ：t h e r ei sa na r cf r o mt t o i fa n d o n l yi f i sa ne c c e n t r i cv e r t e xo f “t h ee c c e n t r i cd i g r a p he d ( g 1o fg r a p hg i ss i m i l a r l yd e f i n e d 垒竺! 翌! ! ! i nt i f f sp a p e r ，w ee x a m i n ee c c e n t r i cd i g r a p h so fs e v e r a lc l a s s e so fg r a p h sa n dd i g r a p h s l e t ? b ea nu n d i r e c t e dt r e e w ed e t e r m i n et h es t r u c t u r eo fe d 2 ( 妁，w h i c hi sa no p e np r o b l e m l i s t e di n 【1 2 】 k e yw o r d s ：m i n i m u md i a m e t e ro r i e n t a t i o n ，q u a s i - k e r n e l ，s i n k ，d i g r a p h ，e c c e n t r i cd i g r a p h c h i n e s el i b r a r yc l a s s i f i c a t i o n ：0 1 5 7 5 摘要 本文主要研究了与无向图及有向田中距离有关的三个同题- ( 1 ) v 虬( m 1 n 1 ) 的最小赢径定向，【2 ) 有向圈中不相交的拟棱，( 3 ) 离心有向阳 对于图g ，设d 为g 的具有最小直径的定向图，定义，( g ) = 出8 m d 本文我们主要 撵索豳v 瓦( m 1 ，n 1 ) 的最小直径定向一些挣殊情况是b 知的。当m = 1 且 n 1 ；m 篁2 或m 4 且n 篁1im = 3 且n = 1 时。，( v 碲分别为o o ，2 。3 因此，我们其考虑当m 2 且疗2 的情况，得到如下结果t ( 1 ) 当m = 2 ，3 n 2 和 m = n = 4 时，( v 瓦) 。3 ；( 2 ) 当m 5 且m 是奇数，2 n ( l 霉j ) 一m 时， ，( v 而= 2 ；( 3 ) 当m 5 rm 是奇数，n ( 【蜀) 一l ? j + 1 时，( v 冒a ；3 ； ( 4 ) 当m 4 且m 被4 整除25n ( 嚣) 一( 警+ 1 ) 时，( v 瓦) 麓2l ( 5 ) 当 仇6 且m 棱4 除余2 ，2 f l ( 霉) 一等时，( v 繇) ；2 ( 6j 当m 4 且m 矗 偶致，作( 罩) 一予+ 1 时，( k _ v ：k - 7 ) = 3 设x 为有向圈d 的一个疆点集，如果x 是一个独立集并且x 之外的每一个点都托经 一步或两步到达x 。则x 称为d 的一个拟棱率文我们输出了有向圉中有一对不相交的拟 校的一个必要条件和若干充分条件 点t ，的离心距e ( ) 是d 中口到其它所有点的最大距离若d d ( ，让) 一e ( t ，) 则点t 是 点_ l ，的离心点有向图d 的离心有向圈e d ( d ) 与d 有相同的顶点集且它的弧集定义如下 点t 到点 有一条弧当且仅当点 是点牡的一个离心点无向圈g 的离心有向田e d ( g ) 可 以类似地定义本文研究了几个无向图类和有向图类的离心有向图设t 是一十无向树，我 们确定丁e d 2 ( t ) 的结构，这是【1 2 】中提出的一个公开问题 美键调t 最小直径定向，拟核，汇点，有向图。离心有向图 中圈分类。0 1 5 7 5 生= ! 呈型塑兰：= 一：= ! 皇墅! 堡：型! 丝! 些：= ：一= ：= 。一= 1i n t r o d u c t i o n 1 1d e f l n i t i o n sa n dn o t a t i o n s i nt h i sp a p e r w er e s t r i c to u ra t t e n t i o nt ot h r e ep r o b l e m sa b o u td i 昏 t a n c e si ng r a p h sa n dd i g r a p h s ：( i ) m i n i m u md i a m e t e ro r i e n t a t i o n so f v 瓦：( 价21 ，礼1 ) ，( 2 ) d i 8 j o i n tq u a s i k e r n e l si nd i g r a p h s ，( 3 ) e c c e n t r i cd i - g r a p h s ， w eu s et h es t a n d a r dt e r m i n o l o g ya n dn o t a t i o na sg i v e ni nf 1 ；a n df 2 】 w es t i l lp r o v i d em o s to ft h en e c e s s a r yd e f i n i t i o n sa n dn o t a t i o n sf o rt h ec o n - v e n i e n c eo ft h er e a d e r i nt h i sp a p e r ，a l lt h eu n d i r e c t e dg r 印h 8a r es i m p l e ( i e g r 印h 8h a v i n g n ol o o p sa n dn om u l t i e d g e s ) l e t ( 仇1 ) b et h ec o m p l e t eg r a p h w i t h 价v e r t i c e sa n d 碥( r i 1 ) b et h ec o m p l e m e n to f a l s o ，w eu s e v ( m 1 ，n 1 ) t o d e n o t et h eg r a p hi nw h i c he a c hv e r t e xo fk m i sa d j a c e n tt oa l lt h ev e r t i c e so f l e tk ( m l ，m 2 ，m n ) b et h ec o r n - p l e t en - p a r t i t eg r a p hw i t hp a r t so fc a r d i n a l t i e sm l ，m 2 ，m ，i 。a l s o ， l e tz + b et h es e to fp o s i t i v ei n t e g e r s w ec a l laf a m i l y 歹o fs u b s e t so f l ，2 ，m a l la n t i c h a i ni fn os e ti n 歹i sc o n t a i n e di na n o t h e r a no r i - e n t a t i o no fa nu n d i r e c t e dg r a p hgi sa na s s i g n m e n to fd i r e c t i o n st ot h e e d g e so fg t op r o d u c ead i r e c t e dg r a p h i i 强ed i s t a n c e ，d o ( u , t ，) ，f r o m 珏 t o 口i nad i g r a p hdi st h el e a s tl e n g t ho fa ( u ，_ 乇，) 一p a t hi f i sr e a c h a b l ef r o m 札，a n di se q u a lt o 。，o t h e r w i s e t h ed i a m e t e ro fad i g r a p hd ，d e n o t e d b yd i a m d ，i st h em a x i m u md i s t a n c ef r o mav e r t e xt oa n o t h e rv e r t e xo f d l e td = ( v a ) b ead i g r a p ha n dl e tz ，yb eap a i ro fv e r t i c e si nd i f x y a ，t h e nw es a yt h a t 七d o m i n a t e s 掣a n dd e n o t ei tb y 茁_ 可t h e i n n e i g h b o u r h d o d ( o u t - n e i g h b o u r h o o d ) o fav e r t e xoi ndi sd e f i n e da s 6 ( 。) = 可v ( d ) ：y + z ) ( 吉( 。) = 可v ( d ) ：z + 可) ) t h ec l o s e d i n - n e i g h b o u r h o o d ( c l o s e do u t - n e i g h b o u r h o o d ) i sd e f i n e da s 饬= 石( z ) u 。) ( f 茜【。】= 售( 。) u z ) ) l e td 7d e n o t ea no r i e n t a t i o no fk mv !丝竺! ：尘竺 ：一：；! ：! 窒窒壁! 罂量竺! 竺璧垒坠：一= = ：。= ： 瓦( m l ，礼1 ) h a m n gm i n i m u m d i a m e t e ra n dl e tk 7 ( m l ，m 2 ，) d e - n o t ea no r i e n t a t i o no fg ( m 1 ，m 2 ，m n ) h a v i n gm i n i m u md i a m e t e r d e f i n e f ( k m v - 蕊) = d i a m d 7a n d ( m l ，m 2 ，m 。) = d i a m k 7 ( m l ，m 2 ，) e 争 p e c i a l l y ，i fm 1 = r n 2 = = = m ，t h e n l e tf ( m l ，m 2 ，) = ，( m ( n ) ) ， w h e r emi sap o s i t i v ei n t e g e ra n dn 3 av e r t e x8 e txo f ad i g r a p hd = ( ka ) i sak e r n e li f xi si n d e p e n d e n t a n df o re v e r yu v xt h e r ee x i s t so xs u c ht h a t 口z a av e r t e xs e t xo fad i g r a p hd = ( v a ) i saq u a s i - k e r n e li fx i si n d e p e n d e n ta n df o r e v e r yt ，v xt h e r ee x i s tw v x ，z xs u c ht h a te i t h e rt 膳ao r ”，w x a ad i g r a p ht = ( v a ) i s at o u r n a m e n ti f f o re v e r yp a i ro ，yo f d i s t i n c tv e r t i c e si nv ，e i t h e rx y ao ry x a ，b u tn o tb o t h av e r t e xo f o u t - d e g r e ez e r oi sc a l l e das i n k ，o t h e r w i s ei ti sc a l l e dan o n - s i n k av e r t e x t ，i nat o u r n a m e n ti sc a l l e dak i n gi fe v e r yo t h e rv e r t e xi sr e a c h a b l ef r o mu b yad i r e c t e dp a t ho fl e n g t ha tm o s tt w o aq u a s i - k e r n e lo fc a r d i n a l i t y1 i s c a l l e da2 - s e r fo fd f o rad i g r a p hd ，w ed e n o t et h ev e r t e x ( a r c ) s e tb y v ( d ) ( a ( d ) ) l e tz ，yb et w ov e r t i c e so fd a n dyb eas u b s e to fy ( d ) i f 霉 d o m i n a t e s 可( zd o e s n td o m i n a t e 暑，) ，t h e nw ed e n o t ei tb y ( z ，暑，) 口 ( ( ，掣) = 0 ) i ft h e r ee x i s t s ( d o e s n te x i s t ) av e r t e xy y s u c ht h a tz ， t h e nw ed e n o t ei tb y ( ，y ) 0 ( ( 七，y ) = = o ) l e tdb ead i g r a p hw i t hn v e r t i c e s ，w em a y a s s u m ev ( d ) = 1 ，2 ，3 ，n ) n o ww er e p l a c ee a c hv e r t e x io fdb y 凰( 1 isn ) ，w h e r e 凰i sa ne m p t yg r a p ha n d 皿n 马= df o r i j i fid o m i n a t e sj ，t h e ne a c hv e r t e xo f 凰d o m i n a t e sa l lt h ev e r t i c e so f 毋w ed e n o t et h en e wd i g r a p hb yd 日1 ，玩，凰】 s u p p o s eg i sa nu n d i r e c t e dg r a p hw i t hv e r t e xs e tv ( a ) a n de d g es e t e ( g ) l e tr d e n o t eap a t hf r o mut o 口t h ed i s t a n c ed a ( u ，t ，) b e t w e e n v e r t i c e sua n d 口i st h el e n g t ho fas h o r t e s tp a t hj o i n i n gua n d t h ee c o c e n t r i c i t ye ( 移) o f i st h em a x i m u md i s t a n c ef r o m 口t oa n yo t h e rv e r t e xi n g t h ed i a m e t e rd i a m gi st h em a x i m u m e c c e n t r i c i t yo ft h ev e r t i c e si ng v e r t e xui sa ne c c e n t r i cv e r t e xo fui fd a ( u ，v ) = e ) v e r t i c e sua n du a r em u t u a l l ye c c e n t r i ci fui sa 3 2e c c e n t r i cv e r t e xo f a n d i sa ne c c e n t r i c v e r t e xo f 珏as e t1 5 r v ( g ) i sam u t u a l t ye c c e n t r i cs e to fv e r t i c e si f f o ra l lu ，础s ，t 正a n d a r em u t u a l l ye c c e n t r i c w ed e f i n ed g ( u ，”) = 0 0 w h e n e v e rt h e r ei 8d op a t h f o i n i n gt h ev e r t i c e s 铭a n d 移t h ee c c e n t r i cd i - g r a p he d ( g ) o fg i st h ed i g r a p ho nt h es a m es e to fv e r t i c e sa sgi nw h i c h t h e r ee x i s t sa na r cf r o mv e r t e x 钍t ov e r t e x 掣i fa n do n l yi f 口i sa ne c c e n t r i c v e r t e xo fu ag r a p ha n di t se c c e n t r i cd i g r a p ha r ed i s p l a y e di nf i g u r e1 g i v e nap o s i t i v ei n t e g e r 老21 ，t h ek t hi t e r a t e de c c e n t r i cd i g r a p ho fgi s w r i t t e na se d ( g ) = e d ( e d 扣1 ( g ) ) w h e r ee d l ( g ) = e d ( g ) l e t ma n dsb et h es m a l l e s tn a t u r a ln u m b e r ss u c ht h a tf o rag r a p hgw eh a v e e d 3 ( g ) = e d “扣( g ) t h ep e r i p h e r yp ( g ) o f g r a p hg i st h e8 e to fe l l l v e r t i c e sw i t hm a x i m u me c c e n t r i c i t y t h ec e n t e rc ( c ) o fg r a p hgc o n s i s t s o fv e r t i c e so fm i n i m u m e c c e n t r i c i t y , a n dt h ev e r t i c e sw i t h i nc ( g ) a r ec a l l e d c e n t r a lv e r t i c e s t h es e to fe c c e n t r i cv e r t i c e so fc e n t r a lv e r t i c e si s d e n o t e db yc e p ( g ) l e ttb ea nu n d i r e c t e dt r e e i fc ( t ) = 让，口 ，t h e nl e t 互d e n o t et h es e to fa l lv e r t i c e sc l o s e rt o 珏t h a nt o 杉，a n dl e t b et h es e t o fa l 】v e r t i c e sc l o s e rt ot ，t h a nt o 乱 b e d c d c g e d ( a ) f 曲l r e j l e tdd e n o t ead i r e c t e dg r a p h ( d i g r a p h ) w i t hv e r t e xs e tv ( d ) a n da r c s e ta ( d ) av e r t e xt ，i ss a i dt ob er e a c h a b l ef r o mv e r t e x 让i nad i g r a p hdi f t h e r ei sad i r e c t e dp a t hf r o mt t ot ，a n dt h en u m b e ro fa r c si nas h o r t e s ts u c h p a t hi st h ed i s t a n c ef r o mut o 口，d d ， ) i ft h e r ei sn od i r e c t e dp a t hf r o m 豇t oui nd ，t h e nw ed e f i n ed n ( u ，t ，) = t h ee c c e n t r i c i t yo fav e r t e x “，e ( t ) i nad i g r a p hd i st h ed i s t a n c ef r o mut oav e r t e xf u r t h e s tf r o m 仳a v e r t e xvi nad i g r a p hdi sa ne c c e n t r i cv e r t e xo fv e r t e x “i ft h ed i s t a n c e f r o mut ovi se q u a lt oe ( ) t h ee c c e n t r i c i t ys e q u e n c eo fad i g r a p hd i s 1i n t r o d u c t i o n j j d e f t n i t i o n sa n dn o t a t i o n s 8 t h es e q u e n c eo fe c c e n t r i c i t i e so fdw r i t t e ni nn o n - d e c r e a s i n go r d e ra n di ti s d e n o t e db ye s ( d ) t h ee c c e n t r i cd i g r a p ho fad i g r a p hd ，d e n o t e db y e d ( d ) i st h ed i g r a p ho nt h es a m ev e r t e xs e ta sd w i t ha na r cf r o mv e r t e x ut o ”i ne d ( d ) i fa n do n l yi f 口i sa ne c c e n t r i cv e r t e xo fu c l e a r l y ，i fav e r t e x h a so u t - d e g r e ez e r o ，t h e nt h ev e r t e xh a sa l lt h eo t h e rv e r t i c e so ft h eg i v e n d i g r a p h a l si t se c c e n t r i cv e r t i c e s g i v e na p o s i t i v ei n t e g e r 詹1 ，t h ek t hi t e r - a t e de c c e n t r i cd i g r a p ho fdi sw r i t t e na s 露d 七( d ) = e d ( e d 扣1 ( d ) ) w h e r ee d l ( d ) = e d ( d ) l e tma n d8b et h es m a l l e s tn a t u r a ln u m b e r s s u c ht h a tf o rad i g r a p hdw eh a v e 县d 。( d ) = 刀d ”扣( d ) l e td - 1b e t h ec o n v e r s eo fd t h e nd 1i so b t a i n e db yc h a n g i n ga l lt h ed i r e c t i o n so f d w - eu s eg t od e n o t et h es y m m e t r i cd i g r a p hw h o s eu n d e r l y i n gg r a p h i sg t h u sg i st h ed i g r a p ht h a ti so b t a i n e df r o mg b yr e p l a c i n ge a c he d g e o fg b yas y m m e t r i cp a i ro fa r c s ，i fd ia n dd 2a r ed i g r a p h s ，t h e nw ed e f i n e d 1 + d 2t ob et h ed i g r a p hd lud 2w i t ha d d i t i o n a la r c sf r o me a c hv e r t e x o fd 1t oe a c hv e r t e xo f 岛w ei l l u s t r a t et h ea b o v et h r e ec o n c e p t si nf i g u r e 2 l e txb eas u b s e to fv e r t e xs e t i fa l lt h ev e r t i c e so fxd o m i n a t ev e r t e x z ，t h e nw ed e n o t ei tb yx _ 茁 f 垃u r e 2 ad i g r a p hdi st r a n s i t i v ei f ，f o re v e r yp a i ro fa r c sx ya n d y zi nd s u c ht h a t z z ，t h ea r c 。zi sa l s oi nd ( s e ef i g u r e3 ) l e tdb ead i g r a p h w ed e f i n e t h ec o m p l e m e n tdo fda sf o l l o w s ( s e ef i g u r e4 ) ： y ( d ) = y ( d ) ，u a ( d ) i f a n do n l yi f 们隹a ( d ) a ne c c e n t r i cp a t ho fv e r t e xt ，i sap a t hf r o m t oa ne c c e n t r i cv e r t e xo fu ad i g r a p hi sc o n n e c t e di fi t su n d e r l y i n gg r a p hi sc o n n e c t e d i nad i g r a p h d ，i ft h e r ei sad i r e c t e du up a t h ，t h e nw es a yt h a t 珏c a nr e a c hu a d i g r a p hi ss t r o n gi ff o re v e r yt w od i s t i n c tv e r t i c e s 札a n du ，t h e r ei sb o t ha 野拶八v 附聍 u vp a t ha n da 口一up a t h w ed e n o t et h el e n g t ho fp a t hpb yz ( p ) a d i g r a p hi sp l a n a ri fi tc a r lb ee m b e d d e di nt h ep l a n ew i t h n oc r o s s i n ge d g e s d 1 2s o m ek n o w nr e s u i t s ”一” ” 、一 “v 吣 一7 、 u 气口u口 。 、一 d 一 西 用弘r e 4 a k n o w nr e s u l t sa b o u tm i n i m u md i a m e t e ro r i e n t a t i o n s t h e o r e ma f 4 | i f 仡之3 ，t h e n ，( m 1 ，m 2 ，) s3f o ra l lp o s i t i v ei n t e - g e r s ? n 1 ，? t l 2 ，1 t h e o r e mb 【4 | ，( ) = 2f o rn 3 ，n 4a n d ，( 纸) ；3 t h e o r e mc 4 】f o rm 3 ，礼4 ，佗3f ( r n ( n ) ) = 2 t h e o r e md 4 】f o rm 2 ，( m ( 4 ) ) = 2 t h e o r e me 4 1i f2 m l m 2 ( 【m i m 1 2 j ) ，t h e n ，( m l ，m 2 ，2 ) = 2 t h e o r e mf 4 1 i f 仃3 ，n 4 ，t h e n ，( 2 ( n ) ) = 2 t h e o r e mg 【4 j ，( m ( ”) ) = 2f o ra n yi n t e g e r 仇l ，a n da n yi n t e g e r 扎3 ， e x c e p tt h ep a i r ( m ，n ) = ( 1 ，4 ) ，f o rw h i c h ，( 1 ( 4 ) ) = 3 1i n t r o d u c t i o n1 2 s o m ek n o w nr e s u t s 1 0 t h e o r e mh 捌 i f m l m 2 2 ，t h e n ，( m l ，m 2 ) = 3 f o rm l ( 【竹笏2 ) ，a n d o t h e r w i s e ，( m 1 ，m 2 ) = 4 8 k n o w nr e s u l t sa b o u tk e r n e l sa n dq u 鼬i - k e r n e l si nd i g r a p h s l e m m aa 【8 1l e t 。b eav e r t e xi nad i g r a p hd i fzi san o n - s i n k t h e nd h a sa q u a s i - k e r n e ln o ti n c l u d i n gz l e m m ab n e v e r yt o u r n a m e n tw i t h o u tv e r t i c e so fi n d e g r e e - z e r oh a sa t l e a s tt h r e ek i n g s s i n c et h ec o n v e r s eo fat o u r n a m e n ti sat o u r n a m e n t ，t h ea b o v et h e o r e m c a n b er e f o r m u l a t e df o r2 - s e r f s l e m m ac e v e r yt o u r n a m e n tw i t hn os i n kh a sa tl e a s tt h r e e2 - s e r f s l e m m ad 【1 0 j e v e r yd i g r a p hh a saq u a s i k e r n e l t h e o r e mi e v e r y d i g r a p hg = ( x ，e ) w i t h o u tk e r n e lp o 醛鹪蝴s tl e a s t t h r e eq u a s i k e r n e l s m o r e o v e rf o re v e r yi n t e g e rn 3t h e r ee x i s t sag r a p h w i t h o u tk e r n e lw h i c hp o s s e s s e se x a c t l yt h r e eq u a s i - k e r n e l s t h e o r e mj nad i g r a p hdh a so n l yo n eq u a s i k e r n e li fa n do n l yi fd h a sas i n ka n de v e r yn o n - s i n ko fdd o m i n a t e sas i n ko fd i fad i g r a p hd h a so n l yo n eq u a s i - k e r n e lq ，t h e nqi sak e r n e la n dc o n s i s t so ft h es i n k so fd t h e o r e mk nl e tdb ea d i g r a p hw i t hn os i n k t h e nd h a sp r e c i s e l yt w o q u a s i k e r n e l si fa n do n l yi fd h a sa ni n d u c e d4 - c y c l eo r2 - c y c l e ，c ，s u c ht h a t n 0v e r t e xo fcd o m i n a t e s8v e r t e xi nd - v ( c ) a n d e v e r yv e r t e xi nd v ( c ) d o m i n a t e sa tl e a s tt w oa d j a c e n tv e r t i c e si nc 1i n t r o d u c t i o n 1 2 s o m ek n o w nr e s u 招 l l t h e o r e ml 【8 la s t r o n gd i g r a p hd o fo r d e ra tl e a s tt h r e eh a sa tl e a s tt h r e e q u a s i k e r n e l s ，u n l e s sd i sa c k n o w nr e s u l t sa b o u te