（应用数学专业论文）图的高阶边连通性和网络的可靠性比较.pdf

图的高阶边连通性和网络的可靠性比较 摘要 本文在网络可靠性比较和寻优问题的背景下研究图的高阶边连通性质。首先 研究高阶边连通度的存在性问题，然后研究其上界、极大性和超级性等一系列优 化问题。利用对三阶边连通度的研究结果，建立了新的第三层局部可靠性比较判 定准则，证明了拟正则完全二部图k k + 1 和拟正则完全三部图耳 + 1 k + 1 分别在 所属的具有相同点数和相同边数的图类中是唯一的局部最可靠图。 ， f 本文中提到的图都指无向简单图。对连通图g 和正整数h ，g 的一个边子集 t s 称为g 的h 阶边割，如果g s 不连通，且其每个连通分支至少有h 个点。如果 g 有h 阶边割，把g 的h 阶边割的最小基数定义为g 的h 阶边连通度，并记作 ) m g ) 。很明显，若g 不是平凡图k t ，a 1 ( g ) 就是通常的边连通度a ( g ) ，而a 2 ( g ) 则是e s f a h a z f i a m 和i i a l d m i 首先提出并研究的限制性边连通度a ( g ) 【“。当h 2 时，如果h ( g ) 存在( 即g 有h 阶边割，从而h ( g ) 可定义) ，则它作为度量g 的 更深入的边连通性质的参数近年来已开始受到关注【7 8 t 2 4 一删。以下将从高阶边通 度的存在性问题、优化问题、以及它在网络的可靠性比较问题上的应用这三个方 面来概述本文的新结果。 1 存在性问题 设g 是n 阶连通图，n 1 ，则h ( g ) = a ( g ) 一定存在je s f a h a n i a n 和h a k i m i 在【8 】中证明：a 2 ( g ) 存在当且仅当t l 4 且g 不是星图k t ，。一1 。当h 2 时， h ( g ) 的存在性问题，就我们所知，除n 2 h 是, m g ) 存在的必要条件，以及若 h ( g ) 存在，则h l ( g ) 也存在这两个明显结论外，还没有其它结果。下面是本文 上海交通大学博士学位论文 在条件n 2 h 下关于a h ( g ) 的存在性的新结果： ( 1 ) a h ( g ) 存在当且仅当g 有两个点集不交的h 阶连通子图。 ( 2 ) 若g 是2 连通的，则h ( g ) 存在。 ( 3 ) 若a ( g ) = 1 2 m l n j ，则a h ( g ) 存在，其中m 表示g 的边数。 ( 4 ) 若g 的最小点度6 ( g ) h ，则h ( g ) 存在。 ( 5 ) 刻划了a 3 ( g ) 不存在的所有图g 。 2 1 上界 2优化问题 熟知a l ( g ) 5 l ( g ) ，这里6 1 ( g ) = 6 ( g ) 是g 的最小点度，即g 中与一点相关 联的边集的最小基数。又已证明f 8 ，如果a 2 ( g ) 存在，则有a 2 ( g ) 6 2 ( g ) ，其中 5 2 ( g ) 是g 的最小边度，即g 中与一边相邻的边集的最小基数。 一般地，对于正整数h 【n 2 j ，可定义g 的h 阶最小外度靠( g ) 如下： 设f 是g 的一个h 阶导出连通子图。把g 的一端属于f ，另一端不属于f 的边 的集，叫做f 的外关联边集，其基数叫做f ( 在g 中) 的外度，记作o ( f ) = a a ( f ) 。 用氕表示g 的所有h 阶导出连通子图的类，则g 的h 阶最小外度定义为 靠( g ) = m i n o ( f ) f 矗) 关于h ( g ) 的上界，本文得到h = 3 ，4 时的如下新结果： ( 1 ) 如果a 3 ( g ) 存在，则a 3 ( g ) 如( g ) 。 ( 2 ) 若g 是阶不小于8 的正则连通图，则k ( g ) 存在且a 4 ( g ) 6 4 ( g ) 。 上述结果可望进一步推进，我们猜测： 对任一正整数h ，如果a h ( g ) 存在，则k ( g ) “( g ) 。 i ； 上海交通大学博士学位论文 2 2 极大性 文献上称满足a ( g ) = 5 ( g ) 的图g 是极大边连通的，简称g 是a 图( 参见 【1 0 2 3 ) 。类似地，对h = 2 ，3 本文称h ( g ) = “( g ) 的图g 是极大h 阶边连通的， 简称g 是h 图。由于h 4 时尚未得到a 的紧上界，故相应的h 图还难以定 义。对于h = 2 ，e s f a h a n i a n 在 3 l 】中证明了k 维方图q b 是a 2 图。李乔良在他的 博士学位论文【6 】中研究循环图的可靠性时，给出了循环图是a 2 图的特征刻划。另 外，文献【2 4 3 0 分别在不同条件下研究了图的某些高阶边连通度的量值。尽管所 给出的量值，在一定意义下是最好可能的，但并没有回答它们是否确实是最好可 能的问题。这一不足应归因于未明确给出相应的高阶边连通度的紧上界。本文对 h = 2 ，3 得到了图g 是a h 图的一些新的充分条件： 1 设g 的阶r t24 。则当下列三个条件中有一个成立时，g 是a 2 图： ( 1 ) g 的任意一对不相邻的点的度和大于n ； ( 2 ) 6 ( g ) 2 且g 的直径d 与围长g 满足关系d g 一2 ； ( 3 ) g 是奇数阶或围长大于3 的连通点可迁图。 以上三个充分条件分别是l e s n j 8 1 【f ，s o n e o k ae t 口d l q 和m a d e r 1 4 给出的g 是 a 图的充分条件的相应推广。本文还分别举例说明他们给出的g 是入图的充分条 件都不足以保证g 是a 2 图，而本文给出的充分条件在一定意义下均不能减弱。 2 设g 的阶n 6 。则当下列两个条件中有一个成立时，g 是a 3 图： ( 1 ) g 的任意一对不相邻的点的度和大于n + 2 ； ( 2 ) g 不含有团k 4 ，且任意一对不相邻的点的度和大于n 一1 。 2 3 超级性 如果g 的每一个最小边割必孤立g 的一个点，则称g 是超级边连通的，简记 为s u p e r a 。容易看到，超级边连通图一定是极大边连通图，但反之不然。因此， m 上海交通大学博士学位论文 图的超级边连通性是比极大边连通性更深入的边连通性质。图的超级边连通性的 概念是b a u e r 等在研究网络的可靠性比较时首先正式提出的 3 5 ，4 0 】。尔后，图的超 级边连通性得到了广泛的研究 s s - 4 4 。象极大边连通性一样，本文对超级边连通 性作如下推广：设g 有h 阶边割且h 3 。如果g 的每一个最小h 阶边割必孤立 g 的一个h 阶导出连通子图，则称g 是h 阶超级边连通的，简记为s u p e r h 。不 难证明s u p e r h 图一定是h 图。亦不难举例说明反之不然。对h 3 ，本文研究 图的s u p e r h 性质得到下列新结果。 1 f i 0 1 ”l 给出过图g 是s u p e r a l 的一个充分条件，本文证明该条件也是必要 的，即，直径为2 的图g 是s u p e r - 的当且仅当其最小度点集m 所导出的子图 g m 】不含有团凰，其中5 = 6 ( g ) 。 2 设g 的阶n 4 。则有 ( 1 ) 如果g 的任意一对不相邻的点的度和大于n + i ，那么g 不是s u p e r - a 2 的当 且仅当t ；为偶数且g 为( 2 ，2 ) 型杠铃图( 定义见后) 。 ( 2 ) 如果g 的最小点度5 3 且直径d 与围长g 满足关系d g 一2 ，那么g 不 是s u p e r - a 2 的当且仅当g 同构于q i ( 如正文图4 1 所示) 。 ( 3 ) 如果g 是围长大于4 的 ( 3 ) 正则连通点可迁图，那么g 是s u p e r a 2 的。 3 设g 的阶n 6 。如果g 的任意一对不相邻的点的度和大于n + 3 ，则g 不是 s u p e r a 3 的当且仅当n 为偶数且g 为( 2 ，3 ) 型杠铃图。其中，一个( ，r ) ( 女r ) 型杠铃图是指这样一个图，它的点集可剖分为两个基数为的点集a ，刀使得导出 子图g 刎，g 旧】是团，而a ，b 之间的边集所导出的子图是一个r 正则二部图。 3 在网络的可靠性比较问题上的应用 网络部件间的连接方式称为网络拓扑。网络可靠性是指网络拓扑为网络在其 上海交通大学博士学位论文 组成部分处于有随机故障的环境中工作时所提供的合适的连接能力【4 5 。 网络的可靠性比较研究这样两个基本问题【4 7 ，4 8 ： 1 给定点数和边数都相同的两个网络拓扑，如何判定哪个更可靠? 2 如何找到最可靠图? 网络可靠性研究的一种基本数学模型，文献上称作m o o r e s h a n n o n 模型，将网 络拓扑抽象为一个概率图，并假定图的点完全可靠，而边则以相同的概率p ( 0 ，1 ) 相互独立地发生故障 5 8 】。 用f l o ( n ，m ) 表示n 点、r n 边的连通图类。对g f ! o ( n ，m ) ，用a ( g ) 表示g 中 由i 条边构成的边割集的个数。b a u e r 和b o e s c h 等基于前人的研究在二十世纪八 十年代中期首先明确提出了当边故障率充分小时可靠性比较( 简称为局部可靠性 比较1 的一个判定准则口o 卅： 设g ，日f 2 0 ( n ，m ) ，如果a ( g ) a ( 日) ，或者a ( g ) = a ( 日) 但a ( g ) 2 ( 日) ，或者a 2 ( g ) = a 2 ( 日) 但e 。( g ) a 3 ( 日) ，或者a a ( g ) = a 3 ( 日) 但e 。( g ) 2 ，i f a h ( g ) e x i s t s ( f e ，gh a sa tl e a s to n eh t he d g ed i s c o n n e c t i n gs e t ， h e n c e ，a h ( g ) i sw e l ld e f i n e d ) ，t h e ni t m e a s u r e sd e e p e re d g ec o n n e e t e d n e s so fgw h i c h c a nn o tb ed o n eb yh 一1 ( g ) i n g e n e r a l n od o u b t ，t h eh t he d g ec o n n e c t i v i t yw i l lp l a y a ni m p o r t a n tr o l ei nr e v e a l i n gd e e p e rt o p o l o g yo fg r a p h sa n dt h e r e f o r ew i l la r o s em a n y a n t h e r si n t e r e s ti nt h ef u t u r e t h i si m p o r t a n tc o n c e p tw a s a l r e a d yp r o p o s e db yh a r a r y i n 【7 】h o w e v e r ，s of a r ，m a n yv i t a lp r o b l e m sa b o u ta h ( g ) i ss t i l lo p e n ，a n dm a n yi m p o r t a n t p r o p e r t i e so fa h ( g ) a r e1 i n o w n t h i sd i s e r t a t i o nf i r s ts t u d i e si t se x i s t e n c ep r o b l e m ，t h e n i n v e s t i g a t e sas e r i e so fi t so p t i m i z a t i o np r o b l e m s ，s u c ha su p p e rb o u n d ，m a x i m a l i t ya n d s u p e r i o r i t y ，e t c ，l a s t l ya p p l i e si t t on e t w o r kr e l i a b i l i t yc o m p a r i s o n c o n s e q u e n t l y ，s o m e u n i q u el o c a l l ym o s tr e h a b l eg r a p h sa r ef o u n d 1 e x i s t e n c ep r o b l e m l e tgb eac o n n e c t e dg r a p ho fo r d e rn 1 ，t h e na i ( g ) = a ( g ) c e r t a i n l ye x i s t s i n 8 】，e s f a h a n i a n h a k i m ip r o v e dt h a ta 2 ( g ) e x i s t si fa n do n l yi fn 4a n dg i s n o tt h es t a r k 1 n 一1 f o rh 2 ，a s f a ra sw ek n o w ，t h e r eh a sb e e nn or e s u l t so i lt h e e x i s t e n c ep r o b l e mo fa h ( g ) ，a p a r tf r o mt w oa p p a r e n tc o n c l u s i o n st h a tn 2 hi sa 上海交通大学博士学位论文 n e c e s s a r yc o n d i t i o nf o ra k ( g ) e x i s t s ，a n di fa h ( g ) e x i s t s ，t h e ns od o e s 入i ( g ) f o ra n y p o s i t i v ei n t e g e ri n f o ra n yp a i ro f n o n a d j e c e n tv e r t i c e st a n d i ng ，w h e r ed ( u ) i st h e v e r t e xd e g r e eo ft i ng ： ( 2 ) 6 2 a n ddsg 一2 ，w h e r e6 ，da n dgd e n o t et h ei r i n i i n u i nv e r t e xd e g r e e ，d i a m e t e r a n dg i r t ho fg r e s p e c t i v e l y ； ( 3 ) g i sac o n n e c t e dv e r t e xt r a n s i t i v eg r a p hw i t ho d do r d e ro rw i t h o u tt r i a n g l e t h et h r e es u f f i c i e n tc o n d i t i o n sa b o v ec a r r yt h ec l a s s i c a lr e s u l t so nt h em a x i m a l i t y o fa ( g ) ，b e l o n g i n gt ol e s n i a k i 引，s o n o k ae t 口删a n dm a d e r 圳r e s p e c t i v e l y ，as t e p f o r w a r d m o r e o v e r ，t h e r ea r ee x a m p l e s i nt h ed i s e r t a t i o nt oi n u s t r a t et h a tt h e i rs u f f i c i e n t c o n d i t i o n sf o rgt ob eaag r a p ha r en o ts u f f i c i e n tf o rg t ob ea 2 g r a p h ，a n df u r t h e r m o r e ， t h e s ee x a m p l e sa l s os h o w e dt h a ta ut h es u f f i c i e n tc o n d i t i o n sa b o v ef o rg t ob eaa 2g r a p h c a nn o tb ew e a l 【e ni nas e n s e 2 l e tgb eag r a p ho fo r d e rn 6 gi saa sg r a p hi fo n eo ft h ef o l l o w i n gt w oc o n d i t i o n s h o l d s ： ( 1 ) d ( u ) 十d ( ) 疗+ 2 f o ra n y p a i ro f n o n a d j e c e n tv e r t i c e st a n d i ng ； ( 2 ) gc o n t a i n sn oc l i q u ek 4a n dd ( t ) + d ( ) n 一1f o ra n yp a i ro fn o n a d j e c e n tv e r t i c e s l x ua n d i n g 2 3s u p e r i o r i t y 上海交通大学博士学位论文 c a l lg s u p e re d g ec o n n e c t e d ，o ri ns h o r t ，s u p e r - a ，i fe a c ho fi t sm i n i l n u l ne d g e d i s c o n n e c t i n gs e ti s o l a t e sav e r t e xi ng i ti se a s yt os e et h a tas u p e r - ag r a p hm u s tb e aag r a p h h o w e v e r ，t h er e v e r s ei su n t r u e t h e r e f o r e ，s u p e re d g ec o n n e c t i v i t yr e f l e c t s d e e p e re d g ec o n n e c t e d n e s st h a nm a x i m a le d g ec o n n e c t i v i t yd o e s t h ec o n c e p to fs u p e r 一 入w a so r i g i n a l l yp r o p o s e db yb a u e re ta 2 3 5 , 4 0 w h e nt h e ys t u d i e dn e t w o r kr e u a h i l i t y c o m p a r i s o np r o b l e m s i nt h e l a s tt w od e c a d e s ，i tr e c e i v e dm u c ha t t e n t i o n s s 一4 4 j u s ta s f r o mag r a p ht oa g r a p hf o rh = 2 ，3 ，o n ec a ng e n e r a l i z es u p e r - at os u p e r a a sf o l l o w s ： f o rhs3 ，s u p p o s et h a tgh a sa tl e a s to n eh t he d g ed i s c o n n e c t i n gs e t c a l lgh t h s u p e re d g ec o n n e c t e d ，o r i ns h o r t ，s u p e r - a h ，i fe a c ho f i t sn l i l i i n 唧h t h e d g ed i s c o n n e c t i n g s e ti s o l a t e sb 3 1i n d u c e dc o n n e c t e ds u b g r a p ho fo r d e rhi ng i ti sn o th a r dt op r o v et h a ta s u p e r - g r a p hm u s t b eaa g r a p h ，a n di ti se a s yt og i v ee x a m p l e sw h i c ha r e h g r a p h s b u tn o ts u p e r a hg r a p h s ( h = 2 ，3 ) o nt h eh t hs u p e re d g ec o n n e c t i v i t y , h = 1 ，2 ，3 ，t h e d i s e r t a t i o np r o v e st h ef o l l o w i n gr e s u l t s ： 1 f i o l s e lh a dg i v e nas u f f i c i e n tc o n d i t i o nf o rag r a p ht ob es u p e r ，t h ed i s e r t a t i o n p r o v e st h a ti t i sa l s oan e c e s s a r yo n e ，t h a ti s ，ag r a p hw i t hd i a m e t e r2i ss u p e r ai fa n d o n l yi ft h ei n d u c e ds u b g r a p ha i m c o n t a i n sn oc l i q u e 所，w h e r e5d e n o t et h em i m i i n u i n v e r t e xd e g r e eo fga n dm ，t h es u b s e to fv e r t i c e so fd e g r e e5i ng 2 l e t gb ea g r a p ho fo r d e rn 4 ，w e h a v e ： ( 1 ) i fd ( u ) + d ( v ) n + 1 f o ra n yp a i ro fn o n a d j a c e n tv e r t i c e st a n d 口i ng ，t h e n gi sn o ts u p e r - a 2i fa n do n l yi fni se v e na n dgi s a n ( 2 ，2 ) b a r b e l l ( a ( ，r ) - b a r b e l l ( 女r ) m e a n ss u c h ag r a p hw h o s ev e r t e xs e tc a nb e p a r t i t i o n e di n t ot w os u b s e t so fe q u a l c a r d i n a l i t y 南，s a ya a n db ，s u c ht h a tb o t hg a 】a n dg b a r e c l i q u e sa n dt h es u b g r a p h o fgi n d u c e db ya l l e d g e sb e t w e e na a n dbi sr - r e g u l a r f o re x a m p l e ，k k 如i st h e ( ，1 ) b a r b e l l ) ； ( 2 ) i f5 3a n dd g 一2 ，t h e n g i sn o ts u p e r a 2i f a n do n l y i f g i sn o ti s o m o r p h i ct o 斑( d e p i c t e d i nf i 9 4 1 ) ( 3 ) ac o n n e c t e dv e r t e xt r a n s i t i v eg r a p hg i s s u p e r a 2i fi t sd e g r e e 3a n di t sg i r t h g 5 x 上海交通大学博士学位论文 3 l e tgb eag r a p ho f o r d e rn2 6 i f d ( “) + 硪廿) 行+ 3f o ra n yp a i ro f n o n a d j a c e n t v e r t i c e st a n d 廿i ng ，t h e ngi sn o ts u p e r - a aj fa n do n l yi f t li s e v e na n dgi sa n ( n 2 ，3 ) b a r b e l l 3a p p l i c a t i o nt on e t w o r kr e l i a b i l i t yc o m p a r i s o n t h ei n t e r c o r m e c t i o nr e l a t i o n s h i pa m o n ge l e m e n t so fn e t w o r k si sr e f e r e dt on e t w o r k t o p o l o g y n e t w o r kr e l i a b i l i t ym e a n s as u i t a b l ei n t e r c o m t e t i o na b i l i t yo f f e r e db yt h en e t w o r kt o p o l o g yw h e ni t sc o m p o n e n t sa r ew o r k i n gi na ne n v i r o n m e n tt h a tt h eo p e r a t i n g e l e m e n t sm i g h tf a i li n c i d e n t a l l y 4 g i v e nt w on e t w o r kt o p o l o g yw i t ht h es a n 2 eo r d e ra n ds i z e ，h o wd ow ek n o ww h i c h o n ei sm o r er e l i a b l e ? h o wc a l lw ef i n dt h em o s tr e l i a b l eo n e 4 z ，4 8 】? aw e l lk n o w nm o d e lf o rn e t w o r kr e l i a b i l i t ys t u d y ，c a l l e dt h em o o r e - s h a n n o nm o d e l i nt h eh t e r a t u r e ，r e p r e s e n t st h en e t w o r kt o p o l o g yw i t hap r o b a b i l i s t i cg r a p hi nw h i c h a uv e r t i c e sa r ep e r f e c tr e l i a b l ew h i l et h ee d g e sm i tf a i li n d e p e n d e n t l yw i t haf i x e d p r o b a b i l i t yp ( 0 ，1 ) 口7 , 5 8 l e tg f 1 0 ( n ，m ) a n dg ( g ) b et h en u m b e ro fe d g ed i s c o n n e c t i n gs e t so fi e d g e s ， w h e r e n o ( n ，m ) d e n o t e s t h ec l a s so fc o n n e c t e d g r a p h sw i t hnv e r t i c e sa n dm e d g e s i n t h e m i d d l eo f1 9 8 0 s ，b o e s c he ta le s t a b l i s h e dac r i t e r i o nf o rn e t w o r kr e f i a b i f i t yc o m p a r i s o n b ye d g ec o n n e c t i v i t yaw h e n t h ee d g ef a i l u r ep r o b a b i l i t ypi s s u f f i c i e n t l ys m a l l ( i ns h o r t ， l o c a ln e t w o r kr e h a b i l i t yc o m p a r i s o n ) 4 0 4 q ： l e tg ，日s 2 0 ( n ，m ) i a ( g ) a ( 日) ，o ra ( g ) = a ( h ) b u t g ( g ) 2 ( 日) ，o ra 2 ( g ) = a 2 ( h ) b u t c k ( g ) a s ( h ) ，o ra 3 ( g ) = a 3 ( h ) b u tg 沁( g ) 以3 ( 日) ，t h e n gi sl o c a l l ym o r er e l i a b l e t h a n 日 3 k k “l i su n i q u el o c a l l ym o s tr e l i a b l ei nn o ( 2 k + 1 ， ( + 1 ) ) ，a n ds od o e s 甄，k + 1 k + z i nn o ( 3 k + 2 ，( + 1 ) ( 3 k + 1 ) ) k e y w o r d s ：g r a p h ，h t he d g ec o n n e c t i v i t y ，hg r a p h ，s u p e r - a h ，n e t w o r k ，r e l i a b i l i t y c o m p a r i s o n ，l o c a l l ym o s tr e l i a b l eg r a p h 第一章基本概念和高阶边连通度的存在性 本章第一节介绍全文所使用的记号、术语和基本概念。其中，大部分取自于文 献【1 】，少量取自于文献 2 】，还有一些是新定义的概念。第二节研究高阶边连通度 的存在性，解决了后文研究所需要解决的基础问题。 1 1 基本概念 设a 是一个实数， l 口j 表示不大于a 的最大整数，a 表示不小于a 的最小 整数。 设s 是一个集合，z 是一个元素。s 表示是s 的元素，说作。属于 s ；2 s 表示z 不是s 的元素，说作不属于f 。吲表示s 中元素的个数， 叫做s 的基数。i s i = 0 时，称s 为空集，用d 表示空集。l s i = 1 时，称s 为独 点集。如果s = z ) 是独点集，常写。代替 ) 。如果1 s i 是一个非负整数，称s 是有限集。否则，称s 是无限集。 设a ，b 是两个集合，a u 丑，叫做a 与b 的并，表示属于a 或日的元素所 成的集合ja n 曰，叫做a 与b 的交，表示既属于a 又属于b 的元素所成的集 合；a b ，叫做a 与b 的差，表示属于a 但不属于b 的元素所成的集合。 常把同一类对象( 如集合，图等) 所形成的集合叫做类。 设y 是一个有限非空点集。e 是y 的某些二元子集类。称有序对( k e ) 为 图。通常用g 来表示它。y 的元素叫做g 的点。e 的元素叫做g 的边。常写 口g 代替口v ，g g 代替e 刀。v = 矿( g ) ，e = e ( a ) 分别称作g 的点 集和边集。它们的基数i y 】，j ej 分别叫做g 的阶和大小。今后将专用n = n ( g ) ， l 矿 上海交通大学博士学位论文 m = m ( g ) 分别表示g 的阶和大小。把阶为n 、大小为m 的图叫做( m ) 图。如 果g 是一个( n ，m ) 图，把2 m n 叫做g 的( 点) 平均度。 设t ， v 。如果n ，口) e ，称它为g 的一条边。否则，称它不是g 的边。 为方便起见，将边 u ，”) 写作“ 。因此，t = ”u 。若e = t e ，则在g 中有 下列等价说法： ( i ) u ， 是e 的端点j ( 2 ) e 连接t 和口j ( 3 ) t ，相邻； ( 4 ) e 与u ，口相关联j ( 5 ) t ，口为e 所饱和，或e 饱和t ，口； ( 6 ) t 控制”，或v 控制t 。 g 中与”相关联的边所成的集合叫做 ( 在g 中) 的关联边集，记作( ”) = 如( v ) 。把d a ( v ) = i 如( v ) i 叫做口在g 中的度。在不引起混淆的情况下，简记为 d ( ) 。熟知， d ( ”) = 2 m v e v 如果d ( ”) 恒等于常数r ，称g 是r 正则的。用5 = 5 ( g ) 表示g 的最小点度； a = a ( g 1 表示g 的最大点度。若一6 = 1 ，称g 是拟正则的。 设e ，e 是g 的两条不同边。如果它们有公共的端点，则称它们在g 中相 邻。g 中与e 相邻的边数叫做e 在g 中的度，记作d ( e ) = d g ( e ) 。用5 2 = h ( g ) 表 示g 的最小边度，a m = 2 ( g ) 表示g 的最大边度。如果2 ( g ) 一h ( g ) = 0 ，称 g 是边正则的。类似地可定义边拟正则的概念。 设a 、b 是y 的两个不交子集。g 中端点分别属于a ，口的边所成之集记 作【a ，b 】。a ，b 间的边数表示成| 【a ，b i 或m o ( a ，b ) 。用i ( a ) 代替【a ，v a 。 2 上海交通大学博士学位论文 o ( a ) = i j ) l 叫做a 在g 中的外度。它是点度和边度的推广。关于外度，不难证 明，如下命题成立。 命题1 1 1 3 ，p 4 5 ，e z 4 8 ( 口) 】设x ，ysv 。则 z ( x u y ) + x ( xn y ) z ( x ) + ，( y )( 1 1 1 ) 设a v ，s 冬e 。a 中为s 中边所饱和的点所形成的集记作且( s ) ；s 中饱和 a 中点的边所形成的集记作s ( a ) 。如果s ( a ) = a ，称s 饱和a 。如果a = z ) ， 写s ( ) 代替占( 0 。如果s ( z ) 口，称z 为s 所饱和。当f s ( z ) f - l ( 2 ) 时，称是 s 单( 双) 饱和的。 g 中与点”相邻的点所成之集叫做”的邻域，记作( ”) = n o ( v ) 。一般地， 设a y ，把n a ( v ) = ( 口) n a 叫做”在a 中的邻域，d a ( v ) = i 以( ) l 叫做口在 a 中的度。更一般地，设丑是y 的另一个子集。把l v ( b ) = ( u v 6 日( ”) ) b 叫做b 在g 中的邻域。n a ( b ) = n ( b ) n a 叫做b 在a 中的邻域。 g 的点和边的交错序列v 0 e 1 口1 e k v k 称作连接点”o ，v k 的一条路，如果该序 列中没有相同的点且每条边的相邻项恰好是该边的端点。路的长度是指该路中的 边数。今后常用r 来表示某条长度为k 的路。为简洁起见，表达一条路时，只依 序写出它的点而略去它的边。如果g 的任意两个点之间都有一条连接它们的路， 则称g 是连通的。所有连通的( n ，m ) 图所成的类记作n o ( n ，m ) 。 设“。”是g 的两个不同点。如果g 中有连接”和 的路，把g 中连接u 和口的最短路的长度叫做u ，”间的距离，记作d ( t ，”) = d z ( u ，。) 。否则，定义 d ( u ，”) = d a ( u ，。) = 0 0 。g 的所有点对间的距离的最大值叫做g 的直径，记作 d = d ( g ) 。显然，g 是连通的充要条件是1 d ( g ) o o 。 设是一个正整数， g 。把6 ( 口) = 艟( ) = u g l d z ( u ， ) = 女 叫做口( 在 g 中) 的邻域。又设a v ，把盍( ”) = n “( ”) n a 叫做t i 在a 中的邻域。更一 3 上海交通大学博士学位论文 般地，设丑冬矿，定义口，b 间的距离为d ( v ，b ) = d g ( ，b ) = m i = a d a ( v ，b ) i b b ) 。 丑在g 中的 邻域为n ( b ) = 占( b ) = p g l d c v ，b ) = 。类似地，丑在a 中 的女邻域为i ( b ) = n ( 丑) n a 。 。 一 、 g 的点和边的交错序列”1 e 1 ”2 钆。1 称作g 的一个圈，如果它满足： ( 1 ) 该序列中每条边的相邻项恰好是该边的端点 ( 2 ) 首尾两个点相同； ( 3 ) 除了首尾两个点再也没有相同的点。 圈的长度是指该圈中的边数。常用仉来表示某个长度为的圈。岛，吼又分别 叫做三角形和四边形。g 中最短圈的长度叫做g 的围长，记作g = g ( g ) 。最长圈 的长度叫做g 的周长，记作c = c ( g ) 。若c = n ，则称g 是h 碰i t o n 图。没有圈的 图叫做无圈图。连通的无圈图叫做树。熟知，一个连通图为树当且仅当m = n 一1 。 1 1 2 子图 设h ，g 是两个图。如果v ( h ) v ( g ) 且e ( h ) e ( g ) ，称且是g 的子图， 记作日g 。当日g 但h g 时，称日为g 的真子图。说g 的子图日是支 撑子图，如果v ( h ) = v ( g ) 。 设a 是y 的一个非空真子集。用g 【创表示g 的这样一个子图：它的点集是a ， 边集则由g 中所有两端点均在a 中的边所构成。这时，称g 是g 的由a 所导出 的子图。说g 的子图日是g 的一个( 点) 导出子图，如果e ( h ) = e c g c v ( h ) ) 。 为了方便，在不引起混淆的情况下，我们不区分a 和c a 】，即a 既看作g 的点子 集，又看作g 的导出子图。且在v 中的余集v a 记作互a 常将导出子图g 【訇写 作g a 。当a = t o ) 为独点桌时，g 一 d ) 被写作为g 一口。g 的极大导出连通 子图叫做g 的连通分支。 设s 是e 的一个非空真子集用g s 】表示g 的这样一个子图：它的边集是 4 上海交通大学博士学位论文 s ，点集则由s 中的所有边的端点所构成。这时，称a s 是g 的边导出子图。s 在e 中的余集记作雪。将g 的以雪为，边集的支撑子图记作g s 。当s = e ) 为 独点集时，g 一 e ) 被写作为g e 。 如果a 是g s 的一个连通分支，即i ( a ) s ，称s 孤立a 。 用磊表示g 的h 阶导出连通予图类，其中1 h h 2 j 。定义 靠= 靠( g ) = m i n o ( f ) l f 氕) 为g 的h 阶最小度。当h = 1 ，2 时，它们就分别是g 的最小点度和最小边度。 设g 1 和g 2 是g 的两个子图。说它们是不交的，如果它们没有公共点。说它 们是边不交的，如果它们没有公共边。它们的并g 1ug 2 是指这样个图：其点集 为矿( g 1 ) u 矿( g 2 ) ，边集为e ( g i ) u e ( g 2 ) 。类似地定义它们的交g 1 n g 2 。当它们 不交时，其并又写作g l + g 2 。同一个图g 的个不同的拷贝的不交并写作k g 。 1 1 3 图类 具有某种共同性质的图在一起形成图类。 如果g 的任意两点都相邻，称它是完全图，又叫做团。阶为n 的完全图记成 。显然，g 是完全图当且仅当d ( g ) = 1 。说图g ，日互补，如果它们具有 相同的点集、边集不交且其并为完全图。完全图的补图叫做空图。用e 。表示n 阶 空图。设as 矿，如果g a 】是空图，称a 是g 的一个独立集。设s e ，如果 g s 】= s i k 2 ，称s 是g 的一个边独立集，简称匹配。 设r 是一个不小于2 的正整数。如果g 的点集y 可剖分成r 个两两不交的非 空子集h ，w ，使得g 陬】，i = 1 ，r ，均是空图，则称g 为r 部图。这时， 称k 为g 的一个色类。若属于不同色