關于圖的邊分解的一些結果.pdf

1、南京師范大學碩士學位論文關于圖的邊分解的一些結果姓名：黃國林申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：許寶剛20100507A b s t r a c tA b s t r a c tA n e d g e ·p a r t i t i o n o f a g r a p h G i s a d e c o m p o s i t i o n o f G i n t o s u b —g r a p h s G 1 ，G

2、 2 ，?，G m ，s u c h t h a t E ( a ) = E ( G 1 ) U E ( G 2 ) ?U E ( G m ) a n dE ( G i ) n E ( G j ) = 彩f o r i ≠歹．W e g i v et h ef o l l o w i n gr e s u l t sa b o u t p l a n a r g r a p h s ：( 1 ) n e e d g e so f e v

3、 e r yp l a n a rg r a p h w i t hA ( C ) ≤3 a n dg ( C ) ≥1 1c a n b ed e c o m p o s e d i n t oa l i n e a rf o r e s ta n d a m a t c h i n g ．T h i sr e s u l ti m p r o v e st h er e s u l to ft h ep a p e r 【2 6 ]

4、 ．( 2 ) B yd a ( G ) ，w e d e n o t e t h em i n i m a l d i s t a n c eb e t w e e n t r i a n g l e si nG ．W e s h o wt h a tt h ee d g e s o fe v e r yp l a n a rg r a p hG c a n b e d e c o m p o s e di n t o a f o r

5、 e s t a n d a l i n e a rf o r e s ti f o l l eo ft h ef o l l o w i n g h o l d s ：①d z x ( G ) ≥1a n d G h a sn o c y c l e so f l e n g t hf r o m 4 t o1 2 ；②d z x ( G ) ≥2 a n dG h a s n oc y c l e s o fl e n g t hf

6、 r o m 4 t O9 ：③d ／x ( G ) ≥4 a n dG h a s n o c y c l e so f l e n g t hf r o m4 t o8 ：( 3 ) T h ee d g e so f e v e r yp l a n a rg r a p hG w i t hg ( G ) ≥5 c a n b ed e c o m p o s e di n t ot w o f o r e s t sn ，死a

7、 n d a l i n e a rf o r e s ts u c h t h a tA ( T x ) ≤f 竽1 ，△( 正) ≤I [ a ( _ ／2 9 A 1 I ．( 4 ) T h ee d g e s o fe v e r yp l a n a rg r a p hG w i t hg ( a ) ≥6 c a n b ed e c o m p o s e di n t ot w o f o r e s t s 矸，

8、乃a n da m a t c h i n g s u c ht h a t △( 乃) ≤『學] ，△( 乃) ≤f 學] ．I na d d i t i o n ，f o r 2 一c o n n e c t e dg r a p h G w i t ha ( c ) ≤3 ，w e s h o wt h a tG h a s a ne d g e ‘p a r t i t i o ni n t oa m a t c h i n g