組合矩陣論若干問題研究.pdf

1、中國科學技術(shù)大學碩士學位論文組合矩陣論若干問題研究姓名：楊凱申請學位級別：碩士專業(yè)：應(yīng)用數(shù)學指導(dǎo)教師：李炯生2002.5.1A b s t r a c tI nt h eC h a p t e r 1 o ft h i sp a p e r ，t h ec o n c e p to f c o m p a c t g r a p h si sg e n e r a l —i z e dt od i g r a p h s ．L e tD

2、 b ead i g r a p hw i t ha d j a c e n c ym a t r i xA a n dl e t P ( A )b et h es e to f a l lp e r m u t a t i o n m a t r i c e sw h i c hc o m m u t e w i t hA ．M o r e o v e r ，t h es e t o fa 1 1d o u b l ys t o c

3、h a s t i c m a t r i c e sw h i c hc o m m u t ew i t hA i s d e n o t e db ys ∽) ．W e c a l lD c o m p a c t i fe v e r ym a t r i xi nS ( A ) i s a c o n v e xs u m o fm a t r i c e sf r o mP ( A ) ．W ef i r s te x t

4、e n dt h en o t i o no fe q u i t a b l ep a r t i t i o n so ng r a p h st od i g r a p h s ，a n dc h a r a c t e r i z ed i g r a p h sw i t hS ( A ) = { n ．W e a l s op r o v et h a t ，i ft h ef r e q u e n c yo f e v

5、 e r yp a i ro f i n d e g r e ea n d o u t d e g r e eo fv e r t e xi nad i g r a p h i sn o te x c e e d2 ，t h e nD i sc o m p a c t ，a n ds h o w t h a tr e g u l a rc o m p a c t d i g r a p h sa r ev e r t e x - t r

6、 a n s i t i v e ．F i n a l l y ，w ed i s c u s sc o m p a c t n e s s o f t o u r n a m e n t s ，p r o v et h a tat o u r n a m e n ti s c o m p a c ti fa n do n l yi fi t se a c hs t r o n gc o n n e c t e dc o m p o n

7、 e n ti s c o m p a c t ，a n dd e t e r m i n ec o m p a c tr e g u l a rt o u r n a m e n t s w i t hp r i m en u m b e ro f v e r t i c e s ．A c o m p l e xm a t r i xA i s s a i dt ob eam a t r i xr e a l i z a t i o

8、no ft h ed i g r a p hDi fD i s t h ea s s o c i a t e dd i g r a p ho fA ，a n dA i s s a i dt oh a v et h ep r o p e r t yB i fe v e r ys i n g u l a rv a l u eo fA i sc o n t a i n e di nt h eu n i o no fB r u a l d it

9、 y p ei n t e r v a l s ．A d i g r a p hD i ss a i dt ob eaf o r c i b l yB —d i g r a p hi fe v e r ym a t r i xr e a l i z a t i o no fD h a st h ep r o p e r t yB ．I nt h eC h a p t e r2 ，w eg i v ea s u f f i c i e n

10、 tc o n d i t i o nf o ram a t r i xt oh a v et h ep r o p e r t yB a n dc h a r a c t e r i z et h ef o r c i b l yB —d i g r a p h s ．A s e q u e n c e 7 r o fn o n n e g a t i v e i n t e g e r s i s s a i d t o b eg

11、r a p h i ci f t h e r e i sag r a p hw h o s ed e g r e es e q u e n c ei s 7 r ．E s p e c i a l l y , i f s u c hg r a p hi s a no r i e n t e dg r a p h ，t h es e q u e n c e i ss a i d t o b e o r i e n t e dg r a p

12、h i c ．I nt h e C h a p t e r 3 ，w ep r o v i d eas u f f i c i e n t a n dn e c e s s a r yc o n d i t i o nt oj u d g ew h e t h e ras e q u e n c ei s o r i e n t e dg r a p h i c ．F u r t h e r m o r e ，i nt h ep r o

13、 o f o f t h i sr e s u l t ，a na l g o r i t h m i s p r o v i d e dt oc o n s t r u c tt h eo r i e n t e dg r a p hw i t ht h eg i v e nd e g r e es e q u e n c ew h e nac e r t a i np a i ro fa d j a c e n c ym a t r

14、 i c e sh a sb e e nf o u n d ．K e y w o r d s ：d i g r a p h ，c o m p a c td i g r a p h ，c o m p a c tt o u r n a m e n t ，e q u i t a b l ep a r t i t i o n ，m a t r i xr e a l i z a t i o n ，s i n g u l a rv a l u e