枚舉有向圖回路的分解算法.pdf

1、同濟(jì)大學(xué)士學(xué)位論文枚舉有向圖回路的分解算法姓名：邵文彪申請(qǐng)學(xué)位級(jí)別：士專業(yè)：@指導(dǎo)教師：熊德琰19870407研究生論文稿紙第j J 『頁(yè)A D E C O I P O S I T l 0 NA L LD I R E C T E DA L G O R I T H M F O RC I R C U I T S 0 F AA b s t r 8 t C tE N U M E R A T I N GD I G R A P HI n t h i

2、 8 p a p e r ，t h e p r o b l e i l l l o f d e v e l o p i n g ad e e o r n p o s i t i o na l g o r i t h m f o r e n u 珥e r a t i n g a 1 1 d i r e c t e d c i l “ ( 2 1 1 i t 8 0 f ad i g r a p hi 8 8 t u d i e d ．A

3、n Y d e c o m p 0 8 i t i o n I R e t h o d I t “ e q u i r e 8 t h a t t h e l a r g eg r a p h b e p a r t i t i O l r l e d i n t 0 s u b g r E t p h s ．F o r t h i s p u r p o s e ，Bh e u r i s t i cc l I l l s t e r

4、 E t l g o t i t h mf o r p a r t i t i o n i n g g r a p h s b y e d g e —t e a r i l 3 9 i s P r e 8 e 1 3 t e d f i r s t ．T h i s a l g o r i t h m ．b a 8 e d o r l t h ec o n c e P t 0 f c o n t 0 U r t l a b l e a

5、u ． a i m s a t I n i n i I l l i z i n g t h e1 3 u m b e r o fe d g e s c 0 1 3 1 1 e c t i l 3 9 t h e s u b g r a p h s 。 i t r l d e l l 8 1 1 i t “ e l s t h a t t h e n u r n b e Fo f v e r t i c e 8 0 f e v e r y

6、 8 u b g r a p h s h a l 1 r i o t e x c e e d a g i , d e ni n t e l t “ V a l ． 1 7 h i s a l g o r i t h m c l l l f l a l s 0 b e U S e d i n t h e c a s e s o fd e e 0 1 1 p o s i t i 0 1 1 0 f 1 a r g e - 8 c a l e

7、 1 1 e t w o r k 8 f o r 0 t h e r P u r P 0 8 e I S ．T h e l l 。 a d e c o m p O S i t i O i l a l g o r i t h m f o r e l r l U r n e r a t i n g 8 1 ld i c i r ' C U i t s 0 f ad i g r a p hb a 8 e do n t h e h y

8、b r 主d a p P r o a c h i sp r o p o s e d 。b y w h i c ha8 e a r c h a l g o r i t h i , i 8 U f l e d f o rf i n d i r l g a 1 1c i r c u i t 8 i 1 1 e a c h 8 u b g r a p l aw h i l e a 1 1 1 8 ．t r i x a l g o r i t h

9、 m f o I t “f i n d i n ga l lc i l t “ C U i t g t o r n b Y c u t e d g e s ． F o r as p e c i a l c a 8 e ．w h e r e0 1 1 1 Y t w o 8 u b g r a p h - q e x i 8 t ． ac o r l p l e i o l l e t l t a r y c o r , b i n a

10、t i 0 1 1a l g o r i t h - , f o rf i r l d i n g a l l d i c i r c a i t 8 i s a 1 8 0 P r e s e l l t e d ．．T h e g r a p h p a r t i t i 0 1 1 a l g o r i t h m ， t h e c i r c u i t 8 e a r t ha ／g o r i t h m 。a l l