（基础数学专业论文）图的书式嵌入.pdf

中文摘要 本文研究零向煎皇堕堡图的毫塞壁厶间墅 书式嵌入的“书”是由一条书脊和多页书页构成其中书脊为一条 直线，书的每一页是由书脊所界定的半平面给定图g 的书式嵌入包括 两部分内容；首先将g 的顶点按照一个由线性标号所定义的顺序嵌入书 脊上，其次将e ( g ) 中的每条边分放于各页，使得每页中的边均可画在 该页上而互不相交 ，衡量图g 书式嵌入优劣的指标有两个：书页数与页宽相对于已知 顶点嵌入方式的书页数定义为在该顶点嵌入方式下，使图g 可嵌入的最 少页数；而称在各种顶点嵌入方式下可嵌入图的书的最少页数为图g 的 书页数；每页的页宽则定义为每页中相交于书脊任意垂线的最多边数； 图g 在相对于给定顶点嵌入下的页宽定义为此嵌入下所有页宽的最大 数；而图g 的页宽为所有顶点嵌入方式下的最少页宽歹 所谓图的书式嵌入问题即寻求以单个或两个指标为目标的最优嵌 入本文将以书页数为目标研究有关书式嵌入问题。 图的书式嵌入问题有多种定义方式，在本文中等价地定义为下述图 的标号问题 ，给定n 个顶点的简单图d = ( ke ) ，为y 一 l ，2 ，n ) 的一一 映射，任意，( ”) l ，2 ，n ) ，称作顶点”的标号，若令嘶= f “( i ) ，则 ，也可视为顶点在书脊上的线性顺序任意两条边x y ，u ”e 称为相交 的当且仅当f ( u ) ，( 。) f ( v ) f ( n ) 或者f ( x ) ，( ) 4 l 4 眠n 5 ( 4 ) 路与瞬的强乘积尸mo g 的书页数为 p n ( p , 。中c 。) ： 3 m = 2 i 4 1 9 1 , 23 ( 5 ) 5 圈与圈的强乘积( ：。子( ：，有p n ( c t o g ) = 6 2 书页数与其它图论参数的关系 该文所讨论的图论参数为：树宽丁( g ) ，路宽p w ( g ) ，带宽b ( g ) ， 割宽c ( g ) ，循环带宽b 。( f ? ) ，以及循环割宽c c ( g ) 下述结果证明并 推广了g a n l e y 和h e a t h 猜想 ( 1 ) 对于任意图g ，有p n ( t w ( g ) f 2 ) 图的书页数，树宽，路宽，带宽的关系如下： p n ( g ) t 1 4 7 ( g ) p w ( g ) sb ( g ) ( 3 ) 图的书页数，树宽，路宽，割宽的关系如下 p n ( g ) st w ( g ) sf w ( g ) sc ( g ) ( 4 ) 若平面图g 满足t w ( g ) = 6 ( g ) = 3 ，则有p n ( g ) = 2 其中 研o ) 为g 的最小度 ( 5 ) 对于1s s4 的树宽临界图，均有tp ( g ) t w ( g ) 1 ( 6 ) 设l y ( g ) l = n ，b 。( 一) = k ，且叫n ，则有p n ( g ) sb 。( g ) ( 7 ) 设i y ( g ) f = n ，b a g ) = k ，且，2 - - 1 ( m o d k ) ，贝0p n ( g ) b 。( g ) 十 1 ( 8 ) 令j y ( g ) i = n ，b 。( g ) = k ，且”= m k + r ( 0 r k ) 则有 p n ( g ) b r ( “) + f 者i ( 9 ) 对于图g ，有p n ( g ) ( 。( g ) 。 3 书页数的性质 有关书页数的刻划仍是一个未解问题本文讨论了图的某些运算的 书页致以及一类具有最大书页数的特殊图 ( 1 ) 给定图e ( g ) ，对任意e e ( g ) ，p n ( g l e ) sp n ( g ) + 1 ( 2 ) 给定图g ，对任意2 度顶点“e 矿( g ) ，令g 为收缩顶点“所得 到的图，则有p n ( g 7 ) p n ( g ) + j ( 3 ) 3 图g l 关于g 2 的加冠图记作d 1o g 2 ，则 p n ( g 1 og 2 ) m a x p n ( g 1 ) ，p n ( g 2 ) + l ( 4 ) 对任意n 芝6 的偶数，( 孑1 是具有最大书页数的图 4 近似算法 迄今为止，除了平面图外，对于一般图，并未发现多项式近似算法， 即使已有的上界也全部是渐进的本文讨论了弦图的书页数，得到结果： 弦图的书式嵌入具有2 近似算法 图的书式嵌入有着广泛的实际来源与极强的应用背景，有关书式嵌 入的研究结果不仅可以应用于各个领域，而且对于算法和复杂性研究也 具有一定的理论价值、7 y 7 a c k n o w l e d g e m e n t f i r s to fa 1 1 ，1w i s ht oe x v e s sl w 、，e l yd e e pg r a t i t u d et om ys u p e r v i s o r p r o f l i ny i x u n ，f o rh i sp a t i e n ta n ds t n a r ti n s t r u c t i o nt om ys t u d y t h er e s e a t c hw o r kc o u l dn o tb eu n d e r t a k e no rc o m p l e t e dw i t h o u th i s g u i d a n c e 1l e a r nm u c h f r o mh i mn o to n l yo i lm a j o r k n o w l e d g eb u ta l s o o ns c i e n t i f i cs p i r i t i ti sa l s ow o l 、t hf o l i n el e a r n i n gh i sa t t i t u d et os c i e n c e a n ( 1 l i f o 1o f f e rm ys i n c e r et h a n k st oz h e n g z h o uu n i v e r s i t y ，d e p a r t m e n to f m a t h e m a t i c s ，f o rg i v i n gr i l et h es t u d y i l l go p p o r t u n i t y ia mg r a t e f u lt o m yc l a s s m a t e sw h o a r eg o o de n o u g ht oc r i t i c i z ea n de v a l u a t et h ee a d y d r a f t so fm y d i s s e r t a t i o n s p e c i a lt h a n k sa r eg i v e nt op r o f y n a nj i n j i a n g f o rh i sk i n dh e l p ig r e a t l yb e n e f i tf r o mt h e i rc o m m e n t sa n dih o p et h a t t h i sd i s s e r t a t i o nr e f l e c t st h e i rc o n t l i b u t i o n s 1w o u l da l s ol i k et ot h a n km yc o l l e a g u e si n d e p a r t m e n to fb u s i n e s s a d m n i s t r a t i o n ，z h o n g y u a ni n s t i t u t eo ft e c h n o l o g y io w e as p e c i a ld e b t o f g l 。a t i t u d et om r s h ec a i x i aw h o h e l p e d pi et oc o m p i l et h ed i s s e r t a t i o n a n dm a d ev a l u a b l es u g g e s t i o n so i i t sc o n t e n t j 1 1 p a r t i c u l a r l y , ia p p r e c i a t ef oz m ym s b a u d a n dm y d a u g h t e r ss u p p o r t io w e al o to f e n c o n r a g e m e n l f r o l nt h e mi nm y r e s e a r c hw o r k f i n a l l y 、1w o u l d1 i k et ot h a n ka l lm yf r i e n d s ，n a m e da n du n n a n e d 、 w h oh a v eh e l p e di m m e a s u r a h l yi ：it h ep r o d u c t i o no ft h i st h e s i s 1w i s ht o a c k n o w l e d g e t h e c o n t i n u i n gs u p p o r ta n di n s p i r i n gp a i n t i n g sf r o mt h e m 本文常用术语记号 本文仅考虑有限无向简单图给定一个图g ，v ( a ) 、e ( g ) 分别 表示图g 的顶点集与边集，为i + - 1 ，2 ，n ) 的一一映射，任意 ， 1 ，2 ，n ) ，称作顶点t ，的标号，若令u i = 7 - 1 ( i ) ，则，也可视为 顶点在书脊上的线性顺序任意两条边x y ， l t l ) e 称为相交的当且仅当 ，( n ) ，( 。) f ( v ) ，( ) 或者，( r ) ，( “) f ( y ) e t h ev e r t e xw i t h l a b e l i t h e n t h el a b e l i n gfc a nb ea l s or e g a r d e da hh l i n e m 。o r d e r i n g 【n l ，i t 2 ， f ) 0 1 1 fh es p i n eo ft h eb o o k t w o e d g e s1 1 1 r y e a r es a i dt ob ec r o s s i n g i fa l l do n l yi ff ( u ) f ( x ) 九 ( ) 0 1 f ( r ) ，( “) f ( y ) 2o t m = n = 3 p n ( p m op n ) = 3 ， ? = 3 ，z 4o r m = 4 ，r l 4 ， l 4 眠，j 5 ( 4 ) f o rg r a p hp m 0 ( j 。 p v ( p m “= 般筹n = 3 2 ( 5 ) f o rg r a p h ( 1 。0 n ， p v ( ( _ j ，；+ ( ：。) = 6 2 r e l a t i o n sw i t ho t h e rg r a p h t h e o le r i cp a r a m e t e r s t h e p a r a m e t e r sw e c o n s i d e l a r pt h pt r e e w i d t ht w ( g ) ，t h e p a t h w i d t l l 尸w ( g ) ，t h eb a n d w i d t hb ( g ) ，t h ec u t w i d t hc ( g ) ，t h ec y c l i cb a n d w i d t l l b c ( g ) ，t h ec y c l i cc u t w i d t h ( 1 ( ? ( “) t h en e x tr e s u l tp r o v e 8a n d g e n e l a 1 一 i z e st h ec o n j e c t u r ep o s e db yg a n l e 3 ，a n dh e a t h 2 0 ( 1 ) f o ra n yg r a p hg ，p n ( c ) t l , i ( g ) 3 ( 2 ) p n ( g ) t w ( g ) p w ( g ) b ( g ) ( 3 ) p n ( g ) t w ( g ) sp w ( g ) c g ) ( 4 ) f o rp l a n a rg r a p hg s u c ht h a t7 w ( g ) = j ( g ) = 3 ，p n ( g ) = 2 w h e r e 研g ) s t a n d sf o rt h em i n i n l t m ld e g l e eo fg ( 5 ) f o rt r e e w i d t hk - c r i t i c a lg r a p h sw i t hk 4 ，p n ( g ) t w ( g ) 一1 ( 6 ) l e ti v ( g ) f = ”，b 。( g ) = “a 1 1 ( 1 i 仃t h e np n ( g ) b c ( g ) ( ? ) l e t1 y ( g ) f = n ，b 。( g ) = k ，a n d1 l 三l ( m o d ) t h e n p n ( g ) b 。( “) + l - ( 8 ) l e ti y ( g ) l = n ，b c ( g ) = 七，a l l d 扎= m k + r ( 0 r 南) t h e n p n ( g ) b 。( 一) + f 羔 ( 9 ) f o rg r a p hg ，w eh a v ep ( g ) sc c ( v ) 3 p r o p e r t i e so fp a g e n u m b e l t h ep r o b l e mo fc h a r a c t e r i z a t i o no fp a g e n u m b e ro fg r a p h sr e m a i n s o p e n t h ep r o p e r t i e sw e c o n s i d e ra r ep a g e n u m b e ro f o p e r a t i o n so fg r a p h s a n dt h eg r a p hw i t hm a x i m u m p a g e n u m b e r ( 1 ) g i v e nag r a p hg ，f o ra u yf e ( g ) ， p ( g e ) sp n ( g ) + 1 ( 2 ) g i v e nag r a p hg ，a n dav e r t e xl v ( g ) w i t hd ( u ) = 2 ，l e tg b et i l er e s u l t i n gg r a p ho b t a i n e df l o m “h y c o n t r a c t i n gv e r t e x t h e n p n ( g 7 ) sp ( ( j ) + 1 ( 3 ) g i v e ng r a p h sg 1a n dg 2 ，l e tt h ec 0 1 o n ao ft h e mb ed e n o t e db y g 1o g 2 t h e n p n ( g 10 g 2 ) d l a x p n ( g 1 ) ，p n ( g 2 ) 卜 1 ( 4 ) i fn 6 【ni se v e l l ) ，t h e n ( 1 辜i st h em a x i m u mp a g e n u l n be 1 g r a p h 4 a p p r o x i m a t i o na l g o r i t h m u pt on o w ，t h e r ei s 1 2 0p o l y n o n l i ma p p r o x i m a t i o na l g o r i t h mf o rp a - g e n u m b e re x c e p tf o rp l a n a , 9 1 1 a p h s a n dm o s t o ft h ek n o w n u p p e r b o u n d s a r ea s y m p t o t i c w ed i s c u s st h ep a g e n i i n l b e ro f c h o r d a lg r a p h sa n do b t a i n t h ef o l l o w i n gr e s u l t ： t h e r ee x i s t sa2 - a p p r o x i m a t i o na l g o r i t h mf o rc h o r d a lg r a p h s t h ep r o b l e mo fb o o ke m b e d d i n go l g r a p h si ss t l o n g l yf r o mp r a c t i c e t h er e s e a r c hr e s u l t sn o to n l yc a nb el l s e di n t ov a r i o u sp r a c t i c a la p p l i c a - t i o nf i e l d s ，b u ta l s oh a v es i g n i f i c a n c et oa l g o r i t h ma n dc o m p l e x i t yt h e o r y 5 c h a p t e r1 i n t r o d u c t i o n i ti sag e n e r a li n t r o d u c t i o no ft h et h e s i s a n di ti 8d i v i d e di n t of o u r s e ( 1 i o n s s e c t i o n1 1 g i v e ss p 、e r a l f b i l l n l a t i o n so fb o o ke m b e d d i n g p r o b l e l l la n di t s b a c k g r o u n d s e c t i o n 12l i s t st h eb a s i cn o t i o n sa n dt e r m i n o l o g yt h a tw o u l db eu s e di nt h et h e s i s s e c t i o n1 3 s u r v e y st h ek n o w n r e s u l t si nv a r i o u sa s p e c t s s e c t i o n1 4i n t l o d u e e 8t h eo r g a n i z a t i o no ft h e d i s s e r t a t i o na n dt h en - i a i nl e s l l l t s 6 1 1t h ep r o b l e ma n db a c k g r o u n d t h ep r o b l e mo fe m b e d d i n ggz a p h si n b o o k si ss t u d i e di nt h ed i s s e r t a t i o n ab o o kc o n s i s t so fas 1 ) i n ea l l ( s o t l l en n n l b e ro fp a g e s t h es p i n e o fab o o ki sal i n ea n de a c hp a g ei sa h a l f - p l a n ew i t ht h es p i n ea si t s b o u n d a r y ab o o ke m b e d d i n g o fa l lu n d i l e c t e dg r a p hg = ( k e ) c o n s i s t s o fii v os t e p s t h en i s t s t e pp l a c e s j i pv p t t i c e so fg o l lt h es p i n ei na l l o r d e rs p e c i f i e db yal i n e a ro l d e li n go frt h es e c o n d s t e pa s s i g n se d g e s o ft h eg r a p ht op a g e ss ot h a t e d g e sr e s i d i n go nt h es a m ep a g ec a nb e d r a w l la tt h a tp a g ew i t h o u tc l o s s i n ge a c ho t h e r f h e r ea r et w om e a s u r e so ft h e q u a l i t y ro f ab o o k e m b e d d i n g f o rg t h e f i r s tm e a s u r ei st h ep a g e n i t l l l b e ； o flh e e m b e d d i n g ，w h i c hi st h em i n i m u m n u n l b e ro f p a g e si nw h i c h a g l a p hc a nb ee m b e d d e d t h ep a g e n u m b e 7 o fn c l a s s0 ，g r a p h si st h em i n i m u m l l l 1 1 1 ) e l o fp a g e st h a te v e r ym e m b e r o ft 1 1 e c l a s sc a nb ee m b e d d e d ，a saf u n c t i o no f g r a p hs i z e t h ew i d t ho fap a g ei s t h em a x i m u mn m n b e ro f e d g e st h a ti n t e l s e c ta n yh a l f - l i n ep e r p e n d i c u l a r t ot i l e s p i n ei nt h ep a g e t h es e c o n dl n e a s u r ei st h ep a g e w i d t ho ft h p e m b e d d i n g ，w h i c hi s t h en l a x h l n n l lw i d l ho fa n yp a g e t h e p a g e w i d t t l o fa g r a p hg i st h em i n i m u m p a g e w i d t ho fa n yb o o ke m b e d d i n go fgi n ab o o kh a v i n gam i n i m u m i u l l l b e o f 1 ) a g e s t h ep a g e w i d t ho fac l a s so f g r a p h s ，a saf u n c t i o no fg r a p hs i z e ，i st i l e n f i n i m u mp a g e w i d t ht h a t e v e r y m n m b e ro ft h ec l a s sc a nb ee m b e d d e d t h e b o o ke m b e d d i n g p r o b l e mi s t ot i u dg o o db o o ke m b e d d i n gf o l a g l a p hf a m i l yw i t hr e s p e c tt oo n eo j b o t ht h e s em e a s l l r e 8 t h i sd i s s e r t a t i o nf o c u s e so nt h pf i r s t 1 1 1 e a s u r et oi n v e s t i g a t et h e p r o b l e n l f o rt h ec o n v e n i e n c eo ft h ea l i a l y s i s ，e q u i v a l e n tf o r m u l a t i o n sa r e o f t e n n - t o ( 、h e l p f l d t h eb o o ke m b e d d i n g1 ) t - o b l e mc a nb ea l s ov i e w e di n a v a l i e t yo fw a y s ： p 1 a c et h ev e r t i c e so f “i nal i n ea n da s s i g ni t se d g e st os t a c k si n s u c t law a yt h a tt h es t a c k sc a nb et l s e dt ol a y o u tt h ee d g e s e m b e dt h eg r a p hg s oth a ti t s 、p l t i r e sl i eo nac i r c l ea n di t se d g e s a r ec h o r d so ft h ec i r c l e ，a n dt h e na s s i g nt h ec h o r d st ol a y e r ss ot h a te d g e s ( c h o r d s ) o nt h es a n 2 e1 a y e l d on o tc f o s s i tc a nb ea l s os t a t e dp r e c i s e h a sag r a p h l a b e l i n gp r o b l e ma sl o t - l o w s ( 1 i v e nas i m p l eg r a p hg = ( i ：) w i t hnv e r t i c e s ，ab i j e c t i o nf ：1 ，_ 1 2 ，n ) i sc a l l e da l a b e l i n g o f r 7 w l l p l e f ( v ) l ，2 ，n ) r e p r e s e n t s t h e l a b e l o f v e r t e xv v l e ti l i = 广1 ( i ) h e t h e v e r t e x w i t h l a b e l i t h e n t h el a b e l i n gfc a nb ea l s or e g a r d e da sal i n e a ro r d e r i n g ( u l ，“2 ，“n ) o nt h es p i n eo ft h eb o o k t w oe d g e s1 1 1 ，x y ea r es a i dt ob ec r o s s i n g i f a n do n l yi f f ( u ) ，( 。) ，( 1 7 ) f ( u ) o r ( x ) f ( u ) f ( y ) ，( ”) ；n d e ra l a b e l i n gf ，ap a l t i t i o np = ( e l ，e 2 ，b ) o f e d g es e te ( g ) i sc a l l e dap a g e p a r t i t i o ni f 1 1 0p a i lo f e d g e si na n ys u b s e te i ( 1si p ) c r o s s t h i sp a g ep a r t i t i o nc a nb er e g a m e da sac o l o r i n go fe ( g ) ，w h e r e t h ee d g e si ne ih a v ec o l o r ? a n dn oc r o s s i u ge d g e ss h a r et h es a m ec o l o r t h u s a p a g ep a r t i t i o npr e p l e s e n t sa l la s s i g n m e n to fe d g e so fg t op a g e s o ft h eb o o k w ec a l lt h el n i u i n n u nn 1 n 1 1 ) e ro fs u b s e t so fap a g e p a r t i t i o n _ pt l wp a g e n u m b e ro fgn 1 1 d e l l a b e l i n gf ，a n dd e n o t ei tb yp n ( g ，r ) t h e p a g e n u m b e r o fgi st h e l ld e f i n e da s p n ( g ) = m i np n ( a ，i ) w h e l efi st a k e no v e ra l ll a b e l i n g so fg 一i ss a i dt ob e p a g ee m b e d d a b l e f o ra n yk 尸( g ) p h eb o o ke m b e d d i n g1 ) 1 o h l e mi s i n t e r e s t i n gb e c a u s ei t a r i s e sf r o n l s e v e r ma r e a so fc o m p u t e rs ( i e n c ea n dv l s i t h e o r y 【2 ，3 】 8 t h ef i r s to n ei sa na p p l o a c ht , of a u l l t o l ma n tv l s id e s i g n t h ep r o b 一 1 e n lo ff a u l t t o l e r a n tv l s id e s i g ni s a s s o c i a t e dw i t hs t a c kl a y o u t ，w h i c h i si n t a o d u c e da sf o l l o w s 1 ： ak ；s t a c kl a y o u to fag r a p hgh a st w oa s p e c t s t h ef i r s ta s p e c ti sa l i n e a l ，o r d e ro fl t h es e c o n da s p e c ti s 8 1 1 a s s i g n m e n to f e a c he d g ei ne t oo l l eo fks t a c k si ns u c haw a yt h a i ih es e to fe d g e sa s s i g n e dt oe a c h s t a c ko b e y sal a s t i nf i r s t o u l ( l i f o ) d i s 一 一 n n 5 互文 | j = i ( 6 ) i fi v i f f ) = ，2 ，鼠( 一j = ka n d ”l ，t h e np n ( g ) b c ( g ) 仃j l e ti v ( g ) l = n ，b 。( “) = “a l l ( 1 ，? i1 ( r o o d 七) t h e np n ( g ) s b ，( f ；) + 1 ( 8 ) l e ti p ( g ) l = ，1 3 ，( ( ? ) = “a n d7 ，= ? 砖+ r ( 0sr 南) t h e n 州鲫水聃 ( 【j ) f o rg r a p hg ，w eh a v ep n ( c ) a ( ( g ) ：j p r o p e r t i e so fp a g e m u n h e l r l i ec h a r a c t e r i z a t i o np r o b l e , no fp a g e n u n a b e ro fg r a p h sr e m a i n so p e n t h e p r o p e r t i e sw e c o n s i d e ra l p p a g e m l t u b e ro fo p e r a t i o n so fg r a p h sa n d t h eg r a p hw i t hm a x i m n m p a g e n u m b e l ( i ) g i v e nag r a p hg ，f i l l a 1 1 5 f e f t ；) ， p n f f ? h ) 4 ) p r o o f ： c l e a r l y , i fag l a p h ( ；t i l l h ee m h e d d e di nag i v e nn u m b e ro f p a g e s t h es a n l ei st r u ef o ri t ss u b g l 3 p h s t h e n ，t h ep a g e n u m b e ro fg i s n o l a l e s st h a nt h a to f i t s s u b g l a p h s s o ，( p 4 园r ) p n ( p a q ) p , , ) ：3 i ti ss u 衔c i e n tt os h o wt h a tt h e r ee x i h t ha 3 - p a g ep a r t i t i o nf o rp 4 ( pp t 。 1 h k ep 40 p 4a n d 只昏，毛a h p x 扎1 u 1 ) 】( 、hf o l - e v e no ro d dnr e s p e c t i v e l v 1 6 一e d g e s i np r i n t i n g c y c l e e d g e s i n e l e d g e s i n e 2 e d g e s i n e 3 】3 f i g u r e2 1 0p 4 + p 4 ec y c g n 陋耳& 乜 n n n n 4 2 89 2 0 - - - - e d g e si np r i n t i n gc y c l e 1 1 一e d g e s i n e l e d g e s i n e 2 1 4 e d g e s i n e 3 f i g u r e 2 1 1p 4o p 5 i tf o i l o w st h a tp ( p 4o r ) = 3 口 p r o p o s i t i o n2 9p ( p 。o 只) = 4( m ，扎5 ) p r o o f ：( l o w e rb o u n d ) s e l e c tas u b g r a p hp 50p 5o fp m0p 札，w h i c h i ss h o w na sf o l l o w s f i g u r e 2 1 2p 5o p 5 l e tt ，0 b et h ec e n t e rv e r t e xo ft h i sg r i d b yv i r t u eo ft h e o r e m1 1 t h e g ie m b e d d e di ne a c hp a g eo fgi s o u t e r p