（计算数学专业论文）kneser图的若干性质及其自同构群.pdf

摘要 k n e s e r 图的若干性质及其自同构群 作者简介：文建伟，男，1 9 7 6 年9 月生，师从成都理工大学魏贵民教授， 2 0 0 8 年6 月毕业于成都理工大学计算数学专业，获得理学硕士学位。 摘要 设q 是一个给定的集合，其势为n 。定义在这个集合上的l o e s e r 图，( 门，七) 的顶点集v 是q 的所有k 元子集，若两个k 元子集不相交则它们在图中关联( 其 中：n ，k 是给定的j 下整数，并且” 2 七，七 1 ) 。k n e s e r 图是十分重要的一类图， 这是因为许多关于集合的计数以及计算问题可以转换为此类图中的问题加以探 讨。关于l o e s e r 图的研究在国外比较多见，而国内在这一方面的研究相对较少。 关于k n e s e r 图最著名的结果莫过于被l o v a s z l 证明的k n e s e r 猜想。 c d g o d s i i 和g r o y i e 从多个角度对这类图进行了深入研究并且取得丰富成 田【l 】 7 ko 本文尝试利用代数理论主要是群理论来讨论k n e s e r 图的部分性质，得到了 如下主要结论。 首先，我们引入确定数的概念利用群论方法证明了k n e s e r 图j ( ，2 ，七) 的自同 构群与n 次对称群妙朋( 门) 同构。其次，我们进一步的证明了k n e s e r 图的半径为 2 ，由此，可以得到k n e s e r 图自中心的一个充分条件。最后，借助计算机程序， 我们分析了k n e s e r 图的谱以及l a p l a c e 谱并得到一个猜想。 关键词：k n e s e r 图自同构群半径谱 a b s t r a c t s e v e r a lp r o p e r t i e so fk n e s e rg r a p h a n di t sa u t o m o r p h i s mg r o u p i n t r o d u c t i o no ft h ea u t h o r ：w e n j i a n w e i ，m a l e ，w a sb o mi nj u l y ，19 7 6w h o s e t u t o rw a sp r o f e s s o rw e i g u i m i n h eg r a d u a t e df - r o m c h e n g d uu n i v e r s i t y o f t b c h n o l o g yi nm a t h e m a t i c a lo fc o m p u t a t i o nm 旬o ra n dw a sg r a n t e dt h em a s t e r d e g r e ei nj u n e ，2 0 0 8 a b s t r a c t l e tqb eaf i x e ds e to fs i z e ，2 t h ek n e s e rg r a p h ，( 力，七) h a s t h ev e r t e xs e tyw h i c hi st h ek - s u b s e t so fq ，a n dt h et w os u b s e t s a r ea d ja c e n ti ft h e i ri n t e r s e c t i o ni s e m p t y ( w h e r e ， ，z ， 七a r ef i x e d p o s i t i v e i n t e g e r s w i t h 刀 2 后， 七 1 ) t h e s eg r a p h sa r e i m p o r t a n t b e c a u s et h e ye n a b l eu st ot r a n s l a t em a n yc o m b i n a t o r i a lp r o b l e m s a b o u ts e t si n t og r a p ht h e o r y t h er e s e a r c h i n ga b o u tt h i sf a m i l yg r a p h s c o u l db ef o u n di nm a n ye x t e r n a lp a p e r sb u tl e s s i nt h ei n t e r n a l t h e m o s tf a m o u sr e s u l ti st h ek n e s e rc o n je c t u r ew h i c hi sf r o ml o v a s z l c d g o d s i la n dg r o y l eh a sa p p r o a c h e dt h ep r o p e r t i e so fk n e s e r g r a p h sf r o md i f f e r e n ta n g l e sa n dm a n yr e s u l t sh a sb e e ns h o w ni nt h e i r b o o k r e f 1 i nt h i sp a p e r ，w es h a l le x p l o r es e v e r a lp r o p e r t i e so fk n e s e rg r a p h v i at h em e t h o dr e l a t e dt oa l g e b r a i ca n dg r o u pt h e o r y ，w h i c hs h o u l db e i n t r o d u c e da sf o l l o w t h ef i r s t ，w eg i v ean e wp r o o fw h i c hs h o w nt h a tt h ea u t o m o r p h - i s mg r o u po fk n e s e rg r a p h ，( 玎，尼) i si s o m o r p h i c t ot h es y m m e t r i c g r o u p妙，2 ( ”)b yi n t r o d u c i n gac o n c e p tn a m e df i x i n gn u m b e r s e c o n d ， w ev e r i f yt h a tt h er a d i u so fk n e s e rg r a p h，( 门，七) e q u a lst o2 b yt h i s ， w es h o u l do b t a i ns i m p l ec o r o l l a r ya b o u tk n e s e rg r a p hi ss e l f - c e n t r a l t h el a s t ，w i t ht h e a i do fc o m p u t e r ， w el is tt h e s p e c t r u m sa n d l a p l a c i a ns p e c t r u m s o fs o m ek n e s e r g r a p h s w i t ht h e s p e c i a l p a r a m e t e r s ，a n dac o n je c t u r ec o u l db ep r o v i d e d k e yw o r d s ：k n e s e rg r a p h a u t o m o r p h i s mg r o u p r a d i u ss p e c t r u m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得盛壑理王太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者导师签名：磊套杌 学位论文作者签名： 妒雹3 疑_ 日 学位论文版权使用授权书 本学位论文作者完全了解盛叠堡王太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盛都堡王太堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 翮年厂月夕日 c h a p t e r1i n t r o d u c t i o n t h es o u r c eo fg r a p ht h e o r yc a nb et r a c e db a c kt o17 8 3 ；a tt h a t t i m et h ef r u i t f u lm a t h e m a t i c i a nl e u l e rs u c c e s s f u l l v s o l v e dt h e k o n i g s b e r gb r i d g e sp r o b l e mw h i c hh a db e e no b s e s s e dl o c a lp e o p l ef o r m a n yy e a r s g r a p ht h e o r yh a sb e e nb o r ni nt h i st i m e a f t e rt h a t ，m a n y m a t h e m a t i c i a n ss u c ha sd k 6 n i g ， j p e t e r s e n ，t g a l l a i ，w 。h a m i l t o n ， p t u t t e ， p e r d 6 sg a v es t r e n u o u sa t t e m p t st om a k eg r a p ht h e o r y t ob e c o m ea ni n t a c ts u b j e c t i ti sw e l lk n o wt h a tg r a p ht h e o r ym a d e e x t e n s i v ea n dd e e p l yi n f l u e n c ei n t ot h eo p t i m i z a t i o nt h e o r y ，o r g a n i c c h e m i s t r y ，t h e o r e t i c a lp h y s i c sa n dc o m p u t e rs c i e n c e i nt h ee a r l y19 t h ，g a l o i si n t r o d u c e dt h ec o n c e p to ft r a n s i t i v e g r o u p ，w h e nh es t u d i e dt h ei s s u eo ff o r m u l a sr a d i c a ls o l u t i o n sa b o u t t h e h i g h - o r d e re q u a t i o n s ， s i n c e t h e n ， g r o u pt h e o r y b e c o m ea n i n t e r n a t i o n a lm a t h e m a t i c a lc o m m u n i t yw i d e l yr e s e a r c h i n18 7 8 ，t h e f a m o u se x p e r t so fg r o u pt h e o r y ，f r o ma c a y l e y ，d e f i n e dt h ec a y l e y g r a p ho ft h eg r o u pa n dh ew a st h ef i r s tc o m b i n et h eg r o u pt h e o r ya n d g r a p ht h e o r y ，w h e nh ei n t e r p r e t e dg r o u p sg e n e r a t o r sa n dd e f i n i t i o n o fr e l a t i o n s i n19 8 3 ，r f r d c h td e m o n s t r a t e dt h a ta n ya b s t r a c tg r o u p i si s o m o r p h i ct oa na u t o m o r p h i s mg r o u po fag r a p h h i so u t s t a n d i n g c o n t r i b u t i o ne s t a b l i s h e dc l o s er e l a t i o n sb e t w e e ng r o u pt h e o r ya n d g r a p ht h e o r ya n dw i d e l yu s e dm e t h o do fg r o u pt h e o r yi nt h em o d e r n t h e o r i e so fg r a p ht h e o r y ，a n di n i t i a t e dt h es c i e n c eb r a n c ho fa l g e b r a i c g r a p ht h e o r yf r o mt h a t i nl9 7 4 ，n l b i g g sp u b l i s h e da no p u s 彳，g p 6 r 口f cg 厂口p i f zr 办p d y ，i t w i d e l yu s e st h el a n g u a g eo ft o p o l o g ya n dg r o u pt h e o r yt op u tf o r w a r d an e wi n t e r p r e t a t i o nf o rt h eb a s i st h e o r yo ft h em a p ，a n dt u r n st h e g r a p ht h e o r yp r o b l e mi n t oa l g e b r ap r o b l e mt os t u d y ，f o r m a t san e w t h e o r y t h ep u b l i c a t i o no ft h i sm o n o g r a p hm a r k st h ea l g e b r a i cg r a p h t h e o r yh a sb e c o m eac o m p l e t et h e o r e t i c a ls y s t e m i n2 0 0 2 ，p r o f e s s o r f a ny u nw h of r o mw u h a n u n i v e r s i t y ， w r o t et h e g ，d 材p w f f 办 c d ，竹6 f 门口f f d 力c d d f 门g ， ab o o kc o m b i n e sg r o u pt h e o r y ，g r a p ht h e o r ya n d c h e n g d uu n i v e r s i t yo ft e c h n o l o g ym a s t e r sd e g r e et h e s i s c o d i n gt h e o r yo r g a n i c a l l y ，r e i n t e r p r e t st h ec o d i n gl i n e a rc o d ea n d r e c y c l i n gc o d eb yu s i n gt h ea l g e b r a i cl a n g u a g e ， a n de n r i c h e st h e c o d i n gt h e o r yf u r t h e r t h e r e f o r e ，i th a sb e c o m ea ni m p o r t a n tr e s e a r c h d i r e c t i o nt h a tu s e st h ec e r t a i nm e t h o d so fg r o u pt h e o r yt os t u d yt h e i s s u eo ft h em a p st h e o r ya n de n r i c h e sc o d i n gt h e o r yf u r t h e ri nt h e s e a r e as i n t h i st h e s i s ，w es h a l lm a i n l ys t u d yt h ek n e s e rg r a p h s ，w h i c h p l a ya ni m p o r t a n tr o l ei na l g e b r a i cg r a p ht h e o r ya n a l o g o u st o t h a t p l a y e db yt h ec o m p l e t eg r a p h si nt h ec l a s s i c a lg r a p ht h e o r y t h e p a p e rc o u l db ed i v i d e di n t o t h r e ep a r t i t i o n s 。t h ef i r s t ，w ei n t r o d u c e s e v e r a lt e r m i n 0 1 0 9 i e sa b o u tg r a p h ，g r o u pa n dr e p r e s e n t a t i o nt h e o r yo f g r o u p ，a l lo ft h e mc o u l do c c u rt h r o u g h o u tt h en e x ts e c t i o n s s e c o n d ， w e s h o wt h ep r o p e r t i e so ft h ep e t e r s e ng r a p hw h i c hi sas p e c i a l e x a m p l eo ft h ek n e s e rg r a p h s t h el a s t ，w es h o wt h em a i nr e s u l t s a b o u tk n e s e rg r a p h sw h i c hi n c l u d et h ec o n s t r u c to ft h ea u t o m o r p h i s m g r o u po ft h ek n e s e rg r a p h ，t h er a d i u s o ft h e ma n dt h es p e c t r u mo f s o m eo ft h ek n e s e rg r a p hw i t hf i x e sp a r a m e t e r m o r e o v e r ，t h e r ei sa c o n j e c t u r es h o u l db el i s t e dw h i c hi su n s o l v e di nt h i sp a p e r s i n c et h i s f a m i l yg r a p h sa f f e c t e db yt h et w op a r a m e t e r ，w eh a v et os t u d yt h e m f t o mal o c a la r e a s ，a n dm o s to ft h er e s u l t sc o u l db eg e n e r a l i z e di nt h e f u t l 】r e 2 2 1g r o u p c h a p t e r2b a s i ct e r m i n o l o g y a 盟幽殴业1 sas e ts a t is f y i n gc l o s u r el a w sa n da s s o c i a t i v el a w s l e 【 “b eas e m i g r o u p i ft h e r ei s a ne l e m e n t ，s a y1 ，s u c ht h a t 12=p 1 7 ra n y ：1 e m e n g1 ng ，t h e ni t c a nb ec a l l e d a n ( ! 星! ) i 鱼曼旦! i ! y 幽a s e m i g r o u pw h i c hc o n t a i n sa ni d e n t i t ye l e m e n ti s s a i dt o b e 趔f o ra n ye l e m e n t gi ng ，i ft h e r ei s a ne l e m e n tzs u c h 2 h a 2 了2 1 ，h e nw er e g a r dt h i s e i e m e n ta st h e 世曼噬o f g ，w ew i l l u s e g d e n o t et h ei n v e r s e o fe l e m e n t g ag ! q 堕卫gi s a s e m l g r o u ps a t i s f y i n gt h ef o l l o w i n gs t a t e m e n t s ： ( 1 )gc o n t a i n sa ni d e n t i t ye l e m e n t ： ( 2 ) f o ra n ye l e m e n tgi ng ，t h e r ei s a ni n v e r s eing a 剑必。fg r 。u pgi s a g r 。u p 日s u c ht h a t 月j s c 。n t a i n e di ng i fa l ie l e m e n t s 。f 日a r ec 。m m u t a b l e i n g ，t h a ti s ， 馏2 黟，w h e r e 比日，g ， t h e nw es a yt h e s u b g r o u p日i s 幽m a l l e t g b ea ne l e m e n to f 篓_ p ，g 掣hk a s u b g r o u p 。f g t h e s e t 妒( r e s p 坛) i s d e f i n e da sf o l l o w 。7 删：2 助iv 办日) ， t n l s1 ss a l db ea 量曼f 生【曼墨j l 主逝曼q 墨星! o ft h e g r o u pg t h ec a r d i n a l n u ? b e r r “。t h “e f to r “曲t c o s e to fas u b g r o u p 日i nag r o u pgi s c a lj e d h e 趣虹i f i nga n di sw r i t t e n jg ：何卜 ag r o u pgi s a ! 二g 丛坐旦i fe v e r ye l e m e n to fge x c e p tt h e 1 d e n t l t yh a so r d e rap o w e ro fap r i m e p as u b g r o u pso fag r o u p u1 sa 龇幽幽岫 o fgi fi ti sa p g r o u pa n di sn o tc o n t a i n e d l na n yl a r g e r p g r o u pw h i c hi sas u b g r o u po f g l e tgb eag r o u p ， 口，g g w es a yt h ee l e m e n t t h e 旦旦妇竺y ! ! 垒塾墨! 垦! i q 塾o ft h ee l e m e n t w es a ye l e m e n t g t h ed e f i n i t i o nf r o m t h a ti s ， 韭a n s l a t e p1 口52 g 昭i s 口 u n d e rt h ee l e m e n t g ，o r t h ee l e m e n t 口a n dw em a yg e n e r a l i z e a ne l e m e n to f gt 。as u b s e t 日。ft h e g r 。u p ， c h e n g d uu n i v e r s i t yo ft e c h n o l o g ym a s t e r sd e g r e et h e s i s g - 1 嵫= g _ 1 蛔iv 办日) i st h e 昼q 坠j 堕g 旦曼y ! ! 垒望墨! 垒! i q 望u n d e r g as u b g r o u p o fag r o u pg iss a i dt ob ean o r m a ls u b g r o u pi f g 一乒辔= 日f o ra l lg g l e tga n d 日b et w og r o u p s t h e 鱼i ! 曼鱼! p q 鱼堕曼! o ft h e mi sa s e t ，w r i t t e ng 日，c o n s i s t so fa l lt h ee l e m e n t s( g ， ) ，w h e r egf r o m t h eg r o u pga n d厅f r o mt h eg r o u ph t h a ti s ， g 日= ( g ，办) jg g ，向) i t i se a s yt op r o v et h a tt h ed i r e c tp r o d u c to ft w og r o u p si sag r o u p l e tqb eap o i n ts e tw i t hs i z e疗t h es e to fa l lo n e - t o o n e m a p p i n go ni t s e l fc a nb es a i ds y m m e t r i cg r o u po nq ，a n dd e n o t e db y 妙惭( q ) ，o rju s t 劬”( 门) t h en e x tr e s u l t sn a m e db yt h em o s tf a m o u s m a t h e m a t i c i a n sa r ev e r yi m p o r t a n ti nt h ew h o l eg r o u pt h e o r y t h e o r e m2 1 1 ( c a y l e y ) e v e r y g r o u pi si s o m o r p h i ct o as y m m e t r i c g r o u po fi t so w ne l e m e n t s t h e o r e m2 1 2 ( l a g r a n g e ) t h eo r d e ro fag r o u pgi st h ep r o d u c to f t h eo r d e ro fas u b g r o u pha n dt h ei n d e xo fhi ng t h e o r e m2 1 3 ( s y l o w ) l e tgb eag r o u pw i t ho r d e r 刀 ( 1 ) i f 甩= p ”jw h e r ep ，p i sa p r i m e ， t h e ngc o n t a i n s s u b g r o u p s o fo r s e r s p ，f = l ，”， a n de a c h s u b g r o u p o f o r d e r s p ，f = 1 ，聊一1 ，i san o r m a ls u b g r o u po fa tl e a s to n es u b g r o u po fo r d e r 矿1 ( 2 ) t h es y l o wp s u b g r o u p so fga r ec o n ju g a t e ( 3 ) t h en u m b e ro fs y l o wp s u b g r o u p so f gi so ft h ef o r m 1 + 印 a n di sad i v i s o ro f 疗 2 2g r a p h i nt h i ss e c t i o nw es h a l ld e f i n es o m eb a s i cg r a p h - t h e o r e t i ct e r m s t h a tw i l lb eu s e di nt h i sp a p e r o t h e rg r a p h - t h e o r e t i ct e r m sw h i c ha r e n o ti n c l u d e di nt h i ss e c t i o nw i l lb ed e f i n e dw h e nt h e ya r en e e d e d 4 a g 羔旦卫旦 gi st r i p l e( y ( g ) ，e ( g ) ，)c o n s i s t i n go fan o n e m p t ys e t 矿( g )o fv e r t i c e s ，as e te ( g )o fe d g e sa n dar e l a t i o n 矽 t h a ta s s o c i a t e e v e r ye d g ew i t ht w ov e r t i c e s c a l l e di t se n d p o i n t s o nu s u a l l y ， w e r e p r e s e n tt h es e te ( g )a s as u b s e to fy ( g ) y ( g )w h i c he l e m e n t s a r eu n o r d e r e dp a i r( 石，y ) ，w h e r e x ， yb e l o n gt o矿( g ) ，s u c hg r a p h s c a nb ec a l l e du n d i r e c t e dg r a p h s w ew i l lu s u a l l yu s e 叉) ， r a t h e rt h a n ( x ，y ) t od e n o t ea ne d g ej u s td u et oc o n v e n i e n c e i ft h e r ei sa ne d g ei n ag r a p hw h i c hh a v i n gt h es a m ee n d p o i n t ，w es a yi tc o n t a i n sa 旦业，o r t h e r ei st w oe d g e sw h i c hh a v i n gt h es a m ee n d p o i n t sx ，y ，w h e r ex y ， w es a yi tc o n t a i n s 也坠! ! i p ! 星星亟g 曼墨i ng e n e r a l ，w ej u s tc o n s i d e rg r a p h s w h i c hh a v en e i t h e r1 0 0 p sn o rm u l t i p l ee d g e s t h ef o l l o w i n gt e r m i n o l o g i e sa r er e a l l ys i m p l e a n db eu s e d f r e q u e n t l y t h e 也 o fag r a p hgi st h en u m b e ro fv e r t i c e si ng ， a n dt h e 逝o fgi st h en u m b e ro fe d g e si ng i ft h e r ei sa ne d g e砂 i ng r a p hg ，t h e nw es a yt h a tt h ev e r t e xxi s 垦鱼i 鱼巡t ov e r t e xy ， w r i t t e nx 口y ，a n dt h es a m et i m ew ea l s os a yt h ee d g e砂 i si n c i d e n t w i t hv e r t e x x ( y ) i f砂 i sa ne d g eo fg ，t h e nw es a yt h ev e r t e xy i s an e i g h b o ro fv e r t e xx i fa n yt w ov e r t i c e si nag r a p hg w i t ho r d e r 以a r ea d ja c e n t ，t h e ni ti ss a i da 璺q 盟卫! 曼! 曼g 垦p hw h i c hd e n o t e db yk j t h e r ea r ea tl e a s tt w om a t r i x e sc o r r e s p o n d i n gw i t he v e r yg r a p h ， w h i c ha r ec a l l e da d j a c e n tm a t r i xa n di n c i d e n tm a t r i x t h e 垦鱼i 鱼剑 m a t r l x w h o s e 么( g ) o fag r a p hgw i t ho r d e r 力i sa月，z s q u a r em a t r i x e n t r i e s a r eg i v e nb y 旷娃乞忌患”加c e m ； t h ei 堕曼i 鱼曼堕! 堡垦! ! i 苎o fag r a p hw i t ho r d e r 刀a n ds i z emi s t h e 甩朋m a t r i xw h o s ee n t r i e s 岛， a r eg i v e nb y zf1 ，矿1 ，j 捃f ，2 c f 出，2 ，w 砌巳； 2 1 0 ，d f 乃p m 娩 i nm a n yc o n d i t i o n s ，w eju s tf o c u so nt h ef o r m e rs i n c ei th a sm o r e w e l lp r o p e r t i e st h a nt h e1 a t t e rs u c ha si ti sas y m m e t r i cm a t r i xa n di t s t r a c eis7 e r o a甜一v巡i nag r a p hi s as e q u e n c eo fv e r t i c e s ， w h i c hb e g i n w l t h 甜 a n d e n d i n g a t ys u c ht h a t c o n s e c u t i v ev e r t i c e s i nt h e s e q u e n c ea r ea d ja c e n t ，e x p r e s s e da sf o l i o w ： ：甜2 ，v l ，唯2v ， w h e 。e后0a n d 哆a n da r ea d j a c e n tf o r f ：0 ，1 ，七一1 1 1扰2y ，t h e nt h ew a 】k 矿i s 出血a甜一， w a l ki nag r a p hw h i c h n ov e r t l c e sa r er e p e a t e d i ss a i dt o b ea 甜一1 ，巡ac l o s e dp a t hi s s a i dt ob ea 蛆出，w h i c hd e n o t e d ei fi tc o n s i s t so f刀 v e r t j c e s a 逊o fag r a p hw i t hac y c l ei s t h el e n g t ho fi t s s h o r t e s tc v c l e s o m e t i m e s ，t h et e r m i n 0 1 0 9 yc o u l db es a y 壁垒g 曼 a c y c j e1 nag r a p h gt h a tc o n t a i n se v e r yv e r t e xo f gi sc a l l e d a 旦型堕吐丝旦遮旦j 唑o fg t h u sah a m i l t o n i a nc y c j eo fgi s a s p a n n l n gc y c l eo f g a 地逝坌坠g ! 垫地i sag r a p ht h a tc o n t a i n sa h a m l l t o n l a nc y c l e a n 匝娅业蛐i nag r a p hgi sap a t hw h i c h c o n a l n se v e r ye d g eo f g t h u sa n 星坚! 曼! i 垦塾g ! 垦卫h i sag r a p ht h a t l e “a n dvb et w ov e r t i c e s i ng r a p h g i ft h e r ei sa “一v p a t h1 ng ，t h e nw es a yt h a t 甜 a n dv a r e 曼q 旦墼曼璺幽，o t h e r w i s e “ a n dv a r e 鱼i 曼q q 里里巡w h e n e v e ra n yt w ov e r t i c e si n ag r a p ha r e c o n n e c t e d ，w em a ys a yt h eg r a p hgi s 曼q n 坠曼曼! 星亟，o t h e r w i s e w es a v t n e g r a p h i s 鱼i 曼q q 旦卫星巡 e v e r yc o n n e c t e d s u b g r a p h i na d l s c o n n e c e dg r a p hi sc a l lb ea 蚴出t h e r e f o r e ，m a n y p r o b l e m s o l d l s c o n n e c t e d g r a p hc a nb et r a n s l a t e d i n t ot h e p r o b l e m so f c o n n e c t e dg r a p h t h el e n g t ho ft h e l o n g e s t 甜一1 ， p a t hi ss a i dt ob e t j l e 鱼土曼垒迎b e t w e e n甜a n d 1 ，d e n o t e db yd i s t ( 材，y ) w h e n e v e r甜 a n d1 ， a r ed i s c o n n e c t e d ， w ed e f i n et h ed i s t a n c e b e t w e e nt h e ma s i n t l n l t e ，t h a ti s ，d i s t ( 甜，v ) = t h eg r e a t e s td i s t a n c eb e t w e e n a n vt w o v e r 1 c e s1 nag r a p h gi ss a i dt o b et h e 幽也皇蛆o f g ，d e n o t e d b v 6 s 计 e u 娜三 泖 o u 一 r 名 孔= 州 n 一 一生 t o 海 s “ 心 o r d 五 o 旷k e e )堂叭眦删 脚 阻 c 虹螂m 蛳沁 t w 增d c h a p t e r2b a s i ct e mi n o l o g y 坊口惭( g ) ，t h a ti s ，坊口聊( g ) =