（运筹学与控制论专业论文）一些图的对偶带宽.pdf

中文摘要 图g 的对偶带宽是指图g 中耜邻两点最小标号差的最大值，记作百( g ) 。 对于给定的母图日，图g 在嵌入方式，下的对偶带宽为 b ”( g ，) = 。艘n g ) 州m ) ，m ) ) 图g 关于日的对偶带宽为 爵( g ) 2m a x 巩( g ，) 我们要解决的问题是对于给定的图g 和母图h 求出图g 在h 下的对偶带宽 百0 ( g ) 的值。 l i n 和y u a n 在 1 1 】中首先提出了对偶带宽问题并且给出了对偶带宽的一些 基本结论。由f 1 1 j ，即便是取g ) s1 的判定问题也是c o - n p - 完全的也就是 说：对于一般图来说对偶带宽问题是难于解决的。 本文仅考虑母图日为路的情形。设图g 的顶点数为n ，图g 在路p n 上的 嵌入可以用一一映射f ：v ( a ) _ 1 ，2 ，n ) 来表示，称为图g 的一种标号。 图g 在标号，下的对偶带宽为 b ( g ，) _ 。躲) m “) 一m ) 图g 的对偶带宽为 百( g ) 2 甲百( g ，n 本文研究了双层星，完全2 t 分树，等毛虫树，路幂图，长度为2 的路与长 度为扎的圈的乘积图，等高单毛虫树，以及m s b i u s 梯子的对偶带宽。利用一 些已知的界以及一些新的技巧，得出如下结果： 定理1 t ( d ，d ，d ) 是顶点数为n ，脊线为p = u l 珏2 钍，且如( 礼，) ：d ( 1s isk ) 的等毛虫树。则 聊 棚，= 每：燃 定理2 对于礼个顶点的树t ，其最大度( t ) ； 。那么对偶带宽 百( 丁) = n 一( ? ) 的充要条件为树t 是内点为最大度顶点的双层星。 定理3 完全2 t 分树噩强的对偶带宽百m 蝻) 幽4 竺t - 2 型一t + l 特别地，完 全二分树足，t 的对偶带宽百仍，。) = 2 一1 ， 定理4路和路r 的乘积图g = p m r 对偶带宽百( p m p n ) l 警j 一【引。当m 4 时，百( g ) l 警j - 2 特别地，当m 茎5 时，百( g ) = 【等卜l 罟j 定理5 等高单毛虫树p m ，。的对偶带宽百( p m ，。) = l 警 定理6 长度为2 的路与长度为n 的圈的乘积图p 2 xg 的对偶带宽 配吲= 毽“1 1 鬣 1n z 忙1 尚铡 定理7 m s b i u s 梯子螈，= 掣) 的对偶带宽 取耻 箍：燃 定理8p e t e r s e n 图的对偶带宽为3 关键词：标号，树，对偶带宽，带宽 2 a b s t r a c t a b s t r a c t ：t h ed u a lb a n d w i d t h o fag r a p hg ，d e n o t e db y 剪( g ) ，i st h em a x i m u m v a l u e o ft h em i n i m u ml a b e l l i n gv a r i a n c eo fa n yt w oa d j a c e n tv e r t i c e si n g - f o rag i v e nh o s tg r a p hh ，t h ed u a lb a n d w i d t ho fe m b e d d i n g f o rg i s 碥( g ，) _ 。嘛) d ( m ) ，m ) ) a n dt h ed u a lb a n d w i d t ho fg w i t hr e s p e c tt ohi s 硫( g ) = m r a x 面, , ( g ，) t h ep r o b l e mi st od e t e r m i n et h ev a l u eb h ( g ) f o rg i v e ng r a p h sg a n dh s o m ef u n d a m e n t a lr e s u l t so nd u a lb a n d w i d t ho fg r a p h sa r eg i v e nb yl i na n dy u a ni n 【1 1 b y1 1 1 ，e v e nt h ep r o b l e mo fd e c i d i n gw h e t h e rb ( g ) s 1i sc o - n p c o m p l e t e t h i s m e a n st h a tt h ed u a lb a n d w i d t hp r o b l e mi sd i f f i c u l ta n dg e n e r a l l yi n t r a c t a b l ef o rg e n e r a l g r a p h s w ec o n s i d e rt h ec a s et h a tt h eh o s tg r a p hhi sap a t hi nt h i sp a p e r s u p p o s et h a t l v ( g ) i = mt h e n ，t h ee m b e d d i n go fg i np a t hrc a ub er e p r e s e n t e da sab i j e c t i o n f ：v ( a ) u 1 ，2 ，n ) ，c a l l e dal a b e l l i n go f g ，t h ed u a lb a n d w i d t ho fl a b e l l i n gff o rg i s 吾( g ，卜诫m e i n ( g ) m 缸卜伽) | a n dt h ed u a ib a n d w i d t ho fgi s b ( g ) = m 争, c b ( g ， j i nt h i sp a p e r ，t h ed u a lb a n d w i d t ho ft w o - l a y e rs t a r s ，u n i f o r m2 t a r yt r e e s ，e q u i t a b l e c a t e r p i l l a r 、t h ep r o d u c to ft w op a t h s ，t h ep r o d u c to fap a t hw i t hl e n g t h2a n dac y c l e w i t hl e n g t hn ，( m ，n ) c a t e r p i l l a r sa n dm s b i u sl a d d e ra r es t u d i e d b yu s i n gs o m ek n o w n b o u n d sf o rd u a lb a n d w i d t ha n ds o m en e ws k i l l s ，w eo b t a i nt h ef o l l o w i n gm a i nr e s u l t s ， t h e o r e m1 l e tt ( d ，d ，d ) b ea ne q u i t a b l ec a t e r p i l l a ro nnv e r t i c e sw i t ht h es p i n e p = l7 2 2 t 船a n d 曲( 札。) = d ( 1 i 女) t h e n - b ( t ( d ，d ，d ) ) = 。一弭， tn l r ， 3 i fkl se v e n i fk i so d d t h e o r e m2 f o rat r e etw i t h 礼v e r t i c e sa n dw i t ha ( t ) 1 2 ，b ( t ) = n a ( t ) i f a n do n l yi ft i sa t w o - l a y e rs t a rs u c ht h a tt h ec e n t e ro fi n n e r s t a ri so fd e g r e e ( t ) t h e o r e m3 t h ed u a lb a n d w i d t ho fu n i f o r m2 t a r yt r e et 2 啪i s 百( 乃啪) 垡岂4 t - 三2 型一 + 1 e s p e c i a l y , t h ed u a lb a n d w i d t ho fu n i f o r mb i n a r yt r e e 马，ki s 再( 是，女) = 2 一l t t h e o r e m4 t h ed u a lb a n d w i d t ho ft h ep r o d u c to ft w op a t h sp ma n dr ( m n ) i s 百( 只。xr ) i 警j 一【警j w h e nm 4 ，百( g ) 曼l 警j 一2 e s p e c i a l y , w h e nm 墨5 ， 百( g ) = 【等j 一【剖 t h e o r e m5 t h ed u a lb a n d w i d t ho f ( m ，n ) c a t e r p i l l a rp m ，。i s 百( 昂，。) = 【警j t h e o r e m6 t h ed u a lb a n d w i d t ho ft h ep r o d u c to fap a t hw i t hl e n g t h2a n da c y c l e w i t hl e n g t hni s y ( p 2 g ) = 一n - - 2 1 , i f n i f n i i s e so d d , t h e o r e m7 t h ed u a lb a n d w i d t ho fm s b i u sl a d d e r 螈( 肛甲) i s 否( 呱) = n 札- 一1 2 nn l se v e n i fni so d d t h e o r e m8 t h ed u a lb a n d w i d t ho fp e t e r s e ng r a p hi s3 k e yw o r d s ：l a b e t h n g ；t r e e ；d u a lb a n d w i d t h ；b a n d w i d t h c h a p t e r1 i n t r o d u c t i o n i nt h i sc h a p t e r ，w ep r e s e n tag e n e r a li n t r o d u c t i o nt ot h et h e s i s ，t h et h e s i si sd i v i d e d i n t ot h r e es e c t i o n s i ns e c t i o n1 1 ，w eg i v eab r i e f i n t r o d u c t i o nt oo u rp r o b l e m s i ns e c t i o n 1 2 ，w el i s tb a s i cn o t a t i o n sa n dd e f i n i t i o n su s e di nt h i st h e s i s i ns e c t i o n1 3 ，w es u r v e y t h em a i nk n o w nr e s u l t sw h i c ha r eu s e f u lf o rt h et h e s i sa n dl i s tt h em a i nr e s u l t so ft h e t h e s i s 1 1i n t r o d u c t i o na n d p r o b l e m f o r m u l a t i o n t h eb a n d w i d t hp r o b l e mf o rg r a p h sr e p r e s e n t i n gac o n n e c t i o no rl i n k a g er e l a t i o n ，d u e t oi t st h e o r e t i ca n da p p l i e di n t e r e s t s ，h a sb e e ne x t e n s i v e l ys t u d i e ds i n c e1 9 6 0 s l e tu s r e c a l lt h eg e n e r a lf r a m e w o r ko ft h ep r o b l e ma sf o l l o w s ( s e e 2 ，5 】f o rd e t a i l s ) w ea r eg i v e nah o s tg r a p h 打w h i c hr e p r e s e n t sal a y o u ts t r u c t u r e ，s u c ha sap a t h ，a c y c l e ，am e s h ，o ra c u b e l e tg = ( k e ) b e a s i m p l eg r a p hw i t hv e r t e xs e tv a n de d g es e t e a ne m b e d d i n go fgi nhi sa ni n j e c t i o n ，：v ( a ) o y ( 日) t h eb a n d w i d t hp r o b l e m ( i ng e n e r a lf o r m ) i st of i n da ne m b e d d i n g ，s u c ht h a tt h em a x i m u ms t r e t c ho ft h ee d g e s o fgi sm i n i m i z e d t h eb a n d w i d t ho fe m b e d d i n gff o rg i st h u sd e f i n e da s 嘞( g ，) _ 。m e a x ( g ) 妇( m m t ，) ) ， w h e r ed h ( x ，y ) d e n o t e st h ed i s t a n c eb e t w e e nza n d yi nh f u r t h e r b n ( g ) = 叫n b n ( g ，) i sc a l l e dt h eb a n d w i d t ho fgw i t hr e s p e c tt oh ，w h e r et h em i n i m u mi s t a k e no v e ra l l e m b e d d i n g s t h i so p t i m i z a t i o np r o b l e mc o m e sf r o mm a n ya p p l i c a t i o na r e a s js u c ha s s p a r s em a t r i xc o m p u t a t i o n s ，v l s id e s i g n s ，c o m m u n i c a t i o nn e t w o r k s ，a n dc o d i n gt h e o r y n o t et h a tt h er e l a t i o nr e p r e s e n t e di ng r a p hg i ss o m ek i n do fc o n n e c t i o no rl i n k a g e ；a n d s ot h eg o a lo f e m b e d d i n g i st om a k et h ea d j a c e n tv e r t i c e sa sc l o s ea sp o s s i b l e h o w e v e r ，s o m ep r a c t i c a lp r o b l e m si m p e lu st oc o n s i d e ra ni n v e r s ep r o b l e m f o re x - a m p l e ，t h ev e r t i c e ss t a n df o rs o m es e n s i t i v ef a c i l i t i e so rc h e m i c a lm e d i c i n e sw h i c hw o u l d i n t e r f e r ef r o me a c ho t h e ri ft h e ya r ep u tt o oc l o s e a l s o ，i nt h ec h a n n e la s s i g n m e n ta n d t c o l o r i n gp r o b l e m ，f 2 0 】t h ev e r t i c e so fg a r et r a n s m i t t e r sa n da ne d g e r e p r e s e n t sc o n f l i c t 5 i ti sn a t u r a lt oa s s i g nc h a n n e l st ot r a n s m i t t e r si ns u c haw a yt h a tc o n f l i c t i n gt r a n s m i t t e r sr e c e i v ec h a n n e l sa ss e p a r a t ea sp o s s i b l e s i m i l a rs i t u a t i o na p p e a r si ut h el o c a t i o n p r o b l e m s ：t h ec e n t e rp r o b l e ma s k sf o rf i n d i n gal o c a t i o nf o ran e wf a c i l i t yf r o mw h i c h t h ef a r t h e s tc l i e n ti sa sc l o s ea sp o s s i b l e ；w h i l et h eo b n o x i o u sc e n t e rp r o b l e mi st of i n da c e n t e r ( e g ，at o x i ca g e n t ) b e i n g l o c a t e da sf a ra w a ya sp o s s i b l ef r o mt h eg i v e ns i t e s ，【2 1 】 b a s e do nt h i sm o t i v a t i o n w ep r o p o s et h ed u a lb a n d w i d t hp r o b l e ma sf o l l o w s f o rag i v e nh o s tg r a p hh ，t h ed u a lb a n d w i d t ho f e m b e d d i n g ，f o rg i s b 日( g ，+ ，) _ 。，躲) d h ( f ( u ) ，m ) ) a n dt h ed u a lb a n d w i d t ho fgw i t hr e s p e c tt ohi s 磊( g ) = n _ 日( g ，n t h e p r o b l e mi st od e t e r m i n et h ev a l u eb s ( qf o rg i v e ng r a p h sg a n dh w ef o u n dt h a t t h ed u a lp r o b l e mi sq u i t ed i f f e r e n ti nn a t u r ef r o mt h e o r i g i n a lo n e i nt h i sp a p e r ，w ec o n s i d e rt h ec a s et h a tt h eh o s tg r a p hh i sap a t h s u p p o s et h a t y ( g ) i = 礼t h e n ，t h ee m b e d d i n go fgi np a t hr c a nb er e p r e s e n t e da sab i j e c t i o n ，：y ( g ) _ 1 ，2 ，礼 ，c a l l e dal a b e l l i n go f g t h eb a n d w i d t ha n dd u a lb a n d w i d t ho f l a b e l l i n g | f o rg a r e b ( g ，) _ 。m e a x f g 、i f ( u ) 一( v ) l ， b ( g ，) _ 。蕊) 坝“) 一弛圳， r e s p e c t i v e l y a n dt h eb a n d w i d t ha n dd u a lb a n d w i d t ho fga r e b ( g ) = r a i n b ( g ，) 百( g ) 2 甲百( g ，) r e s p e c t i v e l y a l a b e l l i n g ，i sc a l l e da no p t i m a ll a b e l l i n gf o r 百( g ) i fi ta t t a i n st h ea b o v e m a x i m u mv a l u e f o re x a m p l e ，f i g u r e1 1s h o w sb a n d w i d t hl a b e l l i n gf o rg r a p h s p 4 ，瓯a n d 3 i n g e n e r a l ，口( p n ) = 1 ，b ( g ) = 2 ，b ( ，。) = m + f n 2 一1f o rm s 礼 6 i 2 4 3 5 34 2 5 67 f i g u r e1 1b a n d w i d t hl a b e l l i n g sf o rp 4 ，c 7a n dk 2 ，3 t h er e a d e rs h o u l de s p e c i a l l yn o t et h eo r i g i n a ls u r v e ya r t i c l eo nb a n d w i d t hb yc h i n ne t a 1 【2 】t h i sp r o v i d e sm a n yo ft h ek e yc o n c e p t sa n di n e q u a l i t i e su p o nw h i c hm o r er e c e n t w o r ki sb a s e d s o m ea d d i t i o n a ls u r v e ym a t e r i a li si n c l u d e di nc h u n g 【5 】a n dl a i 【9 j p a p m ：l i m i t r i o u 1 3 】p r o v e dt h a tt h eb a n d w i d t hp r o b l e m i sn p c o m p l e t ei ng e n e r a l l a t e r i tw a ss h o w nt h a tb a n d w i d t hp r o b l e mi sn p c o m p l e t ee v e nf o rt r e e so fm a x i m u m d e g r e e 3 【7 】a n df o rc a t e r p i l l a r so f h a i rl e n g t h3 1 2 】h e n c e ，r e s e a r c h e r st u r nt h e i ra t t e n t i o n st o s p e c i a lg r a p h s ，c r i t i c a lg r a p h sa n do p e r a t i o n s ( f o re x a m p l e s e e 【3 ，4 ，6 ，1 5 ，1 6 ，1 7 ，1 8 ，1 9 】) ac o n s i d e r a b l ea m o u n to fw o r kh a sb e e np u b l i s h e dp r o v i d i n gb o u n d so nt h eb a n d w i d t ho f g r a p h s t h et w om o s te f f e c t i v eb o u n d sa r ed u et oh a r p e ra p p r o a c hi s 】a n dl o c a ld e n s i t y l o w e rb o u n d 【1 0 f i g u r e1 2s h o w sd u a lb a n d w i d t hl a b e l l i n gf o rg r a p h sp 4 ，c 6a n d 娲3 - i ng e n e r a l ， b ( r ) = 【割，胃( g ) = p n i - - 一1 j ，b ( i f m ，。) = 1 f r o mt h i s ，w ek n o wt h a tt h eb e h a v i o ro f d u a lb a n d w i d t hi sq u i t ed i f f e r e n tf r o mt h a to fb a n d w i d t h l i na n d y u a nf 1 1 1s h o w e dt h a t b ( g ) = m a x k ：磺c 召) + 1sb ( 召) + 1 ，w h e r e 百d e n o t e st h ec o m p l e m e n to f ag r a p h go nn v e r t i c e s h o w e v e r ，i ti sw e l lk n o w nt h a tb ( a ) = m i n k ：gc 磁) t h i ss h o w s t h er e l a t i o no fb a n d w i d t ha n dd u a lb a n d w i d t h ，a n ds oi t i sa n o t h e re x p l a n a t i o no ft h e n a m eo fd u a lb a n d w i d t h 3 1 4 2 4 7 36 5 2 45 12 3 f i g u r e1 2d u a l b a n d w i d t h l a b e l l i n g sf o rp 4 ，c 7a n d 岛3 s o m ef u n d a m e n t a lr e s u l t so nd u a lb a n d w i d t ho fg r a p h sa r eg i v e nb yl i na n dy u a n i n u 】b y 【1 1 ，e v e nt h ep r o b l e mo fd e c i d i n gw h e t h e r 百( g ) 1i s c o - n p c o m p l e t e t h i sm e a n st h a tt h ed u a lb a n d w i d t hp r o b l e mi s d i f f i c u l ta n dg e n e r a l l yi n t r a c t a b l ef o r g e n e r a lg r a p h s ，t oo u rk n o w l e d g e ，t h e r ei sn ok n o w nr e s u l t so nd u a lb a n d w i d t h e x c e p t t h el i t e r a t u r ef n l h e n c e ，w er e s t r i c to u r a t t e n t i o no u s p e c i a lg r a p h ，s u c ha sd o u b l es t a r ， u n i f o r m 2 t - a r yt r e e s ，( m ，n ) c a t e r p i l l a r ，e q u i t a b l ec a t e r p i l l a r s ，p m 只，p 2 g ，p e t e r s e n g r a p ha n ds oo n 7 1 2b a s i ct e r m i n o l o g y h e r ew e p r e s e n ts o m e b a s i cn o t a t i o n sa n dd e f i n i t i o n st h a tw i l lb eu s e dt h r o u g h o u tt h i s p a p e r n o t a t i o n sn o td e f i n e dh e r ef o l l o w 1 a n d 【1 4 g r a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t ea n ds i m p l e ag r a p hg c o n s i s t so fav e r t e x s e ty ( g ) ，a ne d g es e t 露( g ) ，a n da ni n c i d e n c er e l a t i o nt h a ta s s o c i a t e sw i t he a c he d g e e e ( c ) a s e to fv e r t i c e s u ，钉) ，c a l l e d i t se n d v e r t i c e s w eu s et h es y m b o l s 上，( g ) a n d ( g ) ，r e s p e c t i v e l y , t od e n o t et h en u m b e r so fv e r t i c e sa n de d g e s w h e n “a n dua r e e n d v e r t i c e so fa ne d g ee w es a yt h a t 让a n dva r ea d j a c e n ta n dt h a tua n dua r ei n c i d e n t w i t he w h e nt w ov e r t i c e sa r ea d j a c e n t ，t h e ya r en e i g h b o r s f o rx 矿( g ) ，t h en e i g h b o r s e t 0 ( x ) o f xi sd e f i n e db y n a ( x ) = y v ( g ) x ：t h e r e i sz xs u c ht h a tx y e ( g ) ) g ( 。) ) i sw r i t t e ni ns h o r t e rf o r m a sa b ( z ) f o r 。y ( g ) ，t h en u m b e ro f n e i g h b o r so f x i ngi sc a l l e dt h ed e g r e eo f 岳，a n di sd e n o t e db yd e g a ( x ) ，i e ，d e g a ( x ) = i n a ( z ) i 0 ( z ) a n d d e g a ( x ) a r e ，r e s p e c t i v e l y ，a b b r e v i a t e dt on ( x ) a n dd e g ( x ) w h e n t h e r ei sn oc o n f u s i o n a r i s i n g t h em i n i m u md e g r e ea n dm a x i m u md e g r e ea m o n g t h ev e r t i c e so fag r a p hga r e d e n o t e db y5 ( g ) a n d ( g ) ，r e s p e c t i v e l y i f e v e r yv e r t e xh a s d e g r e ed ，t h e ng i sd - r e g u l a r a p a t hi sag r a p hw h o s e v e r t i c e sc a nb el i s t e di na no r d e rs ot h a tt h ee d g e sa r e p r e c i s e l y t h ep a i r so fc o n s e c u t i v ev e r t i c e s t h ef i r s ta n dl a s tv e r t i c e so fap a t ha r ek n o w na si t s e n d v e r t i c e s ；ap a t hw i t he n d v e r t i c e sxa n dyi sa n 扛，y ) 一p a t h ac y c l ei sag r a p hw h o s e v e r t i c e sc a nb el i s t e d c y c l i c a l l ys ot h a tt h ee d g e sa r ep r e c i s e l yt h ep a i r so fc o n s e c u t i v e v e r t i c e s w eu s ert od e n o t et h ep a t h sw i t hnv e r t i c e s ，a n dgt od e n o t et h ec y c l e sw i t h nv e r t i c e s af o r e s ti sa g r a p hc o n t a i n i n gn oc y c l e ac o n n e c t e df o r e s ti sat r e e as u b s e t so fvi sc a l l e da ni n d e p e n d e n ts e to fgi fn ot w ov e r t i c e so fsa r ea d j a c e n ti nga s u b s e tso fvi sc a l l e dac l i q u eo fgi fe v e r yt w ov e r t i c e so fsa r ea d j a e e n ti ngt h e s u b g r a p hi n d u c e db yac l i q u eo fnv e r t i c e si s c a l l e dac o m p l e t eg r a p h 凰ac o m p l e t e b i p a r t i t eg r a p hi sas i m p l eb i p a r t i t eg r a p hw i t hb i p a r t i t i o n ( x ，y ) i nw h i c he a c hv e r t e x o fxi sj o i n e dt oe a c hv e r t e xo fy ；i fl x l = ma n dl y l = n ，s u c hag r a p hi sd e n o t e db y k s n t h ec o m p l e m e n t o fag r a p hg ，w r i t t e ng ，i st h es i m p l eg r a p hw i t ht h es a m ev e r t e x s e ta sg ，s u c ht h a t 札甜e ( g ) i fa n do n l yi f ”甜ge ( g ) t h ed i s t a n c ed ( x ，y ) b e t w e e nt w ov e r t i c e s 王a n dyi st h el e n g t ho ft h es h o r t e s tp a t h b e t w e e nt h e mt h ed i a m e t e ro fa g r a p h i st h em a x i m u mo fd ( z ，y ) o v e ra l lp a i r so fv e r t i c e s z ，y ag r a p hi sc o n n e c t e di f , f o re v e r yt w ov e r t i c e sua n du ，i tc o n t a i n sa ( 札， ) 一p a t h t h ec o m p l e x i t yo fad e c i s i o np r o b l e m ( t h a ti s ，ap r o b l e mw i t hy e s n o a n s w e r ) i st h e 8 m i n i m u mw o r s t c a s er u n n i n gt i m eo v e ra l la l g o r i t h m st h a ts o l v ei t e x p r e s s e da saf u n c t i o n o ft h ei n p u ts i z e t h ec l a s so fa l ld e c i s i o np r o b l e m st h a ta r es o l v a b l ei np o l y n o m i a lt i m ei s d e n o t e d b y p ap r o b l e mi si nn p ，t h ec l a s so f n o n d e t e r m i n i s t i cp o l y n o m i a l t i m ep r o b l e m s ， i ft h e r ei sap o l y n o m i a l t i m ea l g o r i t h mt ov e r i f yy e sa n s w e r ap r o b l e mi sn p h a r di f t h e r ei sap o l y n o m i a l t i m et r a n s f o r m a t i o nf r o ma n yp r o b l e mi nn pt ot h ep r o b l e ma t h a n d i fi ta l s ob e l o n g st on p t h e ni ti sn p c o m p l e t e t h ec l a s sc o - n pi st h ec l a s so fa l l p r o b l e m st h a ta r ec o m p l e t m e n t so fp r o b l e m si nn p w ed e n o t et h el a r g e s ti n t e g e rn ol a r g e rt h a nzb yl 上j ，a n ds i m i l a r l y 石 d e n o t e st h e s m a l l e s ti n t e g e rn os m a l l e rt h a nz 1 3 s u r v e yo fk n o w nr e s u l t sa n dm a i nr e s u l t si nt h e t h e s i s i nt h i ss e c t i o nw el i s ts o m ek n o w nr e s u l t sr e l a t e dt ot h et h e s i sa n dm a i nr e s u l t so b t a i n e di nt h et h e s i s t h e o r e m 1 1 【1 1 】l e t gd e n o t et h ec o m p l e m e n t o fa g