（应用数学专业论文）图的线性荫度和线性k荫度.pdf

图的线性荫度和线性承荫度 摘要 图的染色理论一直是图论界的一个热门话题一个图g 的后边染色是从e ( g ) 到 l ，2 ，后，的一个映射，对于图g 一个给定的鬼边染色，最表示g 中染i 色的边的集 合，而g 忍】表示厩在g 中的边导出子图若毛( 1 i 七) 都是匹配，则称，为一个正 常后边染色使得图g 有正常七边染色的最小数后称为图g 的边色数，记为x 7 ( g ) 在 个b 边染色中，若g 暇】( 1 i 七) 的每个连通分支都是路，则称，为一个缸线性染色 使得图g 有七线性染色的最小的数七称为图g 的线性荫度，记为2 口( g ) 一个图g 的珏染色是从y ( g ) 到 l ，2 ，七) 的一个映射厂对于图g 一个给定 的七一染色，k 表示g 中染i 色的顶点的集合，而g 【k l 表示k 在g 中的点导出子图若 ( 1 七) 都是独立集，则称，为一个正常染色使得图g 有正常b 染色的最小数 七称为图g 的点色数，记为x ( g ) 在一个免染色中，若g m 】( 1 t ) 的每个连通分支 都是路，则称，为一个路惫染色使得图g 有路缸染色的最小的数七称为图g 的点线 性荫度，记为讲口( g ) 一个图g 的线性七一森林为图g 的一个子图，其中，它的每个连通分支为长度至多为 七的路线性b 荫度z 口 ( g ) 即为分解图g 的边集e ( g ) 所需要的线性七森林的最小个 数事实上，线性缸荫度为边着色的一种自然的推广显然，线性1 森林为一个匹配，所 以，f 口l ( g ) 即为图g 的边色数x 7 ( q 当线性b 森林中的路的长度不受限制时( 忌= 。o ) ，记 z 口o o ( g ) 为f 口( g ) ，称为图g 的线性荫度 给定一个礼元集合= o ，1 ，n 一1 ) ，s 为的一个子集，若对于任意两个不同 元素z ，可s 满足2 z 一3 ，l n 一2 ，则称s 为一个2 一稳定子集一个图为s c h r i j v e r 图 s g ( n ，七) ，如果它的顶点集是由n 元集合h 】= o ，l ，n 一1 的所有七元2 稳定子集构 成的，并且两个顶点相邻当且仅当它们所对应的两个集合不交 一个完全佗部图称为均衡的，如果它的顶点集的每个划分都有相同的顶点个数我们 记j 厶( 。) 为一个均衡完全n 部图，其中顶点集的每个划分中有m 个顶点 假设g l ，g 2 ，g m 为m 个图，则图g = g l 口g 2 口口g m 称为图g l ，岛，g 。的笛 卡尔积图，其中，g 的顶点集为n 銎ly ( g ) ，并且两个顶点( u 1 ，心2 ，t m ) a n d ( 1 ，睨，) 相邻当且仅当存在一个歹满足u ，u ，e ( g ，) ，并且对于其他的 j 有u l = 仇当 g = g ( t = 1 ，2 ，m ) ，我们记g m = g l 口g 2 口口g m 一些完全图，2 ，珞。的 笛卡尔积图，口j 乙。口口j 厶。称为一个h 锄m i n g 图 记j 0 ( m 1 ，叼，s g ( n ，七) 分别为均衡完全n 部图，h a m m i n g 图口口口蜀；和 s 出r i j v e r 图记( g ) 为图g 的最大度 本论文主要分以下四部分： 在第一章中，我们引进了一些定义和符号，并且介绍了线性荫度和线性七一荫度的研究 现状 在第二章中，我们研究了s c h r i j 、，e r 图s g ( 2 七+ 2 ，七) 的线性荫度和点线性荫度得到了 s g ( 2 危+ 2 ，七) 的结构特征，并得到了下面两个结论 结龃吲螂俐，2 蕊：冀 结论2 t ，z 口( s g ( 2 七十2 ，七) ) = 2 在第三章中，我们研究了( m ) 和研的线性七- 荫度，在这里，我们取七= n 一1 得 到了如下两个非常好结论 结论3 对于均衡完全竹部图j 乙( m ) ， f 。州( 珞( 。) ) = f 警1 结论4 对于h 锄m i n g 图研， z ( 砰) = 警1 在第四章中，我们研究了c 翟的线性2 荫度，j r 赢加，甄。+ 1 ，锄，j r 赢，饥+ 1 的线性4 - 荫 度得到了如下几个结论 结论5 对于二部完全图和m 个n 一圈的笛卡尔积图，我们得到了： ( a ) f 口2 ( c ? ) = f 挚1 ，其中礼毒o ( m o d3 ) ， ( b ) z d 4 ( 甄。，轨) = 3 n ， ( c ) z 口4 ( j r 矗+ 1 。轨) = z 口4 ( j r 赢，锄+ 1 ) = 3 竹+ 1 ，其中n 为奇数 关键词线性森林，线性荫度，线性忌森林，线性肛荫度，均衡完全多部图，笛卡尔 积图，h a 玎1 m i n g 图，s c h r i j v e r 图 t h el i n e a u ra r b o r i c i t ya i l dl i n e a r 后一a r b o r i c i t yo fg r 印h s a b s t r a c t t h ec o l o r i n gi st h ef o c u so f r e s e a r c hi nt h e 髓a p ht h e o r y a 七一e d g ec o l o r i n go fa 野a p hgi s am a p p i n g ，厅o me ( g ) t o 1 ，2 ，知，w i t hr e s p e c tt oa 酉唧舡e d g ec o l o r i n g ，厩i sd e n o t e d b yt h es e to fa 1 1e d g 鹤o fgc o l o r e dw i t hi ，a n dg 【历】i sd e n o t e db yt h es u b g r a p hi n d u c e db y 厩 i ng i fei sam a t c h i n gf i e v e r y1 i5 七，t h e n ，i sc a l l l e dap r o p e r 七一e d g ec o l o r i n g t h e e 幻e 如7 _ d m 口t l cn t m 6 e rx ( g ) o fa 黟印hg i st h em i n i m u mn u 1 b e r 七f i mw h i c hgh 铀ap r o p e r 缸e d g ec o l o r i n g a l lc o m p o n e n t 8o fg 【邑】a r ep a t l l s ，t h e n ，i sc a l l e da 七一l i n e a l rc o l o r i n g t h e l i n e a r 盯b o r i c i t yo fag r a p hg ，d e n o t e db y2 口( g ) ，i 8t h em i n i m 衄n u i n b e r 七f o rw h i c hgh a sa 后一l i n e a rc o l o r i n g a 肛c o l o r i n go fa 蓼a p hgi sam a p p i n g ，f 如my ( g ) t o 1 ，2 ，后w i t hr e s p e c tt oa 西v e n 七一c o l 矾n g ，ki sd e n o t e db yt h es e to f a nv e r t i o 陷0 f gc o l o r e dw i t hi ，a n dg 陬d e n o t e d b yt h es u b g l 印hi n d u c e db y 磁i ng i f i sa ni n d e p e n d e n ts e tf o re v e r y1 t ，t h e n ，i s c a l l e dap r o p e r 七一c 0 i o r i n g t h ec r d 仇n t i cm m 6 e rx 7 ( g ) 0 fag r 印hgi st h em i n i m u mn u h l b e r 七o rw h i c hgh 弱ap r 叩e r 七一c o l o r i n g a l lc o m p o n e n t so fg 【k 】a r ep a t l l s ，t h e n ，i sc a l l e ( 1a p a t h 缸c o l o r i n g t h ev e r t e xl i n e a ra r b o r i c i t yo fag r 印hg ，d e n o t e db y 优o ( g ) ，i st h e l i n i m u m n u m b e r 后f ；d rw h i c hgh 鹊ap a t hb c o l o r i n g al i n e a r 七一f b r e 8 t0 fa 寥a p hgi sas u b 擎a p ho fgw h o 鼬c o m p o n e n t sa r ep a t h sw i t hl e n 昏h s a tm o s t 后t h el i n e a r 七a r b o r i c i t y0 fg ，d e n o t e db yz 口七( g ) ，i st h em i n i m u mi m m b e ro fl i n e a r 缸d r e s t sn e e d e dt 0p 础i t i o nt h ee d g e8 e tf ( g ) o fg i i l t ，i tban a t u r a lg e n e r a l i z a t i o n o fe d g ec o l o r i n g c l e a r l y ，al i n e a r1 一f o d e s ti si n d u c e db yam a t c h i n g ，a n dz 口1 ( g ) i st h ee d g e c k o m a t i cn u l b e r ，o rc h r o m a t i ci n d e x ，x ( g ) o fag r 印h i nc 嬲et h a tt h el e n g t l l so fp a t h si n l i n e a r 詹一a r b o r i c i t y 啪n o tr 豁t r i c t e d ，w et h e nh a v et h el i n e a ra r b o r i c i t yo fg ，d e n o t e df 口( g ) b yz 口( g ) ac o m p l e t em p 叭i t e 擎印hi so n et h a ti ss i m p l ea n di nw h i c he a c hv e r t e ) ci sj o i n e dt o e v e 珂、，e r t e ) ct h a ti sn o ti nt h es a m es u b s e t ，w h i c hi sd e n o t e db yj 厶l ，f 1 2 ，i f jki = a = l ，2 ，m ) 、h e nn 1 = n 2 = = n m = n ，w e d e n o t ej 厶1 ，n 2 ，n 。b y k n ( n ) ，w h i c hi sc m l e d b a l a n c e dc o m p l e t em p a r t i t eg r 印h as u b s e tso fh 1 = o ，1 ，n 1 ) i 8s a i dt ob e2 一s t a b l ei f2 lz 一可l n 一2f b ra n yt w o d i s t i n c te k m e n t sza n d 可，i e ，sd o 鹤n o tc o n t a i nt 、mc o n s e c u t i v en u 瑚i b e r si nt h ec y c l i co r d e r i n g o f t h es c h r j j v e rg r 印hs g ( n ，后) i sd m n e d a sf o l l o w s i t sv e r t i o e sa l r et h o s e 忌一e l e n l e n t8 u b 8 e t s o f t h e 鼬t = o ，l ，n 一1 ) t h a td on o tc o n t 撕nc y c l i c a l l yc o n s e c u t i 、，ee k m e n t si ，i + l0 r n 一1 ，0 t w os u c hv e r t i c e sa r ea d j a u c e n ti ft h e yr e p r e s e n td i s j o i n t 后一s u b 8 e t s t h ec 疵e s i a np r o d u c to fmg r 8 p h sg l ，g 2 ，g m 毽t h eg r a p hg = g l 口g 2 口口g m w h o s ev e r t e xs e ti sn 譬ly ( 戗) a n dt w ov e r t i c e s ( u 1 ，“2 ，t m ) a n d ( 口l ，眈，) a r ea d - j a c e n ti fa n do n l yi ft 上j e ( g j ) f o rs o m e 歹a n du = f o ra l lo t h e rt 歹w h e ng i = g f o ra l ll ，w e1 1 s eg ”t od e n o t eg l 口g 2 口口g m ah a m m i n gg r a p hi 8t h ec a r t 鹊i a np r o d u c t l 口2 口口。o f c o m p l e t e 留a p h s 1 ，2 ，。 l e tj 乙( m ) ，研，s g ( n ，后) b et h e b a l a j l c e dc o m p l e t en p a r t i t eg r a p h ，h 锄m i n g 髓印h 口j 厶口口a n ds c h r i j v e r 黟印h d e n o t et h em a x i m u md e 印e eo fg r a p hgb y ( g ) t h i sp 印e ri sd i v i d e di n t of o u rc h a p t e 瑙： i nc ：h 印t e r1 ，s o m ed e f 诚t i o 璐，n o t a t i o 璐a n dt h ed e v e l o p m e n to f l i n e a ra r b o r i c i t ya n dl i n e a u r b a l r b o r i c i t ya u r ei n t r o d u c e d i nc ：h a p t e r2 ，t h el i n e a ra r b o r i c i t yo fs c h r i j v e rf 印hs g ( 2 七十2 ，后) i ss t u d i e d t h ec o 皿哥 u r a t i o no fs g ( 2 后+ 2 ，后) i so b t a i n e d f h r t h e r m o r e ，t w or e s u l t sa r eo b t a i n e d c - 腻儿以娜俐，2 麓芝套墓 c o n c l u s i o n2 们口( s g ( 2 后+ 2 ，后) ) = 2 i nc h a p t e r3 ，t h el i n e a r 七一a r b o r i c i t yo fj 厶( m ) a n dk ? i ss t u d i e d lw bt a k e 七= n 一1 ，t h e f d l o w i n gt 、j l ，on i c er e s u l t s 砌ee s t a b l i 8 h e d c o n c l l l s i o n3 f o rb a l a i l c e dc o m p l e t en - p a r t i t e 舒印hj 厶( m ) ， 一1 ( ( 。) ) = 警1 c o n c l u s i o n4 e o rh a m m i n g 口印hk ， f d 州( 研) = f 竿1 i nc h a p t e r4 ，w es t u d yt h el i n e a r2 一a r b o r i c i 锣o fc 翟，a n dt h el i n e a r4 - a r b o r i c i 锣o fk 觎，缸， 玩叶1 ，瓤，4 ，l + 1 t h ef o l l o w i n gr e s u l t sa r eo b t a i n e d c o n c l u s i o n5 f o rc o m p l e t eb i p a r t i t eg r a p ha n dc a r t e s i a np r o d u c tc ? ，i ti so b t a i n e dt h a t ( a ) z 口2 ( c 2 ) = f 等1 ，w h e r e 礼三o ( m d d3 ) ( b ) f 口4 ( 甄n ，饥) = 3 n ( c ) z 口4 ( k _ 6 n + l ，4 n ) = f n 4 ( k 6 n 。4 n + 1 ) = 3 n + 1 ，w h e r en i so d d k e yw o r d sl i n e 盯f b r e 8 t ，l i n e a r 盯b o r i c i t y l i n e a r 如f o r e s t ，l i n e a r 珏a r b o r i c i 坝b a l a n c e d c o m p l e t e 伦p a r t i t eg r 印h ，c 甜t e s i a l lp r o d u c tg r 印h ，h a m m i n g 窜印h ，s c h r i j v e rf a p h 原创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得苤鲞竖塾盘鲎或其它教育机构 的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 做作者签名篱鲮吼勿卢年 研究生学位论文使用授权说明 ( 必须装订在提交学校图书馆的印刷本) 石圹日 本人完全了解天津师范大学关于收集、保存、使用研究生学位论文的规定， 按照学校要求向图书馆提交学位论文的印刷本和电子版本； 图书馆有权保存学位论文的印刷本和电子版，并通过校园网向本校读者 提供全文与阅览服务。 图书馆可以采用数字化或其它手段保存论文； 因某种特殊原因需要延迟发布学位论文，按学位论文保密规定处理，保 密论文在解密后遵守此规定。 论积磊矿哪日期易咖年月日 c h a p t e r1 i n t r o d u c t i o n 1 1b a s i cd e f l n i t i o n sa n dn o t a t i o n s i nt h i 8s e c t i o n ，w ew i l ld e f m es o m eb 嬲i ct e r m i n o l o g 洒a n dn o t a t i o n 8w h i c ha 舱i l s e di n 鲈a p ht h e o r y w | el e tisl b et h ec 盯d i n 缸i t yo ft h es e ts f i o rar e a ln u i i l b e rz ，p i st h el e 鹪t i n t e g e rn o tl e 鹤t h a nz ，【z ji 8t h em o s ti n t e g e rn o tm o r et h a nz ag r a p hgi sa no r d e r e dt r i p l e ( y ( g ) ，e ( g ) ，砂g ) c o n s i s t i n go fn o n e m p t ys e ty ( g ) o f v e r t i 嘲，as e te ( g ) ，d 两o i n t6 m my ( g ) ，o fe d g e 8 ，a n da ni n c i d e n c ef u n c t i o n 妒gt h a ta s s o c i a t e s w i t he a c he d g eo fga nu no r d e r e dp a i ro f ( n o tn e o e s s 都i l yd i s t i n c t ) v e r t i c e so fg i fei sa ne d g e a n d 牡a n dt ，a r ev e r t i c e ss u c ht h a t 矽g ( e ) = u v ，t h e nei ss a i dt o j o i nt 上a n d ；t h ev e r t i c 髑t a n d t ，a r ec 甜l e dt h ee n d so fe t h ee n d so f 缸e d g ea r es a j dt ob ei n c i d e n tw i t ht h ee d g e ，a n dv i c e r s a t w ov e r t i c e sw h i c ha r ei n c i d e i l tw i t ha ne d g ea r ea d j a c e n t ，a sa r et w oe d g e 8w h ic ：ba _ r e i n c i d e n tw i t hac o m m o nv e r t e x a ne d g ew i t hi d e n t i c a le n d 8i sc a l l e dal o o p ，a n da i le d 萨w i t h d i s t i n c te n d si 8c a l l e dal i n k a 伊a p hi ss i m p l ei fi th a sn o p sa n dn o 协mo fi t 8l i n k sj o i nt h es a m ep a ko fv e r t i c e s a 留印hi s 丘n i t ei f b o t hi t sv e r t e x ta n de d g e ta r ef m i t e i nt h i st h e s i s ，、es t u d yo i l l y 五m t e a n ds i m p l eg r a p h s ag r a p h 日i sas u b g r a p ho fg ( w r i t t e n 日g ) i fy ( 日) y ( g ) ，e ( 日) e ( g ) ，a n d 妒日i s t h er 鹤t r i c t i o no f 妒gt oe ( 日) w h e n 日gb u t 日g ，w ew r i t e 日cga n dc a l l 日ap r o p e r s u b f a p h as p a n n i n gs u b 伊a p ho fgi sas u b g r a p h 日w i t hy ( 日) = y ( g ) s u p p o s et h a ty i san o n e m p t ys u b s e to f y t h es u b 留a p ho f gw h o v e r t e xs e ti sy 7a n d w h o e d g es e ti st h es e to ft h o s ee d g 鹤o fgt h a th a v eb o t he n d si ny 7i sc a l l e dt h es u b 擎a p h o fgi n d u c e db yy 7 锄dd e n o t e db yg ，】w es a yt h a tg f y ，】i sa ni n d u c e ds u b 留a p ho fg t h ed e g r e ed g ( t ，) o f av e r t e xt ，i ngi st h en u n l b e ro f e d g e so f gi n c i d e n tw i t h ”，e a c hl o o p c o u n t i n g 粥协r oe i l g e s w ed e n o t eb y ( g ) t h em a x i m u md e 留e eo fv e r t i o 骼o fg ag r a p hgi s 如r e g u l a ri fd ( t ，) = 七f b ra | l y a 、 厂a 肽i ngi saf l n i t en o n n u l ls e q u e n c ew = u o e l 口1 e 2 也e 知坝，w h o s et e r m s 羽屯a l l t e r n a t e l yv e r t i c e s 舭l de d g e s ，s uc ：ht h a t ，f b r1 i 七，t h ee n d so f b ia r e 魄一la n d 仇t h ei n t e g e r 七 i st h el e n g t ho f t h ev e r r t e xt ，oa n d a r ec 甜l e dt h eo r i g i i la n dt e r m i n u so f w bs a yt h a t i sa ( 珈，) - w a l k i f t h ev e n i c e s 秽o ，口1 ，讥a r ed j s t i n c t ，i sc a u e dap a t h w bd e n o t e b yr t h ep a t hw i t hl e n 昏h 七，w h i c hi ss a i d 詹一p 口玩ap a t hi sc l o s e di fi th a sp 0 8 i t i v ek n 酵h a n di t so r i 西na n dt e r m i n u sa r et h es 锄e ac 1 0 8 e dp a t hi sc 献l e dac y c k ac y c l eo fl e n 或h 七 i sc a l ma 七一c y c l e ，w h i c hi sd e n o t e db y 仇ah 砌i l t o nc ) r c l eo fgi sac y c l et h a tc o n t 撕璐a l l v e r t i o 鹧o fg t h eg 砒ho fag r a p hgi st h el e n g t ho ft h es h o r t e s tc y c ki ng 。 t 、 r ov e r t 玉e e st a n duo fga r es a i dt ob ec o n n e c t e di ft h e r ei sa ( t ，t ，) p a t hi ng c o n n e c t i o n i sa ne q u i v 对e n c er e l a t i o no nt h ev e r t e ) ( ty t h u st h e r ei sap a r t i t i o no fyi n t on o n e m p t y 1 s u b s e t s ，耽，s u c ht h a tt w ov e r t i c 豁t a n dt ，a r ec o n n e c t e di fa n do n l yi fb o t ht a n d t ，b e l o n gt ot h es a m e t t h es u b g r a p h sg 【h 】，g 【k 】，g 【圪】a r ec 址l e dt h ec o m p o n e n t s o fg i fgh a se ) 眦t l yo n ec o m p o n e n t ，gi sc o n n e c t e d ；o t h e r w i s egi sd i s c o n n e c t e d w bd e n o t e t h en u r n b e ro fc o m p o n e n t so fgb yu ( g ) at r e ei sa n n e c t e d 锄c y c l i c 铲a p h af b r e s ti sa n 卸c y c l i c 斟印hw h o s ec o m p o n e d 上sa r e t r e 鹄i np a r t i c u l a r ，a na c y c l i c 黟a p hw h o s ec o m p o n e n t sa r ep a t h si sc a l l e dal i n e a u rf o r e s t a l i n e a rk f o r e s ti st h eg r 印hw h o s ec o m p o n e n t sa r ep a t h sw i t hl e n 昏ha tm o s t 詹 f o rs u b s e t ssa n ds o fy ，w ed e n o t eb y 慨s ，】t h es e to fe d g 鹤w i t ho n ee n di nsa n dt h e o t h e ri ns 7 a ne d g ec u to fgi sas u b s e to fe ( g ) o ft h ef o r m 【s ，翻，w h e r es 遗a n o n e m p 锣 p r o p e rs u b s e to fya n ds = y w h i c hi 8o b t a i n e db yd e l e t i n ga l le l e m e n t so fs 行o my as u b s e tmo f ei sc 址l e dam a t c h i n gi i lgi fi t se l e m e n t sa r el i n l 【sa n dn ot w oa r ea d j a u c e n t i ng ap e r f ；e c tm a t c h i n go fgi sam a t c h i n gt h a tc o n t a i n se v e r yv e r t e xo fg as u b s e tso fy i sc a l l e da ni n i i 印e n d e n ts e to fgi fn ot w dv e r t i o 豁o fsa r ea d j a c e n ti ng ap r o p e r 舡e d g ec o l o r i n go f gi sam a p p i n g 毋：e ( g ) h 1 ，2 ，耐s u c ht h a t ( e ) ( ，) f o ra n ye n ，西i n f a c t ，l e t ( e l ，岛，凤) b e a p a r t i t i o no fe ( g ) ，w h e r ee id e n o t 镐t h es u b s e t o fe ( g ) 鹪s 遮n e dc o l o ri t h e nap r o p e r 蠡- e d g ec o l o r i n go fgi sap a r t i t i o n ( e l ，玩，最) o f e ( g ) i nw h i c he a c hs u b s e t 五i sam a t c h i n g t h ee d g ec h r o m a t i cn u m b e rx ( g ) o fgi st h e m i i l i m u m 忌f ；d rw h i c hgh 船ap r o p e r 舡e d g ec o l o r i n g ap r o p e r 七v e r t e x 砌嘶n go fgi sam 印p i n g ：y ( g ) h 1 ，2 ，耐s u c ht h a t ( t ) 西( t ，) f o ra n y 伽e ( g ) i n t ，l e t ( ，屹，攻) b eap a r t i t i o no fy ( g ) ，w h e r e kd e n o t 髓t h es u b s e to fy ( g ) 嬲s i 鹊e dc o l o ri t h e nap r o p e r 七一v e r t e 。cc o l o r i n go fgi sa p a r t i t i o n ( ，k ，k ) o fy ( g ) i nw h i c he a c hs u b s e tk i sa ni n d 印e n d e n ts e t t h ev e r t 饮 c h r o m a t i c 眦m b e rx ( g ) o fgi st h em i n i m u m 七d rw h i c hgh 弱ap r o p e r 七一v e r t e ) 【c o l o r i n g t h ea r b o r i c i t yo fg ，d e n o t e db yo ( g ) ，i st h em i n i m u mn u l b e r o ff o r e s t sn e e d e dt op a r t i t i o n t h ee d g es e te ( g ) o fg t h eu n e a r 七一a r b o r i c i t yo fg ，d e n o t e db yf o 屉( g ) ，i st h em i n i m u m n u m b e ro fl 妇盯珏f o r e s t sn e e d e dt op a n i t i o nt h ee d g es e te ( g ) o fg i nk t ，i ti san a t u r a l g e n e r a l i z a t i o no fe 幻ec d f d r 饥9 c l e a r l y al i n e a r1 - f o r e s t 培i n d u c e db yam a t c h i n g ，a n d2 口l ( g ) i 8t h ee 幻ec 打d m n i cn u m 6 盯，0 r 眈r d m o 统c n d e z ，x ( g ) o fa 留印h i nc a s et h a tt h el e n 垂h s o fp a t h si nl i n e 敬惫一f 缸e s t sa r en o tr t r i c t e d ，w et h e nh a v et h el i n e a ra r b o r i c i t yo fg ，d e n o t e d l 口o 。( g ) b y 口( g ) t h ev e r t e ) 【a r b o r i c 姆o fg ，d e n o t e db y 口( g ) ，i st h em i n i m u mn u m b e r 后f ；d rw h i c ht h e r e i sap 扒i t i o n ( ，k ，k ) o fy ( g ) i nw h i c he a c hg f 磁】i i l d u c 鹤af o r 鹤t t h ev e r t e xl i n e a r a r b o r i c i 锣o fg ，d e n o t e db yu z 口七( g ) ，i st h em i n i m u mn u 如l b e r 七五d rw h i c ht h e r ei sap a r t i t i o n ( h ，k ) o fy ( g ) i nw h i c he a c hg f k 】i n d u c e sal i n e a r 五0 r 鹤t ac o m p l e t eg r a p hi sas 抽1 p l eg r a p hi nw h i c he a c hp a i ro fd i s t i n c t 、r e r t i c 豁i sj o i n e db y a ne d g e w bd e n o t eac o m p l e t e 擎a p ho nnv e r t i e e sb yk n ab i p a r t i t eg r a p hi so n ew h o s e v e r t e xs e tc a nb ep 础i t i o n e di n t ot w os u b s e t sxa n dy ，s ot h a 土e a c he d g eh a 8o n ee n di nx a n dt h eo t h e re n di ny ；s u c hap a r t i t i o n ( x ，y ) i sc a l l l e dab i p a r t i t i o no ft h e 铲印h ac o m p k t e 2 b i p a n i t eg r 印hi sa8 i m p l eb i p a i r t i t e 口印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 xo fx i sj o i n e dt oe a c hv e r t e xo fy ；i flxl = m ，lyi = n ，8 u c hag r 印hi sd e n o t e db yk m ，n ，w h i c h i sc a l l e db a l a n c e dc o m p l e t eb i p a r t i t eg r a p hi fr n = n am p a r t i t e 矿a p hi so n ew h o s ev e r t e x 鼬tc a nb ep a r t i t i o n e di n t o 詹$ u b s e t s ，s ot h a tn oe d g eh a sb o t he n d si na n yo n e s u b s e t a = 1 ，2 ，m ) ac o m p l e t em p a r t i t eg r a p hi 8o n et h a ti ss i m p l ea n di nw l l i c he a u c h v e r t e xi sj o i n e dt oe 、，e 】眵v e r t e xt h a ti sn o ti nt h es a m es u b s e t ，w h i c hi 8d e n o t e db yk n l ，他”，n m i flk i = n ( 1 = 1 ，2 ， i ) w h e n n l = = n 2 = = n m = n ，w ed e n o t ej 厶1 ，n 2 ，n 。b yj m ( n ) ， w h i c hi sc a l l e db a l a n c e dc o m p l e t em p a r t i t eg r a p h 1 2t h ed e v e l o p m e n to fl i n e a ra r b o r i c i t y 锄dl i n e a rk - a r b o r i c i t y a tf i 璐t ，w er e c a ut h ec o n c 印to fa r b o r i c i t y t h e 甜b o r i c i t yo fg ，d e n o t e db y 口( g ) ，i s