（运筹学与控制论专业论文）关于图的可定向嵌入亏格分布.pdf

摘要 已知一个连通图g 和一个闭曲面s ( 无边缘的2 - 维紧流形) ，若 存在一个同胚：g s 使得s 一曲( g ) 的每一个连通分支都同胚于 一个开圆盘，则称g 在s 上有一个胞腔嵌入若s 是可定向的， 则嵌入是可定向嵌入；若s 是不可定向的，则嵌入是不可定向嵌 入图的曲面嵌入问题是拓扑图论的中心问题在本论文中图， 曲面和嵌入分别指的是连通图，闭曲面和可定向的胞腔嵌入 已知一个图g ，g 的亏格指的是它所能嵌入的曲面的最小亏 格图在各种不同亏格的曲面上有多少个不同的嵌入呢? 这就 是图的嵌入亏格分布问题由于求图的亏格是n p - 完备的，由此 可见图的嵌入亏格分布问题的难度和意义 g r o s s 和b u r s t 在1 9 8 7 年引入了图的嵌入亏格分布的概念。迄今 为止，只求出以下图类的嵌入亏格分布：c l o s e d - e n d l a d d e r s ，c i r c u l a r l a d d e r s ，m 6 b i u sl a d d e r s ，r i n g e ll a d d e r s ，d i p o l e s ，c o b b l e s t o n ep a t h s ，b o u q u e t so f c i r c l e s 和n e c k l a c e s 所用的方法主要是组合的方法，j a c k s o n 公式法 和m o h a r 覆盖矩阵法总体而言，这些方法对解决其它图的嵌入 亏格分布有局限性 2 0 0 3 年刘提出的图的联树( 1 9 7 9 的文章体现了这种思竭为嵌入 亏格分布的研究提供了理论基础 在本论文中，我们引入了图的嵌入曲面和曲面集的亏格分布 的概念通过运用图的联树我们提取了图的嵌入曲面，从而提出 了两种新方法一个是曲面生成法即利用嵌入曲面间的生成关 系求图的嵌入亏格分布的方法；另一个是曲面分类法即通过分 类曲面利用曲面集的关系计算图的嵌入亏格分布的方法通过 使用新方法和下面的新的研究结构对图的嵌入亏格分布问题展 开了系统化的研究： ( 1 ) 梯图和交叉图 ( 2 ) 梯型图和交叉型图 ( 3 ) 含有h a m i l t o n 路的3 - 正则图 ( 4 ) 3 - 正则图 ( 5 ) 一般图 它们的包含关系如下： 我们得到了梯图和交叉图的嵌入亏格分布的显式表达式，把 已知的c i r c u l a rl a d d e r s ，m 6 b i u sl a d d e r s ，c l o s e d - e n dl a d d e r s ，r i n g e ll a d d e r s 的嵌 入亏格分布简单地推出，得到了其它四类图的嵌入亏格分布， 这是对于这些图类的第一个结果 总之，这些新方法不仅推出了一些已有的结果而且可以用来 研究其它的嵌入问题 关键词：联树；蓝面生成法；曲面分类法；嵌入；嵌入曲面； 亏格分布 a b s t r a c t g i v e nac o n n e c t e dg r a p hga n das u r f a c es ( a2 - d i m e n s i o n a lc o m p a c tm a n i f o l d w i t h o u tb o u n d a r y ) ，i ft h e r ei sah o m e o m o r p h i s m 由u c ht h a te a c hc o n n e c t e d c o m p o n e n to fs - ( g ) i sh o m e o m o r p h i ct oa l lo p e nd i s c ，t h e n 咖( g ) i sa ne m b e d d i n g ( i ne a r l yr e f e r e n c e s2 - c e l le m b e d d i n g ) o ns i fs i so r i e n t a b l e ，t h e nt h ee m b e d d i n g i so r i e n t a b l e i fsi sn o n o r i e n t a b l e ，t h e nt h ee m b e d d i n gi sn o n o r i e n t a b l e h o wt o e m b e da g r a p ho nas u r f a c e ，w h i c hi sac e n t r a lp r o b l e mo ft o p o l o g i c a lg r a p ht h e o r y t h r o u g ht h i st h e s i sag r a p h ，as u r f a c ea n da l le m b e d d i n ga r ea l w a y si m p l i e da c o n n e c t e dg r a p h ，a no r i e n t a b l es u r f a c ea n da l lo r i e n t a b l ee m b e d d i n gr e s p e c t i v e l y g i v e nag r a p hg ，t h eg e n u so fgi st h em i n i m u mg e n u so ft h es u r f a c ew h i c h i tc a nb ee m b e d d e do n h o wm a n yd i s t i n c te m b e d d i n g sd o e sag r a p hh a v eo ne a c h s u r f a c e ? t h i si st h ep r o b l e mo fe m b e d d i n gg e n u sd i s t r i b u t i o nf o rag r a p h s i n c e t od e t e r m i n et h eg e n u so fag r a p hi sn p c o m p l e t e ，i ti sm o r ed i f f i c u l tt od e t e r m i n e t h ee m b e d d i n gg e n u sd i s t r i b u t i o no fag r a p hf r o mt h i sp o i n t i ti sa l s os i g n i f i c a n t t od e t e r m i n et h ee m b e d d i n gg e n u sd i s t r i b u t i o no fag r a p h g r o s sa n df u r s ti n v e s t i g a t e dt h ee m b e d d i n gg e n u sd i s t r i b u t i o no fag r a p hi n 1 9 8 7 u n t i ln o wt h ee m b e d d i n gg e n u sd i s t r i b u t i o no n l yf o rt h ec l o s e d e n dl a d d e r s ， c i r c u l a rl a d d e r s ，m s b i u sl a d d e r s ，r i n g e ll a d d e r s ，d i p o l e s ，c o b b l e s t o n ep a t h s ，b o u - q u e t so fc i r c l e sa n dn e c k l a c e sa r ed e t e r m i n e d t h e ym a i n l yu s e dt h ec o m b i n a t o r i a l m e t h o d ，af o r m u l ao fj a c k s o na n do v e r l a pm a t r i c e so fm o h a rt oc a l c u l a t et h ee m - b e d d i n gg e n u sd i s t r i b u t i o no fag r a p h h o w e v e r ，t h ea b o v em e t h o d sa r er a t h e r l i m i t e df o rt h ee m b e d d i n gg e n u sd i s t r i b u t i o ni ng e n e r a l l i uc r e a t e dj o i n tt r e e s ，i n i t i a t e di nh i se a r l yp a p e ri n1 9 7 9 ，o fag r a p hi n2 0 0 3 w h i c hp r o v i d e daf o u n d a t i o no ns t u d y i n ge m b e d d i n gg e n u sd i s t r i b u t i o n i nt h i st h e s i sw ei n t r o d u c ee m b e d d i n gs u r f a c e so fag r a p ha n dt h eg e n u sd i s t r i - b u t i o no fas u r f a c e8 e t w ee x t r a c te m b e d d i n gs u r f a c e so fag r a p hb yu s i n gj o i n t t r e e so ft h eg r a p h t h e nw ed e v e l o pt w on e wm e t h o d s o n ei sas u r f a c eg e n e r a t i n g m e t h o dw h i c hc a l c u l a t e st h ee m b e d d i n gg e n u sd i s t r i b u t i o no fag r a p hb yu s i n gt h e g e n e r a t i n gr e l a t i o n sa m o n ge m b e d d i n gs u r f a c e so fg a p l t h eo t h e ri sa8 u 咖c e s o r t i n 9m e t h o dw h i c hc a l c u l a t e st h ee m b e d d i n g 昏m u 8d s t n l o u t i o no fag r a p hb y s o r t i n gs u r f a c e sa n db yu s i n gt h er e l a t i o n sa m o n g s u r f a c es e t s w es t u d ye m b e d - d i n gg e n u sd i s t r i b u t i o nf o rt h ef o l l o w i n gt y p e so fg r a p h sb yn s i n gt h et w ot y p e so f m e t h o d sa n db yu s i n gn e ws y s t e ms t r u c t u r e ： ( 1 ) l a d d e r sa n dc r o s s e s ( 2 ) l a d d e rt y p ea n dc r o s st y p e ( 3 ) ac u b i cg r a p hw i t hah a m i l t o np a t h ( 4 ) ac u b i cg r a p h ( 5 ) ag e n e r a lg r a p h t h e i ri n c l u s i o nt e l a t i o n sa r ea 8f o l l o w s ： w eo b t a i nt h ee x p l i e te x p r e s s i o n so fe m b e d d i n gg e n u sd i s t r i b u t i o nf o rl a d d e r s a n dc r o s s e s a sas p e c i a lc o n s e q u e n c e ，t h ek n o w nr e s u l t so f c i r c u l a rl a d d e r s ，m 6 b i u s l a d d e r s ，c l o s e d - e n dl a d d e r s ，r i n g e ll a d d e r sa r es i m p l yd e d u c e d w e o b t a i n e dt h e f o r m u l a eo fe m b e d d i n gg e n u sd i s t r i b u t i o nf o rt h er e s tf o u rt y p e so fg r a p h s ，w h i c h a r ef i r s tr e s u l t sf o rt h e s e 酽印h b i ng e n e r a l ，t h e s em e t h o d sn o to n l yd e d u c es o m ek n o w nr e s u l t sb u ta l s oc a nb e u s e dt os t u d yo t h e rp r o b l e m sa b o u te m b e d d i n g s k e y w o r d s - j o i n tt r e e ；s u r f a c eg e n e r a t i n gm e t h o d ；s u r f a c es o r t i n gm e t h o d ； e m b e d d d i n g ；e m b e d d i n gs u r f a c e ；g e n u sd i s t r i b u t i o n v a c k n o w l e dg e m e n t s ia p p r e d a t em ys u p e r v i s o rp r o f y a n p e il i u sh e l pv e r ym u c h h es u g g e s t e d t h ee m b e d d i n gg e n u sd i s t r i b u t i o nt om eb a s e do nh i st h e o r e t i c a lf o u n d a t i o n ia m v e r yl u c k yt ob e c o m eas t u d e n to fh i m n oa n yw o r d se a r lb ee x p r e s s e dm yt h a n k s f o rh i m i8 h a uc a l t yf o r w a r dh i sa c a d e m i ct h o u g h t sa n dr e s e a r c hs p i r i t sa n dd e v o t e m y s e l ft om a t h e m a t i c st h o u g h o u ta l lm yl i f e ia mv e r yt h a n k f u lt op r o f h o n g - j i a nl a i ，p r o f n a i h u ax i u ，p r o f y a n q u a n f e n g ，p r o f y a n x u nc h a n g ，p r o f z h o n 曲a oj i a n g ，a s s o c i a t ep r o f r o n g x i ah a o a n dw e i l ih ef o rt h e i rh e l p s ia m o b l i g e dt ot a ow a n gs i n c es o m ec a l c u l a t i o n sa r e c h e c k e db yt h ep r o g r a m m i n gc o m p l i e db yt a ow a n gb a s e do nt h et h e o r yi n i t i a t e d i n1 9 7 9a n de s t a b l i s h e di n2 0 0 3b yy a n p e i “u ia mi n d e b t e dt om yp a r e n t sf o rt h e i rl o v ea n de n c o u r a g e m e n t s ia l s oe x p r e s s m yt h a n k st om ys i s t e rs h e n g n a nw a na n dt w ob r o t h e r s ，c h a o y a n gw a na n d x u g u a n gw a n ，f o rt h e i rs u p p o r t s c h a p t e r1 i n t r o d u c t i o n 1 1s i t u a t i o no ft h ep r o b l e m t b z o u g h o u tt h i st h e s i sas u r f a c ei sa l w a y sa s s u m e da l lo f i e n t a b l e2 一d i m e u s i o n a l c o m p a c tm a n i f o l dw i t h o u tb o u n d a r y ag r a p hi si m p n e dac o n n e c t e dg r a p h a n e m b e d d i n gi sa l w a y sa s s u m e da no r i e n t a b l ee m b e d d i n g g i v e nag r a p hga n das u r f a c es ，i ft h e r ei sah o m e o m o r p h i s m ：g _ s s u c h t h a te a c hc o n n e c t e dc o m p o n e n to fs 一曲( g ) i sh o m e o m o r p h i ct oa no p e nd i s c ，t h e n 咖( g ) i sa ne m b e d d i n g ( i ne a r l yr e f e r e n c e s2 - c e ue m b e d d i n g ) o ns 勰s h o w n i nt h e m o n o g r a p ho fl i u 【1 3 1 t o p o l o g i c a lg r a p ht h e o r yc o n c e n t r a t e so n h o wt oe m b e da g r a p ho nas u r f a c es i n1 9 6 6d u k ep r o v e dt h ei n t e r p o l a t i o np r i n c i p l e t h e o r e m1 1 1 2 】i fag r a p hh a se m b e d d i n g so nt w os u r f a c e s 耳a n d 岛w h o s e g e n e r aa l era n d tf o rr tr e s p e c t i v e l y , t h e ni th a sa ne m b e d d i n go ns kf o re a c h p o s i t i v e i n t e g e r w i t hr k t n a t u r a l l y , t h eg e n u so yag r a p h w a si n t r o d u c e d ，w h i c hi st h em i n i m u mg e n u s o fas u r f a c et h a tag r a p hc a l lb ee m b e d d e do n i na d d i t i o n ，t h ee m b e d d i n gg e n u s d i s t r i b u t i o nf o rag r a p hw a si n v e s t i g a t e db yg r o s sa n df u r s t ，w h i c hi st h ep r o b l e m w es t u d yi nt h i st h e s i s p r o b l e m 1 6 】g i v e nng r a p h ，h o wm a n yd i s t i n c te m b e d d i n g sd o e si th a v eo ne a c h s u r f a c e ? i n1 9 8 9 ，t h o m a s s e np r o v e dt h ef o l l o w i n gt h e o r e m t h e o r e m1 1 2 【1 8 】g i v e nag r a p h , i t sg e n u sp r o b l e mi sn p - c o m p l e t e 1 g i v e na n yg r a p hg ，i ft h e r ei sa ne f f i c i e n ta l g o r i t h mt od e t e r m i n et h ee m b e d d i n g g e n u sd i s t r i b u t i o no fg ，t h e nt h e r ei sa ne f f i c i e n ta l g o r i t h mt od e t e r m i n et h eg e n u s o fg t h u s o n ec a nt h i n kt h a tt od e t e r m i n et h ee m b e d d i n g g e n u sd i s t r i b u t i o no f ag r a p hi sm o r ed i f f i c u l tt h a nt od e t e r m i n ei t sg e n u s t h es t u d yo ft h e e m b e d d i n g g e n u sd i s t r i b u t i o nw i l lm a k e1 1 8k n o wg r a p h sf u r t h e r m o r e o v e r ，i tm a yg i v ea n e wi d e at os i m p l i f yt h ep r o o f so fs o m ec l a s s i c a lt h e o r e m ss u c ha st h em a pc o l o r t h e o r e m i na d d i t i o n ，i tm i g h tb ea p p l i e dt op h y s i c s ，c h e m i s t r ya n db i o l o g yt o s t u d yt h es t r u c t u r eo fm a t t e r b e f o r et h i sd i s s e r t a t i o n ，s o m ea u t h o r sh a v ed o n er e s u l t so ne m b e d d i n gg e n u s d i s t r i b u t i o n sf o rs o m ep a r t i c u l a rt y p e so fg r a p h s n l r s t g r o s sa n ds t a t m a nc a l - c u l a t e dt h ee x p l i c te x p r e s s i o n so ft h ee m b e d d i n gg e n u sd i s t r i b u t i o nf o rc l o s e d - e n d l a d d e r sa n dc o b b l e s t o n ep a t h s 【5 】m c g e o c hc o m p u t e dt h ee x p l i c te x p r e s s i o n so f c i r c u l a rl a d d e r sa n dm s b i u sl a d d e r s 【1 6 k w a ka n dl e eo b t a i n e dt h ee m b e d d i n g g e n u sd i s t r i b u t i o no fd i p o l e s 1 0 。t e s a rg o tt h ee x p l i c te x p r e s s i o n so ft h ee m - b e d d i n gg e n u sd i s t r i b u t i o nf o rr i n g e ll a d d e r s 【1 7 g r o s s ，r o b b i n sa n dt u c k e r p r o v i d e dt h ee x p r e s s i o n so ft h ee m b e d d i n gg e n u sd i s t r i b u t i o nf o rb o u q u e t s 【7 】o f c i r c l e s c h e n ，g r o s sa n dr i e p e ro b t a i n e dt h ee x p r e s s i o n so ft h ee m b e d d i n gg e n u s d i s t r i b u t i o nf o rn e c k l a c e s 【1 】l ia l s oc a l c u l a t e dt h ee m b e d d i n gd i s t r i b u t i o no f m 6 b i u sl a d d e r s ( 1 1 z h ua n dl i up r o v i d e dt h ee m b e d d i n gg e n u sd i s t r i b u t i o no f t w ot y p e so fg r a p h 8 【2 9 1 t h e ym a i n l yu s et h ec o m b i n a t o r i a lm e t h o d ，af o r m u l a o fj a c k s o na n do v e r l a pm a t r i c e so fm o h a rt oc a l c u l a t et h ee m b e d d i n gg e n u sd i s t r i - b u t i o no fag r a p h h o w e v e r ，i tl o o k st h a tt h em e t h o d sa r en o ts i m p l et oc o m p u t e o r i e n t a b l ee m b e d d i n gg e n u sd i s t r i b u t i o no fo t h e rg r a p h s ， l i ui n t r o d u c e dj o i n tt r e e s 【1 5 jo fag r a p hb a s e do nh i si n i t i a lw o r ki n1 9 7 9 【1 3 t h i sp r o v i d e saf o u n d a t i o nt os o l v ee m b e d d i n gp r o b l e m s b yu s i n gj o i n tt r e e sz h a o a n dl i uc a l c u l a t e dt h ee m b e d d i n gg e n u sd i s t r i b u t i o no ft r e e - l i k eg r a p h s 【2 8 ，a n d l ia n dl i uc o m p u t e dt h ee m b e d d i n gg e n u sd i s t r i b u t i o no fat y p eo fc u b i cg r 印h s 12 j i nt h i st h e s i se m b e d d i n gs u r f a c e so fag r a p ha r ee x t r a c t e db yu s i n gj o i n tt r e e s o ft h eg r a p h t h e nw ed e v e l o pt w on e wm e t h o d sw h i c ha r et h es u r f a c eg e n e r a t i n g m e t h o da n d8 u r f a e es o r t i n gm e t h o d 【1 9 - 2 1 1 t h es u r f a c eg e n e r a t i n gm e t h o dc a l c u - l a t e st h ee m b e d d i n gg e n u sd i s t r i b u t i o no fg r 印h sb yu s i n gt h eg e n e r a t i o nr e l a t i o n 2 a m o n ge m b e d d i n gs u r f a c e so f 擎a p h s t h es u r f a c es o r t i n gm e t h o dc a l c u l a t e st h e e m b e d d i n gg e n u sd i s t r i b u t i o nb yu s i n gt h eg e n u sd i s t r i b u t i o no fs u r f a c es e t s w e s t u d yt h ee m b e d d i n gg e n u sd i s t r i b u t i o no fag r a p hb yu s i n gt h et w om e t h o d sa n d n e ws t r u c t u r e s o m en e wr e s u l t sh a v eb e e nf o u n di n 【1 9 - 2 6 1 1 2o r g a n i z a t i o no ft h i sd e s s e r t a t i o n i nc h a p t e r2w es k e t c hal i n e a rs e q u e n c e ，a ni n v e r s es e q u e n c e ，as u r f a c e ，ag r a p h ， a ne m b e d d i n g ，a ne m b e d d i n g g e n u sd i s t r i b u t i o na n ds o m el e m m a s w ei n t r o d u c e s e v e r a lc o n c e p t sr e l a t e dt oal i n e a rs e q u e n c e ，g e n u sd i s t r i b u t i o no fs u r f a c es e t sa n d l e m m a su s e di nt h i st h e s i sb a s e do nt h et h e o r yd i s c r i b e di nl i u 【1 4 1 。 i nc h a p t e r3w ei n t r o d u c et h es u r f a c eg e n e r a t i n gm e t h o d w es h o we m b e d d i n g g e n u sd i s t r i b u t i o no ft w ot y p e so ff 印h s a n dw 名n o tt o p o l o g i c a l l ye q u i v a l e n t w h i c hh a v et h es a m ee m b e d d i n gg e n u sd i s t r i b u t i o nf o rn 3b yu s i n gt h em e t h o d t h e nw eg e n e r a l i z et h em e t h o dt oc a l c u l a t et h ee m b e d d i n gg e n u sd i s t r i b u t i o nf o r s o m et y p e so fg r 印h s a sa ne x a m p l e ，w ep r o v i d et h ee m b e d d i n gg e n u sd i s t r i b u t i o n f o rat y p eo fg r a p h sw h i c ha r en o tc u b i ci nh o m e o m o r p h i s m t h e s ea r et h ef i r s t r e s u l t sf o rs i m p l eg r a p h sw h i c ha r en o th o m e o m o r p h i et oac u b i cg r a p h c h a p t e r4i n t r o d u c e st h es u r f a c es o r t i n gm e t h o d i ns e c t i o n4 1w ed e f i n es o m e s u r f a c es e t s 研f o rp o s i t i v ei n t e g e r sm ，ja n dnw i t h1 j 1 3a n dn21 t h e g e n u sd i s t r i b u t i o nf o rt w ot y p e so fs u r f a c es e t sa r ei n v e s t i g a t e d s e c t i o n4 2s h o w s s o m et y p e so fg r a p h sw h o s ee m b e d d i n gg e n u sd i s t r i b u t i o nc a nb ec a l c u l a t e db y u s i n gt h eg e n u sd i s t r i b u t i o no f 卯s e c t i o n4 3p r e s e n t st h ee x p l i c i te x p r e s s i o n so f t h eg e n u sd i s t r i b u t i o nf o r 卵w i t hm = 1 s e c t i o n4 4s h o w st h ee x p l i c i te x p r e s s i o n s o fe m b e d d i n gg e n u sd i s t r i b u t i o nf o rl a d d e r sa n dc r o s 8 p a r t i c u l a r l y , t h ek n o w n e m b e d d i n gg e n u sd i s t r i b u t i o nf o rc i r c u l a rl a d d e r sa n dm s b i u sl a d d e r sf 16 】，c l o s e d - e n dl a d d e r s 【5 a n dr i n g e ll a d d e r s 【1 7 a r ed e d u c e di nas i m p l ew a y s e c t i o n4 5 p r o v i d e sa f o r m u l at oc o m p u t et h ee m b e d d i n gg e n u sd i s t r i b u t i o nf o rat y p eo fn o n - p l a n a rg r a p h sw i t hm i n i m u mg e n u sd e p e n d e n to nt h e i rs i z e s t h e s ea r et h ef i r s t r e s u l t sf o rn o n - p l a n a rf 8 p h sw h o s em i n i m u mg e n e r ad e p e n do nt h e i rs i z e s c h a p t e r5p r o v i d e sar e c u r s i o nf o r m u l ao ft h ee m b e d d i n gg e n u sd i s t r i b u t i o nf o r ac u b i cg r a p hw i t hah a m i l t o np a t h t h e s ea r et h ef i r s tr e s u l t sf o rt h i sk i n do f 3 g r 印h sa sk n o w nu pt on o w i nc h a p t e r6w ei n t r o d u c eas u b - j o i n tt r e e ，am a x i m a ls u b - j o i n tt r e ea n dad i s - t r i b u t i o nd e c o m p o s i t i o no fag r a p h w ep r o v i d eaf o r m u l at od e t e r m i n ee m b e d d i n g g e n u sd i s t r i b u t i o no fac u b i cg r a p h e m b e d d i n gg e n u sd i s t r i b u t i o no fag e n e r a l g r a p hi st r a n s f o r m e di n t oe m b e d d i n gg e n u sd i s t r i b u t i o no fs o m ec u b i cf a p h sb y u s i n gad i s t r i b u t i o nd e c o m p o s i t i o no fag r a p h t h er e s u l tf o rag e n e r a lg r a p hi s s e e nt ob et h ef i r s ta sk n o w nu pt on o w c h a p t e r7p r e s e n t ss o m ep r o b l e m sf o rf u r t h e rs t u d y 4 c h a p t e r2 p r e l i m i n a r i e s i nt h i sc h a p t e rw er e c a l ls o m ec o n c e p t sa n dl e m m a s f r o m 【6 ，8 ，1 3 ，1 4 ，1 5 a n d i n t r o d u c es o m ec o n c e p t sa n dl e m m a s 2 1 s e q u e n c e sa n ds u r f a c e s i nt h i ss e c t i o nw er e c a l lal i n e a rs e q u e n c e ，i n v e r s es e q u e n c e ，s u r