（运筹学与控制论专业论文）拟阵圈图的一些性质.pdf

l i p 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 查聋 e t 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校 保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保 存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：奎聋导师签名： 目录 中文摘要1 一 英文摘要l v 一 符号说明i x 第一章绪论1 1 1 拟阵基图6 1 2 树图及其它图8 1 3 拟阵基关联图1 0 1 4 与拟阵相关的图的染色数1 1 第二章拟阵圈图的连通度1 3 2 1 简介1 3 2 2 预备知识1 8 2 3 拟阵圈图的连通度与最小度1 9 2 4 拟阵圈图的边连通度2 5 第三章拟阵圈图中的圈2 9 3 1 简介2 9 3 2 预备知识3 1 3 3 拟阵圈图的边泛圈性3 2 3 4 拟阵圈图中的哈密顿圈3 6 山东大学博士学位论文 拟阵圈图的一些性质 李萍 ( 山东大学数学学院，济南2 5 0 1 0 0 ) ( 指导教师：刘桂真教授赖虹建教授) 中文摘要 图论和拟阵理论在二十世纪经历了空前的发展图的支撑树及拟阵的基 都是组合理论的基本研究对象一个连通图的树图能够反映该图的不同支撑 树之间的变换关系因此，研究一个图的树图有助于我们更好地了解该图的 性质同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系因 此，研究一个拟阵的基图有助于我们更好地了解该拟阵的性质近些年来，树 图和拟阵的基图被推广得到了一些新的图为了研究拟阵中圈图的性质，我 们提出了拟阵圈图的概念，并且研究了圈图的连通度，圈图中圈的性质，路 的性质，并且把圈图的概念推广为n 阶圈图，并得到了咒阶圈图的一些性质。 设e 是一个有限集如果s l ，s 2 e ，那么s l s 2 = x l x s l 和x 岳s 2 一个拟阵肘就是一个有限集e 以及e 的一个非空子集族够，且满足以下 条件： ( c 1 ) 若c l ，c 2 汐且c l c 2 ，则c 1 = q ( c 2 ) 设c l ，c 2 够并且a ，b e 若a c lnc 2 且b c l g ，则存在c 3 够 满足b c 3 ( c luc 2 ) 一f 口1 当c 汐( 加，我们称c 为肘的一个圈如果m 的一个圈只有一个元素，则 称之为m 的一个环如果两个元素的集合 工，y l 是m 的一个圈，则称 工，y ) 为一 对平行元如果m 既没有环也没有平行元，则称m 是一个简单拟阵如果一个 元素含在肘的任一基中，则称之为肘的一个反环 如果s 是e 的一个子集，且对任意的圈c ，都有c s 或者c e s 则称s 为m 的一个分离集显然e 和0 都是m 的分离集肘的极小分离集称为m 一个 分支如果拟阵肘只有一个分支，则称肘为连通拟阵设e e ，则m e 和m e 分别表示由拟阵m 经过收缩和删除p 后所得到的拟阵 够( 加在c k ( 加中相邻当且仅当在肘中i cnc i k 为了符号表示方便，我们 既用c 表示g ( 加的顶点，也用c 表示肘中的圈 本文分为五章第一章给出关于树图，拟阵基图以及森林图的一个简短 但相对完整的综述第二章给出拟阵圈图的概念，并讨论拟阵圈图的连通度 和边连通度第三章我们深入讨论了拟阵圈图的哈密顿性，边泛圈性以及圈 图中顶点不交圈的性质第四章讨论了拟阵圈图中路的性质第五章我们给 出了拟阵的圈图的定义，并讨论了它的直径和连通度 下面列出本文的主要结果 结论1 设g = g ( 加是一个连通拟阵肘的圈图，而且召是肘的一个基， 则g 的连通度k ( g ) 2 1 e b l 一2 山东大学博士学位论文 结论2 设g = g ( 加是一个连通拟阵m 的圈图，而且g 的最小度是6 ( g ) ， 贝u a ( g ) 2 1 e b i 一2 结论3 设g = g ( 蚴是一个连通拟阵m 的圈图，而且g 的最小度是6 ( g ) ， , $ j j g 的边连通度( g ) = 6 ( g ) 结论4 设g = g ( 加是一个连通拟阵m 的圈图，而且m 含有至少三个圈， 则g = g ( 加是边泛圈的 结论5 设g = g ( 加是一个连通拟阵m 的圈图，而且m 含有至少四个圈， 则g 是一致哈密顿的 结论6 设g = g ( 加是一个连通拟阵m 的圈图， 果i v ( g ) i = n 并且七l + 恕+ + = 刀( k i 为整数，岛3 ，i = 1 ，2 ，p ) ，则g 有一个2 因子f 包含p 个 顶点不交的n d i ，d e ，砩而且圈协的长度为岛o = 1 ，2 ，p ) 结论7 设g = o ( t v l ) 是一个连通拟阵m 的圈图，而且肘含有至少三个圈， 则g 的直径不超过2 并且，d ( g ( 加) = 2 当且仅当m 中有两个没有公共元素的 圈 结论8 设g = g ( 加是一个连通拟阵m 的圈图， 果i v ( g ) i = 咒并且c l ，岛 y ( g ) ，则对于任意的七满足2 k n 一1 ，存在一条长度为忌的路连接c l 和c 2 结论9 设肘是一个连通简单拟阵则如下结论成立 ( i ) c 2 ( m ) 是连通的 ( i i ) 如果肘没有一个约束子拟阵同构于妮6 则在c 2 ( m ) 中任何两个不相邻的 顶点c l 和c 2 有一个公共邻点g ( i i i ) q ( 加的直径不超过2 当且仅当对于任何边集合x e ，肘在x 上的约束子 拟阵都不同构于观6 结论1 0 设肘是一个包含至少两个圈的连通简单拟阵，且肘不是一条线， 则c 2 ( m ) 是2 一连通的 山东大学博士学位论文 关键词：拟阵；拟阵圈图；拟阵k 阶圈图；一致哈密顿性；边泛圈性 山东大学博士学位论文 s o m e p r o p e r t i e so fc i r c u i tg r a p h s o fm a t r o i d s l ip i n g ( s c h o o lo fm a t h ，s h a n d o n gu n i v ，j i n a n2 5 0 10 0 ) a b s t r a c t m a t r o i dt h e o r yd a t e sf r o mt h e19 3 0 sa n dw h i t n e yi nh i sb a s i cp a p e r 【6 9 】c o n - c e i v e dam a t r o i da sa l la b s t r a c tg e n e r a l i z a t i o no fam a t r i x m a t r o i dt h e o r yg i v e su s p o w e r f u lt e c h n i q u e sf o ru n d e r s t a n d i n gc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sa n d f o rd e s i g n i n gp o l y n o m i a l t i m ea l g o r i t h m s g r a p ht h e o r ya n dm a t r o i dt h e o r yh a v ew i m e s s e d a l lu n p r e c e d e n t e dg r o w t hi nt h et w e n t i e t hc e n t u r y s p a n n i n gf l e e so fg r a p h sa n db a s e s o fm a t r o i d sa r eb a s i co b j e c t si nc o m b i n a t o r i a lt h e o r y t h et r e eg r a p ho fac o n n e c t e d g r a p hc a nr e f l e c tt h ee x c h a n g i n gr e l a t i o n s h i po fd i f f e r e n ts p a n n i n gt r e e s ，s os t u d i n gt r e e g r a p h si su s e f u lf o ru st ol e a r nm o r ea b o u tt h ep r o p e r t i e so fag r a p h s i m i l a r l y , t h eb a s e g r a p ho fa m a t r o i dc a nr e f l e c tt h ee x c h a n g i n gr e l a t i o n s h i po fd i f f e r e n tb a s e s ，s os t u d i n g b a s eg r a p h si su s e f u lf o ru st ol e a r nm o r ea b o u tt h ep r o p e r t i e so fam a t r o i d i nr e c e n t y e a r s ，m a n yv a r i a t i o n so ft r e eg r a p ha n d b a s eg r a p ha r ei n t r o d u c e d i no r d e rt os t u d yt h e p r o p e r t i e so fc i r c u i t so fm a t r o i d s ，w eg i v ean e w d e f i n i t i o na sc i r c u i tg r a p ho fm a t r o i d ， a n dg i v es o m ep r o p e r t i e so ft h i sg r a p h l e t e b e a f i n i t es e t o f e l e m e n t s f o r s l ，s 2 e ，s e t s i - $ 2 = x l x s i a n d x 仨s 2 l e t 够b eac o l l e c t i o no fn o n - n u l ls u b s e t so few h i c hs a t i s f i e st h ef o l l o w i n gt w oa x i o m s ： ( c 1 ) ap r o p e rs u b s e to fam e m b e ro f 够i sn o tam e m b e ro f 够 ( c 2 ) i fa c lnc 2a n db c 1 一c 2w h e r ec 1 ，c 2 够a n da ，b e ，t h e nt h e r e e x i s t sac 3 够s u c ht h a tb c 3 ( c 1uc 2 ) 一( 口) t h e nm = ( e ，够) i sc a l l e dam a t r o i do ne w er e f e rt ot h em e m b e r so f 够a s c i r c u i t so fm a t r o i dm t h ef a m i l yo fc i r c u i t so fm d e t e r m i n e sam a t r o i d as u b s e to fet h a td o e sn o tc o n t a i na n yc i r c u i ti sc a l l e da ni n d e p e n d e n ts e to fm am a x i m a li n d e p e n d e n ts e ti sc a h e dab a s i so fm ，d e n o t e db y 烈 d l e t 留( dd e n o t e t h ef a m i l yo fb a s e so fm t h e ni ts a t i s f i e st h ef o l l o w i n gt w oa x i o m s ： v i fx = 忙 ，w eu s em ea n dm et od e n o t et h em a t r o i do b r a i n e df r o mm b yd e l e t - i n ga n dc o n t r a c t i n ge ，r e s p e c t i v e l y am a t r o i do b t a i n e df r o mmb yl i m i t e dt i m e so f c o n t r a c t i o n sa n dl i m i t e dt i m e so fd e l e t i o n si sc a l l e dam i n o rm a t r o i do f 膨 as u b s e tso fei sc a l l e das e p a r a t o ro fmi fe v e r yc i r c u i to fmi se i t h e rc o n t a i n e d i nso re s u n i o na n di n t e r s e c t i o no ft w os e p a r a t o r so fmi sa l s oas e p a r a t o ro fm i f 妒a n de a r et h eo n l ys e p a r a t o r so fm ，t h e nmi ss a i dt ob ec o n n e c t e d t h em i n i m a l n o n - e m p t ys e p a r a t o r so fm a r ec a l l e dt h ec o m p o n e n t so fm i fac i r c u i to fmh a so n l yo n ee l e m e n t , t h e nw ec a l lt h i sc i r c u i tal o o po fm i fa s e to ft w oe l e m e n t s x ，y i sac i r c u i to fm ，t h e nw ec a l lt h es e t 工，y la p a i ro fp a r a l l e l e l e m e n t s ，xa n dya r ep a r a l l e lt oe a c ho t h e r am a t r o i di ss i m p l ei fi th a sn o2 - c i r c u i t s a n dl o o p s w es a yt h a tei sac o l o o pi fi ti sn o tc o n t a i n e di na n yc i r c u i to fm ac o l o o p i sac o m p o n e n to f m l e tmb eam a t r o i da n dl e t 痨d e n o t et h ef a m i l yo fb a s e so fm l e t 劈d e n o t e t h ef a m i l yo fc o m p l e m e n t so fm e m b e r so f 留i ne t h e n 历i st h ef a m i l yo fb a s e so f am a t r o i d ，d e n o t e db ym 。，c a l l e dt h ed u a lo fm t h ec i r c u i t so fm a r ec a l l e dt h ec o - c i r c u i t so f m 留( m p ) = b i b 历( d ，e 岳b la n do 够( m e ) = b 一 e i b 留( d ，e 研 aw a l ki na g r a p hg i sa na l t e r n a t i n gs e q u e n c eo fv e r t i c e sa n de d g e s p = v 0 ，e o ，1 ，l ，e l ，魄，以，仇+ 1 s u c ht h a te ii sa ne d g ej o i n i n gv ia n dv “卜f o rs i m p l i c i t y , p = v o p l + 1w i l lb ew r i t t e n 山东大学博士学位论文 t h e r e b yi m p l y i n gt h eo c c u r r e n c e so ft h ee d g e s i fq = v t + l + 2 v ni saw a l k , t h e n p + q = v o v i v k v k + i v k + 2 v 一 p = v 0 ，e 0 ，v l ，e l ，垓，+ ii saw a l ki nw h i c ha l lt h ev e r t i c e sa r ed i s t i n c t ，t h e np i sc a l l e dap a t h i fv o ，v l ，垓+ 1a r ed i s t i n c ta n dv 0 = l t h e npi sc a l l e dac y c l e ，n l e l e n g t ho fa w a l ki st h en u m b e ro f e d g e sc o n t a i n e di nt h es e q u e n c e a f a m i l yo fp a t h si ng i ss a i dt ob ei n t e r n a l l y d i s j o i n ti fn ov e r t e xo fg i sa n i n t e m a l v e r t e xo fm o r et h a no n ep a t ho ft h ef a m i l y av e r t e xc u to fgi sas u b s e t o fvs u c ht h a tg v i sd i s c o n n e c t e d ak - v e r t e x c u ti sav e r t e xc u to fke l e m e n t s ，n l eo n l yg r a p h sw h i c hd on o th a v ev e r t e xc u t sa r e t h o s et h a tc o n t a i nc o m p l e t eg r a p h sa ss p a n n i n gs u b g r a p h s i fgh a sa tl e a s to n ep a i ro f d i s t i n c tn o n a d j a c e n tv e r t i c e s ，t h ec o n n e c t i v i t yk ( g ) o fgi st h em i n i m u mkf o rw h i c hg h a sak - v e r t e xc u t ；o t h e r w i s e ，w ed e f i n ek ( g ) t ob ely ( g ) l 一1 w ec a l la g r a p hw i t hj u s t o n ev e r t e xt r i v i a la n da l lo t h e rg r a p h sn o n t r i v i a l t h u s 足( g ) = 0i fgi se i t h e rt r i v i a lo r d i s c o n n e c t e d gi ss a i dt ob ek - c o n n e c t e di f 足( g ) k a l ln o n t r i v i a lc o n n e c t e dg r a p h s a r e1 - c o n n e c t e d f o rs u b s e t ssa n ds o fy ( g ) ，w ed e n o t eb y 【s ，s 】t h es e to fe d g e sw i t ho n ee n d i nsa n dt h eo t h e ri ns a ne d g ec u to f gi sas u b s e to f e ( g ) o f t h ef o r m 【s ，s 】，w h e r e si san o n e m p t yp r o p e rs u b s e to fy ( g ) a n ds = v s a k - e d g ec u ti sa l le d g ec u to f ke l e m e n t s i fgi sn o n t r i v i a la n de i sa ne d g ec u to fg 、t h e ng e ti sd i s c o n n e c t e d w et h e nd e f i n et h ee d g ec o n n e c t i v i t y ( g ) o fgt ob et h em i n i m u mkf o rw h i c hgh a sa k - e d g ec u t g i ss a i dt ob ek - e d g e - c o n n e c t e di fx ( g ) k l e tgb eag r a p h t h en o t a t i o nv ( g ) a n de ( g ) w i l lb eu s e df o rt h ev e r t e x - s e ta n d e d g e s e to fg ，r e s p e c t i v e l y ap a t ht h a tc o n t a i n se v e r yv e r t e xo fg i sc a l l e dah a m i l t o n p a t ho fg ；s i m i l a r l y , ah a m i l t o nc y c l eo fg i sac y c l et h a tc o n t a i n se v e r yv e r t e xo fg a g r a p hi sh a m i l t o n i a ni fi tc o n t a i n sah a m i l t o nc y c l e ag r a p hg i sc a l l e dh a m i l t o n c o n n e c t e di fe v e r yt w ov e r t i c e so fga r ec o n n e c t e db yah a m i l t o np a t h w en o wc a l la g r a p hgp o s i t i v e l yh a m i l t o n ，w r i t t e ng 矿，i fe v e r ye d g eo fg i si ns o m eh a m i l t o n c y c l e ；gi sn e g a t i v e l yh a m i l t o n ，w r i t t e ng 矿，i ff o re a c he d g eo fgt h e r ei sah a m i l t o n c y c l ea v o i d i n gi t w h e ng h + a n dg 旷，w es a yt h a tg i su n i f o n n l yh a m i l t o n a g r a p hg i sa l s oc a l l e de d g e - h a m i l t o n i a ni fgi sp o s i t i v e l yh a m i l t o n a g r a p hg w i t hnv e r t i c e si sc a l l e dv e r t e x p a n c y c l i ci ff o ra n yi n t e g e rk ，3 k n ， v n c o n c l u s i o ni s u p p o s et h a tg = g ( 加话t h ec i r c u i tg r a p ho fac o n n e c t e dm a t r o i d m t h e nt h ec o n n e c t i v i t y k ( g ) 2 1 e 一矧一2 w h e r ebi sab a s eo f m c o n c l u s i o n2 s u p p o s et h a tg = g ( 加i st h ec i r c u i tg r a p ho f ac o n n e c t e dm a t r o i dm w i t hm i n i m u md e g r e e6 ( g ) t h e n6 ( g ) 2 1 e b l 一2 c o n c l u s i o n3 s u p p o s et h a tg = g ( 加i st h ec i r c u i tg r a p ho f ac o n n e c t e dm a t r o i dm w i t hm i n i m u md e g r e e6 ( g ) t h e nt h ee d g ec o n n e c t i v i t y ( g ) = 6 ( g ) c o n c l u s i o n4 f o ra n yc o n n e c t e dm a t r o i dm = ( e ，dw h i c hh a sa tl e a s tt h r e ec i r c u i t s , t h ec i r c u i tg r a p hg = g ( 加西e d g e - p a n c y c l i c 一 山东大学博士学位论文 c o n c l u s i o n5 f o ra n yc o n n e c t e dm a t r o i dm 舭c i r c u i t g r a p hg ( 加i su n i f o r m l y h a m i l t o nw h e n e v e rg ( 1 v oc o n t a i n sa tl e a s t f o u rv e r t i c e s c o n c l u s i o n6 l e tgb et h ec i r c u i tg r a p ho fac o n n e c t e dm a t r o i dm = 但，d t f i v ( g ) i = na n dk l + 如+ + = nw h e r e 岛i sa ni n t e g e ra n d 岛3 ，i = 1 ，2 ，力 t h e ngh a sa 2 0 f a c t o rfc o n t a i n i n gpv e r t e x d i s j o i n tc y c l e sd i ，d 2 ，啡s u c ht h a tt h e l e n g t ho f d ii s 岛“= 1 ，2 ，p ) c o n c l u s i o n7 l e tm = ( e ，够) b eac o n n e c t e dm a t r o i dw i t ha tl e a s tt h r e ec i r c u i t s t f g = g ( 加i st h ec i r c u i tg r a p ho f mt h e nt h ed i a m e t e ro f gi sa tm o s t2f u r t h e r m o r e , 政g ( d ) = 2i fa n do n l yi ft h e r ee x i s tt w oc i r c u i t ss u c ht h a tt h e yh a v en oe l e m e n t 切 c o m m o n c o n c l u s i o n8 l e tg = g ( 加b et h ec i r c u i tg r a p ho f ac o n n e c t e dm a t r o i dm = ( e ，叻 f i v ( g ) l = na n dc i ，c 2 g ) ，t h e nt h e r e 妇ap a t ho f l e n g t hk j o i n i n gc la n dc 2 f o r a n y k s a t i s f y i n g2 k n 一1 c o n c l u s i o n9 l e tmb eac o n n e c t e ds i m p l em a t r o i d e a c ho f t h e f o l l o w i n gh o l d s i i ) c 2 ( m ) i sc o n n e c t e & l m l fm h a sn or e s t h c f i o ni s o m o r p h i ct ou 2 ，6 t h e ne v e r y p a i ro f n o n a d j a c e n tv e r t i c e sc l a n dc 2i nc 2 ( m ) h a sac o m m o n n e i g h b o rc 3 ( i i i ) t h ed i a m e t e ro fc r m ) i sa tm o s tt w oi f a n do n l yi f f o ra n yx et h er e s t r i c t i o no f mt oxi sn o ti s o m o r p h i ct ou 2 。6 c o n c l u s i o n1 0 l e tmb eac o n n e c t e ds i m p 跆m a t r o i dw i t hm o r et h a no n ec i r c u i t , b u t mi sn o ta l i n e , t h e nc 2 ( m ) 括2 一c o n n e c t e d k e y w o r d s ：m a t r o i d ；c i r c u i tg r a p ho fam a t r o i d ；k t ho r d e rc i r c u i tg r a p ho fa m a t r o i d ；u n i f o r m l yh a m i l t o n i a n ；e d g e p a n c y c l i c i x 论文 ( g ) n d s ) g 【s 】 c g 的最大度 g 中集合s 的邻点集 由s 导出的g 的子图 圈 x 山东大学博士学位论文 z ( g ) x ( g ) 鼻( g ) ( g ) d ( g ) e ( 加 g ( 加 q ( 加 g 的色数 g 的边色数 g 的连通度 g 的边连通度 g 的直径 肘的元素集合 肘的圈图 肘的k 阶圈图 第一章绪论 二十世纪三十年代，w h i m e y 在他的论文【6 9 】中，作为对矩阵的抽象概 括，首次提出了拟阵的概念拟阵论为组合优化问题和设计多项式算法提供 了强有力的工具图论和拟阵理论在二十世纪经历了空前的发展图的支撑 树及拟阵的基都是组合理论的基本研究对象一个连通图的树图能够反映该 图的不同支撑树之间的变换关系因此，研究一个图的树图有助于我们更好 地了解该图的性质同样的一个拟阵的基图能够反映该拟阵的不同基之间 的变换关系因此，研究一个拟阵的基图有助于我们更好地了解该拟阵的性 质近些年来，树图和拟阵的基图被推广得到了一些新的图在这一章里我 们主要对拟阵基图、拟阵的基关联图、邻接叶边交换森林图以及图的分数 荫度等结果进行总结本章分为五个部分第一部分给出基本概念，而一些基 本结果将在第二、三、四、五部分分别给出。 1 1基本定义和符号 设e 是一个有限集如果s l ，s 2 e 那么s l s 2 = x l x s l 且x 名s 2 1 一个拟阵m 就是一个有限集e 以及e 的一个非空子集族够，且满足以下 条件： ( c 1 ) 若c l ，q 够且c l 互c 2 ，则c l = c 2 ( c 2 ) 设c l c 2 够并且a ，b e 若a c lnc 2 且b c l c 2 ，则存在c a 够 满足b c 3 ( c lt jc 2 ) 一亿1 当ce 够( 加，我们称c 为肘的一个圈 e 的任何不含圈的子集称为m 的独立集一个极大独立集称为m 的基，记 作召( 蚴记留( 加为肘中全体基的集合则留( 加有如下性质： ( b 1 ) 留( 加至少含有一个元素 ( b 2 ) 若b ，留( d ，且b b b 7 ，则必有b 一b 使得b u l b ! 一 6 留( d 设m = 但，够) 是一个拟阵如果x e ，则可以得到一个在e x 上的拟 阵，它的圈是包含在e x 中的肘的圈，称为肘在e x 上的限制，记作m x 或 者m i ( e 一面 山东大学博士学位论文 除此之外，还有另一类重要的衍生拟阵一收缩拟阵若x e 则m 到e x 的 ( 或者将x 从m 中收缩后得到的拟阵) 的圈集合是肘中的圈与e x 的极 空交集的集合，我们将这个拟阵记为m x 若x = e l ，我们用m e 和m e 分别表示从肘中删除e 和收缩e 得到的拟阵拟 幼阵就是拟阵通过限制或收缩运算得到的拟阵 如果s 是e 的一个子集，且对任意的圈c ，都有c s 或者c e s 则称s 的一个分离集显然e 和0 都是m 的分离集m 的极小分离集称为肘一个 如果拟阵m 只有一个分支，则称肘为连通拟阵 如果肘的一个圈只有一个元素，则称之为m 的一个环如果两个元素的 集合i x , y 是肘的一个圈，则称i x ，y 为一对平行元如果肘既没有环也没有平 行元，则称m 是一个简单拟阵如果一个元素含在m 的任一基中，则称之为m 的一个反环一个反环是m 的一个分支 设m 是一个拟阵并且令留表示m 的基集合令纱表示历中的元素在e 中的 补集的集合贝0 勿是一个拟阵的基集合，我们称这个拟阵为肘的对偶，记作m m 中的圈叫做m 的反圈我们有留( m p ) = 矧曰留( l d ，e 岳b 并且留( l 纠p ) = b f e l b 留( 加，e 口 一个没有环及反环的拟阵称为真拟阵。设肘是关于的拟阵，肘的环及反 环的集合为r 显然拟阵m i ( e t ) 是一个真拟阵，称它为m 的简化。设m 和m 是 两个非平凡的拟阵。设叁l 尬是m 的简化的直和分解，其中每个舰是连通的。 如果存在m 7 的简化的直和分解冬1 哗使蟛是连通的且适当的安排哗的次序 有尬同构于肘；或( 蟛) 贝0 称m 与肘是等价的 本文所考虑的图均为简单无向图g ，并记其顶点集合为y ( g ) ，边集合为e ( g ) 设x 是一个实数，记m 是不小于x 的最小整数，l 州是不大于x 的最大整数，如 果s 是一个集合，我们用i s i 记s 的基数，即s 中元素的个数图g 中顶点1 ，的度 就是g 中与1 ，关联的边的数目，记作如( v ) 我们分别用6 ( g ) = n f m l c l g ( ，) ：1 ， y ( g ) 和( g ) = m a x l d g ( v ) ：1 ，y ( g ) 来记g 的最小度和g 的最大度对g 中的任 意顶点集s ，我们称与s 中顶点邻接的所有顶点的集合为s 在g 中的邻点集，记 作g 哂) 我们把顶点1 ，在g 中的邻点集简记作n d v ) 如果没有混乱，我们分别 用y ，e ，政“) ，6 ，( 1 ，) 代替y ( g ) ，e ( g ) ，如( “) ，6 ( g ) ，( g ) ，n d v ) 图g 的一个支撑子图是满足y ( 1 - 1 3 = y ( g ) 的一个子图日对一个顶点集矿 g ) ，我们用g 【矿】来记g 的由矿导出的那个子图，即顶点集为矿且边集为l u v e ( g ) ：u ，1 ，v l 的g 的那个子图我们称g v 】是g 的一个导出子图导出子 2 山东大学博士学位论文 图g v 】简记作g 一矿( 如果矿= ， ，则简记作g 一力对一个边集e 7 e ( g ) ， 我们用g f 】来记g 的由f 导出的那个子图，即顶点集为 “，以g ) ：比1 ，e 且 边集为的g 的那个子图我们称g e 7 】是g 的一个边导出子图我们用g f 来 记g 的边集为e 的那个支撑子图，即通过删除e 中的那些边所得到的g 的 那个子图类似地，我们用g + e 7 来记把f 中的边添加n g 中所获得的那个图 如果e ，- e l ，我们将g 一和g + e 1 分别简记为g 一已和g + e 图g 的一条路径是一个非空序列w = v o e l v l e 2 v 2 e k v k ，满足在序列中点 边交替出现并且对1 fsk ，边e f 的两个端点分别是1 ，扣1 和如果在w 中， 边e l ，e 2 ，e k 互不相同，则称w 是一条迹，如果中点，1 ，l ，h 互不相同，则称 是一条路，如果v o = v k 并且，l ，圪，h 互不相同，则称是一个圈，此时整数k 称 为圈的长度长度为k 的圈称为“圈，图g 围长，用g ( g ) 表示，是g 中最小圈的长度 g 的路的集合被称为内部不相交的，如果g 的任意顶点都最多只是这个 集合中一条路的内部顶点 如果g 一矿是不连通的，则y 的子集y 7 称为g 的顶点割集如果g 的一个 顶点割集有七个元素，我们称它为b 顶点割不含有顶点割集的图必然包含 一个为完全图作为支撑子图如果g 含有两个不相邻的顶点，那么g 的连通 度k ( g ) 是g 的最小项点割集的基数；否则，我们定义k ( g ) = i y ( g ) i 一1 因此，如 果g 不连通或者只含有一个顶点，k ( g ) = 0 如果, k g ) k ，g 被称为如连通的 对于g ) 的两个子集s 和s7 ，我们用【s ，s ，】表示一个端点在s 中，另一个端 点在s 中的边的集合如果s 是y ( g ) 的一个非空真子集并且可= y s ，e ( g ) 的 子集 s ，- g j 为g 的一个边割集一个“边割集是有k 个元素的边割集如果g 有至 少两个顶点并且f 是g 的一个边割集，n g e 是不连通的我们定义图g 的边 连通度( g ) 是g 的最小边割集的基数如果( g ) k ，g 被称为k 边连通的 设g 是一个