（计算机软件与理论专业论文）k可扩图和n因子临界图的等价及其性质.pdf

中文摘要 摘要 尼可扩图和佗因子临界图的等价及其性质 专业 博士生 导师 ：计算机软件与理论 ：张赞波 ：娄定俊 令g 为一连通图，其顶点个数为，整数0 七2 1 ，若g 有大小为的对 集，且g 的每一个大小为尼的对集都包含在g 的一个完美对集中，则称g 为七可扩的 若0 死一2 ，对于图g 的任意大小为佗的顶点子集s y ( g ) ，g s 均有完美对集， 则称图g 为扎因子临界的 本文主要研究忌可扩图和死因子临界图 我们注意到对集可扩理论与连通度理论之间有很多的相似的结论，这促使我们 研究忌可扩图和尼连通图之间的关系在本文第2 章中，我们独立地得到了南可扩二部图 和尼强连通有向图之间的等价关系利用这个等价关系，我们列举说明了对集可扩理论 和连通度理论的一系列相似结论，简化了尼可扩二部图一个结论的证明对于有完美对 集但非1 可扩的二部图我们证明了其基本分支与有向图的强连通分支对应从所得到 的等价关系，我们还证明了七可扩二部图，尼强连通有向图与组合矩阵的关系 忍可扩图和n 因子临界图是两个关系密切的概念因此有不少研究这两个图类 之间关系的工作由定义即可知一个2 南因子临界图总是尼可扩的但是反过来，尼可扩 图在何种条件下是2 七因子临界的，这是一个还没有研究清楚的问题f a v a r o n 和y u 在 这个问题上分别得到了一些结论l 0 u 和y u 证明了当七4 时，七可扩非二部图g 的 连通度圪2 尼这个连通度达到了2 忌因子临界图连通度的下界这启发我们研 究七，4 的庇可扩图和2 尼因子临界图的关系本文第3 章给出我们的研究结果，即 当忌( + 2 ) 4 时，尼可扩非二部图是2 南因子临界的我们还给出例子，说明这个下界 是最好可能的作为一个推广，我们还得到了( 2 忌+ 1 ) 因子临界图与后；可扩图之间的类 似关系对于惫= 4 的情况，我们也把后可扩图和2 因子临界图的关系研究清楚，给出 了一个尼可扩图是2 七因子临界图的充分必要条件 基于我们关于尼可扩图和n 因子临界图的等价性质的研究结果，我们可以从系统的 角度看待尼强连通图，可扩二部图，知可扩图和n 因子临界图，这将有利于我们今后研究 工作的开展 从第4 章起我们研究后可扩图和n 因子临界图的性质 中文摘要 第4 章把a n a c h u e n 和c a c c e t t a 的关于忌可扩图中独立数的一个结论推广到n 因子临 界图 在第5 章的研究工作中，我们试图证明七4 时，尼可扩图中有对集交错 的h a m i l t o n 圈我们的工作表明，对集交错的h a m i l t o n 圈的存在性可以由更弱的条 件得到我们证明了在具有完美对集m 的二部图g 中，当顶点最小度6 ，4 + 1 时， 图g 有m 交错的h a m i l t o n 圈在一般图中，当g 的连通度，c 2 时，除非g 属于一类例 外的图类，g 有m 交错的h a m i l t o n 圈由于例外图类不是尼可扩的，因此从我们的结论可 以推出当尼4 时，七可扩图中有对集交错的h a m i l t o n 圈本章中关于一般图的结论 证明有一定的难度，最终的结论具有与经典的h a m i l t o n 圈存在性条件类似的简洁形式 在第6 章中，我们首先研究了h a m r y 图及其变种的因子临界性和可扩性，其意义在 于这些图类包含了边数最少的尼可扩图和n 因子临界图我们发现现有文献所构造的边 数最少的危可扩图都是二部图，这促使我们研究具有最少边数的凫可扩非二部图本章 完全解决了南= l ，2 的情况 关键词：尼可扩图，佗因子临界图，后强连通有向图，m 交错路，m 交错圈 英文摘要 a b s t r a c t e q u i v a l e n c eb e 帆e e n 尼一e x t e n d a b l eg r a p h sa n d 佗一f h c t o r - c r i t i c a l g r a p h sa n dm e i rp r o p e r t i e s m 萄o r n a m e s u p e r v i s o r 1 t l e o r e t i c a lc o m p u t e rs c i e n c e z a n b oz h a n g d i n 百u nl 0 u l e tgb eac o n n e c t e dg r a p hw i t h 二，v e n i c e s ，o 忌二，2 一la ni n t e g e r ，i fgh a sa m a t c h i n go fs i z e 忌，a i l de v e 巧尼- m a t c l l i n go fg i sc o n t a i n e di nap e r f e c tm a t c m n go fg ，t h e n gi ss a i dt 0b e 忽一e x t e n d a b i e l e tgb eac o n n e c t e dg m p h 锄do n 一2a ni n t e g e r i ff o re v e o rs y ( g ) w i t hl s l = n ，g sh a sap e r f e c tm a t c h i n g ，t h e nw es a yt h a tgi s 佗f a c t o r c t i c a l w es t u d y 七一e ) 【t e n d a b l eg r a p h sa n dn f a c t o r c r i t i c a i 鲈a p h si nt h i st h e s i s n o t i c i n gt t l a tt h e r ea r eal o to fa n a l o g o u sr e s u l t si nm et i l e o 眄o fm a t c h i n ge ) ( t e n s i o n a i l dt l l et h e o 巧0 fc o f l i l e c 6 v i 饥w es t u d yt h er e l a t i o nb e 觚e e ne x t e n d i b i l i 够a j l dc o n n e c t i v - i 够h lc h 印t e r2 ，w ei n d e p e n d e n t l y0 b t a i nt h ee q u i v a l e n c eb e 帆e e n 忌一e x t e n d a b l eb i p a r t i t e 伊a p h sa n ds t r o n 孚y 忌- c o n n e c t e dd i g r a p h s w bt t i e ni i l u s 仃a t ea n de x p l a i ns o m ep a r a l l e lr e - s u l t sf o r 后- e x t e n d a b l eb i p a n i t eg r 印h sa n ds t r o n 百y 忌一c o n n e c t e dd i g r a p h s as i m p l ep r 0 0 f 0 fa ne x i s t i n gr e s u l to n e x t e n d a b l eb i p a n i t eg r a p h si s 西v e n f o r b i p a r t i t eg r a p h sw i mp e r - f e c tm a t c h i n g sb u tn o tl e x t e n d a b l e ，w ep r o v em a tt h e i re l e m e n t a 巧c o m p o n e n t sc o l l r e s p o n d t 0m es 缸o n gc o m p o n e n t so fd i 笋a p h s s 眦e df r o mm ee q u i v a l e n c er e l a t i o n s h i pw e0 b t a i n ， w ef i n dt h er e l a t i o na m o n g 七一e x t e n d a b l eb i p a r t i t e 孕印h s ，s 仃o n g l y 南c o n n e c t e dg r a p h s 锄d c o m b i n a t o r i a lm a t r i c e s t h ec o n c e p t so fe ) ( t e n d i b i l i t ) ，a n df a c t 0 卜c r i t i c a l i 够a r ec l o s e l yr e l a t e d h e n c et h e r eh a v e b e e nm a n yr e s e a r c ho nr e l a t i o nb e t 、v e e n 七一e ) ( t e n d a b l eg r a p h sa n d 扎一f a c t o r c r i t i c a lg r a p h s b y d e f i n i t i o n ，a2 七一f a c t o r c t i c a lg r a p hi s 鲥w a y s 尼e ) ( t e n d a b l e h o w e v e ci ti sn o tt h o r o u g h l y c l e a r 也a tu n d e rw h a tc o n d i t i o na 尼- e x t e n d a b l eg m p hi s2 尼一f a c t o f c r i t i c a l f a v a r o na n d j h a v eo b t a i n e ds o m er e s u l t s0 nt h i sp f o b l e 札l o ua n dy uh a v ep r 0 v e dt h a tw h e n 尼王，4 ， t l l ec o n n e c t i v 时o fa 忌一e x t e n d a b i en o n - b i p a r t i t eg r a p hgi sa ti e a s t2 尼s u c hav 2 l l u e0 f c o n n e c t i v i 够b e c o m e sc o m p 疵b l et ot h a to f2 忌一f a c t o 卜c r i 在c a lg r a p h s t h i sf a c th a si l l u m i n e d u st 0s t l l d yt i l er e l a t i o nb e t w e e n 庇- e x t e n d a b l e 伊a p h sa n d2 七一f a c t o 卜c r i t i c a l 鲈a p h sw h e n l n 英文摘要 尼4 i nc h a p t e r3 ，w es h o wo u rr e s u l tt h a tw h e n 尼( ，+ 2 ) 4 ，a 尼- e x t e n d a b i e n o n b i p a n i t eg r a p hi s2 惫一f a c t o 卜c n t i c a i w es h o wt h a tt h el o w e rb o u n do f 七i sb e s tp o s s i b i e b ye x a m p l e s as i m i i a rr e l a t i o nb e t w e e n 七 一e x t e n d a b l eg r a p h sa n d ( 2 尼+ 1 ) f a c t o r c r i t i c a l g r a p h si sa i s oo b t a i n e d m o v e o v e r ，f 0 r 尼= 4 ，w e6 n d a n e c e s s a d ra n ds u 币c i e n tc o n d i t i o n f o ra 七一e x t e n d a b l eg r a p ht ob e2 尼一f a c t o 卜c r i t i c a l b a s e do nt h ee q u i v a i e n tr e s u i t sw eo b t a i n e d ，w eh a v eas y s t e m a t i cv i e wo fs t r o n g l y 忌- c o n n e c t e dd i g r a p h s ，尼- e x t e n d a b l eb i p a r t i t eg r a p h s ，尼一e x t e n d a b l eg r a p h sa n d 佗- f 沁t o 卜c r i t i c a l g r 印h s ，f r o mw h i c ho u rf u t u r er e s e a r c hm a y b e n 醣t w es t u d ys o m ep r o p e r t i e so f 尼- e x t e n d a b l eg r a p h sa n dn f a c t o r c r i t i c a lg r a p h sf 幻m c h a p t e r4 i r ic h a p t e r4 ，w eg e n e r a l i z ear e s u l to fa n a c h u e na n dc a c c e t t ao ni n d e p e n d e n c en u m b e r i n 尼一e x t e n d a b l eg r a p h st oas i m i l a rr e s “tf o rn f a c t o r - c r i t i c a lg r a p h s h lc h a p t e r5 ，w ei n t e n dt 0p r o v et h a tw h e n 尼4 ，t h e r ei sa na 彳- a l t e m a t i n gh 锄i l t o n c y c l ei na 七一e x t e n d a b l eg r a p hgf o fe v e 眄p e 疏c tm a t c h i n gmo fg nt u m so u tt h a tt h e e x i s t e n c eo fs u c hac y c l ec a nb ee n s u r e db yw e a k e nc o n d i t i o n s f o rb i p a r t i t eg r a p h sw i t h ap e e c tm a t c h i n gm ，w ep r o v et h a tw h e nt i l em i n i m u md e g r e ej 4 + 1 ，gh a sa n m a l t e m a t i n gh a m i l t o nc y c l e f o rg e n e r a ig r a p h s 晰t hap e 彘c tm a t c h i n gm ，w ep r 0 v e t h a tw h e nt h ec o n n e c t i v i t y ，c 2 ，u n l e s sg b e i o n g st oo n ee x c e p t i o n a lc l a s so fg r a p h s ， gh a sa f lm - a l t e m a t i n gh a m i l t o nc y c l e s i n c et h ee x c e p t i o n a lg r a p h sa r en o t 七一e x t e n d a b l e ， w ec o n c l u d em a tw h e n 七4 ，t h e r ei sa nm a l t e m a t i n gh a m i l t o nc y c l ei na 七一e x t e n d a b l e g r a p hgf o re v e 叮p e 彘c tm a t c h i n gm o fg t h ep r o o f si nt h i sc h a p t e ra r ei n v o l v e d t h e m a i nr e s u l t sa r e0 fs i m p l ea n de l e g a n tf o r m ss i m i l a rt 0t h a to ft h ec l a s s i cr e s u l t so nt h e e x i s t e n c eo fh a m i l t o nc y c i e s i l lc h a p t e r6 ，w es t u d yt h ee x t e n d i b i l i 锣a n df a c t o f - c r i t i c a l i t ) ro fh a r a 呵伊a p h sa n d t h e i rv a r i a n t s i n c l u d e di nt h e ma r e 七一e x t e n d a b l eg r a p h sa n d 佗一f a c t o 卜c t i c a lg r a p h sw i t h m i n i m u mn u m b e ro fe ( 培e s w ef i n dt h a ta l i 七一e x t e n d a b l eg r a p h sw i t hm i n i m u mn u m b e r o fe d g e sc o n s t r u c t e da r eb i p a f t i t e h e n c e ，w ec o n s i d e rt h ep r o b l e mo ff i n d i n g 尼- e x t e n d a b i e n o n - b i p a r t i t eg r a p h sw i t hm i n i m u mn u m b e ro fe d g e s kt h i sc h a p t e r ，w es o l v em ep r o b l e m f o r 尼= 1 。2 k e yw o r d s ： 七一e x t e n d a b l eg r a p h ，佗- f 苟c t o r c f i t i c a lg r a p h ，s t r o n g i y 七一c o n n e c t e dd i g r a p h ， m - a l t e m a t i n gp a t h ，m - a l t e m a t i n gc y c l e 一一 主要概念中英文对照表 主要概念中英文对照表 下表各项依第一个字的次序排列，英文在前，中文在后，英文和中文分别按照英文 字母表次序和中文拼音次序排列若某项以代数符号开始则忽略代数符号，例如“七可 扩”，“s 片段”等则按照“可扩”，“片段”分别排在“k ，和”p ”内 c a r t e s i a n 积 c a n e s i a np 似l u c t h a m i i t o n 路 h a m i l t o np a t h h 锄i l t o n 圈h 锄i i t o nc v c l e 伴随有向图 a s s o c i a t e dd i g r a p h 饱和s a t u r a t e d 闭包c l o s u r e 边e d g e 并u n i o n 尼不可分七一i n d e c o m p o s a b l e 不可约i r r e d u c i b l e 昆不可约昆i 玎e d u c i b l e 部分可分p a n i a l l yd e c o m p o s a b l e 后部分可分p a r t i a l l y 尼一d e c o m p o s a b l e 长度l e n 舀h 出度o u t d e g r e e 出邻居o u t n e i g h b o r 单点 s i n 翻e t o n 单固定f i x e ds i n g l e 单向对o n e w a yp a i r 导出子图i n d u c e ds u b g r a p h 顶点v e 懈 顶点割 v e r t e xc u t 凫顶点割凫- v e n e xc u t 独立集 i n d e p e n d e n ts e t 独立数i n d e p e n d e n tn u m b e f 度d e g r e e 度序列d e 笋e es e q u e n c e 端点 e n d v e r t e x 对集m a t c h i n g 七对集 七- m a t c h i n g 对集子形m a t c h i n gm i n o r 对角线d i a g o n a l 耳朵分解 e a rd e c o m p o s i 在o n 二部耳朵分解b i p a r t i t ee a rd e c o m p o s m o n 二部图( 偶图) b i p a n i t eg r a p h 二分类 b i p a n i t i o n 反有向j 峦 a n t i d i r e c t e dt r a i l 分隔集s 印a r a t o r 封闭的m 交错路 c i o s e dm a l t e m a t i n g p a t h 孤立点 i s o l a t e dv e r t e x 固定f i x e d 合选e l i g i b l e 和j o i n 弧a u r c 基本e l e m e n t a 呵 基本分支e l e m e n t a l yc o m p o n e n t 奇分支 o d dc o m p o n e n t 极小七可扩m i n i m a l 七e x t e n d a b l e 极小昆强连通m i n i m a ls t r o n 酉y 尼c o n n e c t e d 极小死因子临界 m i n i m a l 礼一f a c t o r - c t i c a l 几乎完美对集n e a u rp e 彘c tm a t c h i n g 几乎无爪图 a l m o s td a w - f r e eg r a p h r 4 一 主要概念中英文对照表 m 交错路 m a l t e m a t i n gp a t h m 交错圈m a l t e m a t i n gc y c i e 紧割集分解t i g h t c u td e c o m p o s i t i o n 局部七连通l o c a l l y 七- i n n e c t e d 局部完全化l o c a l l yc o m p l e t i o n 距离d i s 啪c e 开放的m 交错路0 p e nm a l t e m a t i n gp a t h 尼可扩尼e x t e n d a b l e ( m ，n ) 可扩( m ，他) 嘞【t e n d a b l e 尼 可扩尼 - 镊t e n d a b l e 可约 r e d u c i b l e 七可约尼f e d u c i b l e m 可增广路m a u g m e n t i n gp a t h 尼控制南习o m i n a t i n g 控制集d o m i n a t i n gs e t 控制数d o m i n a t i n gn u m b e r 连通c o n n e c t e d 连通度c o n n e “v i t y 连通分支c o n n e c t e dc o m p o n e n t u 连续集矿c o n s e c u t i v es e t 。s 链 s 1 i n k 路p a t h s 片段 s s e g m e n t 强s t r o n g 强连通s t r o n g l yc o n n e c t e d 七强连通s t r o n 弭y 七一c o n n e c t e d 强连通分支s t l i o n gc o m p o n e n t 圈c y c l e 缺失d 对集d e f e c t dm a t c h i n g 缺失忌可扩d e f e c t 恐一e x t i e n d a b l e 入度 i n d e g r e e 入邻居i n n e i 曲b o r 生成子图s p a n n i n gs u b g r a p h 双固定f i x e dd o u b i e 双固定f i x e dd o u b l e 双因子临界b i c r i d c a l 头h e a d 图g r a p h ( n ，庇，d ) 图( n ，d ) - g r a p h 完美对集p e f f e c tm a t c h i n g 完全不可分t o t a l l yi n d e c o m p o s a b l e 完全二部图c o m p l e t eb i p a n i t eg r a p h 完全图c o m p l e t eg m p h 尾t a i l 无爪图c l a w - 融g r a p h 相关联弱s o c i a t e d 相邻a d j a c e n t 悬挂点h a n 百n gv e f c e x 因子临界f a c t o r - c r i t i c a l 礼因子临界 佗f a c t o 卜c d t i c a l 有向路径d i r e c t e dp a t h 有向圈d i r e c t e dc y c l e 有向图 d i g r a p h ，d i r e c t e dg r a p h 约化伴随二部图r e d u c e da s s o c i a t e d b i p a r t i t eg r a p h 约化邻接矩阵r e d u c e da d j a c e n tm a t r i x 正则r e g u i a r 支撑b 豫c e 主对角线m a i nd i a g o n a l 爪c l a w 砖块b r i c k 子图s u b g r a p h ( 爪的) 中心c e n t e r ( o f ac l a w ) 最大对集m a ) 【i m u mm a t c h i n g 一8 5 原创声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均己 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 作者签名： 佞穆【、扯 日期： 关于学位论文使用授权的说明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅，有 权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方法保 存学位论文。 作者签名： 张哩j k 日期：三! ：墨：三：望 导师签名： 日期：垫塑：壹：望= 第一章引言 第一章引言 图论是用图作为抽象模型来研究解决现实生活中各种问题的一个学科图论中的 一个图由一组对象的集合( 抽象为图的顶点) 和这个对象集合上的二元关系( 抽象为图 的边) 构成现实生活中的很多现象都可以用图来描述例如人群的集合和人与人的朋 友或夫妻关系，城市集合和城市间连接的公路，等等图论起源于2 0 0 多年前瑞士数学 家e u l e r 对k 6 n i g s b e r g 市中七座桥梁的遍历问题的研究而近年来信息科学的蓬勃发展 为图论注入了新的活力和内容其他学科如生物，化学等也大有图论的用武之地此 外，处理现实生活的一些新涌现的问题，如交通网络流量，人际关系网络，疾病传播模 型等，也需要图论这个工具因此，图论学科越来越受到重视，得到了很大的发展 对集理论是图论的一个重要分支由于其简单性和普遍性，现实生活中的很多问 题都可以归结为对集问题例如工作分配，任务日程安排等同时，对集问题与图论的 其他分支联系紧密，某些对集问题的解决可以导致图论其他问题的解决因此对集作 为图论研究的一个热点和前沿而深受关注 由于对集的应用广泛，解决实际问题经常需要计算一个图的完美对集的个数例 如，化学家们发现某些化学成分的稳定性与其分子结构所对应的图的完美对集个数相 关某些磁性物质状态的确定也可以通过求平面图的完美对集个数而解决计算任意 一个图的完美对集个数是一个n p 难题( v a l i a n t ，【6 6 】) 因此研究怎样的图可以在多项式 时间内求解完美对集的个数就成为一个研究课题 要计算一个图的完美对集的个数，它的不含于任何完美对集的边可以忽略，因 此我们可以只考虑所有的边都含于完美对集中的图，这种图也就是l 可扩图l o v a s z ( 【4 2 】) 提出了紧割集分解，将l 可扩图唯一地分解成若干砖块，即3 连通2 因子临界图， 和支撑，即2 可扩二部图k a s t e l e y n ( 2 7 】， 2 8 】) 已经证明了如果可以给一个无向图g 的 边定向获得g 的一个p f 狮a n 定向，则g 的对集个数可以在多项式时间内求得而 由v 掘m i 和y n n a k a i ( i s ( 6 7 】) 得到的下述定理奠定了砖块和支撑的重要地位 定理1 o 1 ：任意图g 具有p 觚a n 定向当且仅当它的砖块和支撑有p f 擒a n 定向 从上面的介绍我们可以看到，寻找可以多项式时间求解完美对集个数的图的问题 最终归结到砖块和支撑的结构研究p l u m m e r ( 5 0 】) 发现了以下两个关系 ( 1 ) 一个2 可扩图或为砖块或为支撑 ( 2 ) 一个( 七+ 1 ) 可扩图必为忌可扩 于是为了促进对砖块和支撑的深入研究，p l u m m e r 在 5 0 】中提出了南可扩图的概念 后来y u 和f a v a r o n 对因子临界性也作了类似的推广，分别独立地提出了n 因子临界图的 概念( 7 6 】， 1 6 】) 这两个概念被提出以后，受到了很多学者的关注，涌现出大量的研究 文献研究的方向主要集中在：( 1 ) 寻找属于这两个图类的图；( 2 ) 对这两类图作刻画，特 一l 一 第一章引言 别是寻找一个图是七可扩图或n 因子临界图的充分必要条件：( 3 ) 研究可扩性，因子临界 性与图的其他参数，例如顶点度数，连通度等之间的关系；( 4 ) 研究极大或极小后可扩图 和n 因子临界图的性质；( 5 ) 研究这两类图的一些变种或推广等 近年来，对于砖块和支撑的结构研究取得了很大的进展( 参见本章研究现状介绍) ， 可以说促伽l u m m e r 提出尼可扩图概念的原始问题己经近乎解决但是，经过众多学者 长时间对后可扩图和佗因子临界图性质的挖掘，它们呈现出了更广泛的理论意义和应用 前景因此，对这两个图类的研究方兴未艾 本文研究了可扩性与强连通性，因子临界性之间的等价关系，因子临界性与图的 独立数之间的关系，忌可扩图中存在m 交错h a m i l t o n 路径与m 交错h a m i l t o n 圈的充分条 件，以及具有最小边数的尼可扩图等 在本章中，我们在第1 1 节定义本书用到的基本概念和记号，第1 2 节列出对集理论 的几个基础性的定理，第1 3 节对我们关心的部分研究进展作一个总结，并在第1 4 节简 略介绍后面各章节的内容 1 1 基本概念和记号 本节列出本文所涉及的图论特别是对集理论的若干基本概念而下文将出现的其 它相关的概念将在它们所出现的章节里作说明 一个图是一个有序的对g = ( ve ) ，满足e y y 通常我们假定yne = d y 的元素称为图g 的顶点，e 的元素称为图g 的边通常，我们使用符号y ( g ) 来代表图 的顶点的集合，而使用e ( g ) 来代表图的边的集合并且，记i g i = = ( g ) = i y ( g ) l 以 及= g ( g ) = l e ( g ) 1 若另有g ，= ( y 7 ，e 7 ) 使得y 7 y 以及e 7 e ，则称g 7 是g 的 子图g 的生成子图是指满足y ( 日) = y ( g ) 的子图日令非空集合y ，y ( g ) ，g 的 由y 7 导出的子图是以y 7 为顶点集，以g 中所有两端点都在中的边构成的集合为边集 的图我们以g f y 7 1 表示g 的由y 7 导出的子图，并以g y 7 表示子图g y ( g ) y ，1 所谓 的二部图( 或偶图) 是指一个这样的图，其顶点集可以分解为两个子集x 和y ，使得任何 一条边都有一个端点在x 中，另一个端点在y 中；这样一种分类( x ，y ) 称为图的一个二 分类称e = y y 的图为完全图，含有n 个顶点的完全图记为k 由n 个互不相邻的 点构成的图记为厶若二部图g 的两个分部为x 和y ，任意两个顶点z x 和剪y 之间 都有边相连，则称g 为完全二部图，记i x l = m ，l y l = 几的完全二部图为弦称k l ，3 为 爪，其中大小为l 的分部中唯一的顶点称为爪的中心若图g 没有导出子图为爪，称g 为 无爪图 令g 1 和g 2 为两个不相交的图，它们的并g lug 2 是具有顶点集矿( g 1 ) uy ( g 2 ) 和边 集e ( g 1 ) ue ( g 2 ) 的图它们的和g lvg 2 是在g lug 2 中连结g 1 的各个顶点到g 2 的各 个顶点而得 今设g 中有边e = “，u ) ，则称顶点u 与u 相邻，乱或u 与e 关联并且常把边e 记为e = 乱秽图g 中与点u 相邻的点的集合记为g ( u ) 或( u ) ，( 乱) 的大小称为钆的度，通常 一2 一 第一章引言 记为d g ( u ) 或d ( u ) 若图g 的顶点为口i ，口2 ，我们称( d ( u 1 ) ，d ( u 2 ) ，d ( ) ) 为 图g 的一个度序列度为0 的点称为孤立点，度为1 的点称为悬挂点令y ( g ) ， 记( u ) ： 口：钞( u ) ，让u ) 称6 ( g ) = m 犰 d ( u ) l 钆y ( g ) ) 为g 的最小度，而 称( g ) = m a z d ( t 正) i 乱y ( g ) 为g 的最大度若6 ( g ) = ( g ) = 尼，则称g 是忌正则图 对于g 的子图日以及顶点集v y ( g 一日) ，我们把在口中的邻集记为蜥( ) ，若c 厂仅 含一个顶点让也记为( u ) 令x 和y 为y ( g ) 的两个不相交的子集，从x 到y 的g 的边的 数目记为e ( x ，y ) 所谓路径或路是这样的子图尸= ( ke ) ，使得y = 铷，秒l ，讥 而e = 铷口l ，秽l 钉2 ，仇一l ，其中诸忱互不相同称p 连接蛳与称铷和讥为尸的端点尸中 边的数量称为尸的长度通常我们称尸为一条( 珈，讯) 路径，把尸记为p = 铷t ，l 仇， 在某些章节中，我们使用自然数来命名图的顶点，在这种情况下，我们也把p 记 为p = ，奶，讥对于图g 中的两个顶点u 和钞，称u 和可之间最短的路径长 度为它们之间的距离，记为d g ( 乜，杉) 或d ( 锃，钞) 所谓圈则是子图g = ( ke ) ，使 得y = 珈，口l ，仇】- 而e = 伽口l ， l 秽2 ，t ，七一l 仇，u 岛伽】，其中诸忱互不相同如果 我们用自然数来命名图的顶点，我们也把c 记为c = 伽，饥，讥，铷图g 的h a m i l t o n 路 径和h a m i l t o n 圈分别指包含g 的所有顶点的路径和圈 我们称图g 的两个顶点t 与钞为连通的，如果g 中有一条( u ，秒) 路径连通是y ( g ) 上 的一个等价关系从而存在y ( g ) 的一个划分，k ，圪使得顶点“和 连通当且仅 当乱和钉属于同一个k 子图g 【】，g 】，g 圪】称为g 的连通分支或简称分支如 果g 只含有一个分支，则称g 为连通的；否则称g 为不连通的本文提到的图一般都 是连通的我们用( g ) 来表示g 的连通分支的数目在对集理论中我们常常考察 一个图g 的具有奇数个顶点的分支，此类分支称为奇分支，其数目我们用d ( g ) 来表 示图g 的一个顶点割是指y ( g ) 的一个子集y 7 ，使得g y 7 不连通一个尼顶点割是含 有七个顶点的顶点割g 的连通度，记为仡或圪( g ) ，定义如下若g 不含有作为生成子 图，g 的连通度定义为最小的忌，使得g 有一个忌顶点割，否则g 的连通度定义为( g ) 一1 顶点集合a y ( g ) 称为一个独立集，如果an ( a ) = d g 中最大的独立集 的顶点数称为g 的独立数，记为q ( g ) 或q 顶点集合b y ( g ) 称为一个控制集，如 果bu ( b ) = y ( g ) g 中最小的控制集的顶点数称为g 的控制数，记为7 ( g ) 或7 如 果7 ( g ) 称g 为忌控制的 图g 的一个对集m 是指e ( g ) 的一个子集，使得m 的任意两个元素都没有公共 端点若对集m 的某条边与顶点u 相关联，则称u 是m 饱和的，否则称u 是m 非饱和的 若g 的每一个顶点都被m 所饱和，则称m 为完美对集大小为尼的对集通常称为尼对 集若g 恰有一个点不被m 所饱和。则称m 为近乎完美对集若g 有d 个点不被m 所饱 和，则称m 为缺失d 对集若g 没有另外的对集m 7 使得i m 7 i i m l ，称m 为g 的最大对 集g 的最大对集所含的边数用q ，或q ( g ) 来表示g 的对集m 中的边的端点集合有 时记为y ( m ) g 的m 交错路是指其边在e ( g ) m 和m 中交错出现的路我们称起始 一3 一 第一章引言 和终结于e ( g ) m 中的边的m 交错路为开放的m 交错路，起点和终点都是m 非饱和 的m 交错路为m 可增广路，起始和终结于m 中的边的m 交错路为封闭的m 交错路注 意m 可增广路必定是开放的m 交错路，反之则不一定成立g 的m 交错圈是指其边 在e ( g ) m 和m 中交错出现的圈 令g 为一连通图，整数1 尼2 1 ，若g 有大小为尼的对集，且g 的每一个大小 为南的对集都包含在g 的一个完美对集中，则称g 为尼可扩的如果g 是南可扩的，但对 于任意e e ( g ) ，g e 非忌可扩，则把g 称为极小尼可扩的设0 他一2 ，若对于 图g 的任意大小为佗的顶点子集s y ( g ) ，g s 均有完美对集，则称图g 为佗因子临 界的，或n 临界的对佗= 1 ，通常称为因子临界的若g 为佗因子临界的，但是对于任 意e e ( g ) ，g e 非佗因子临界，则称g 为极小佗因子临界的2 可扩二部图通常称为支 撑3 连通的2 因子临界图通常称为砖块 在对南可扩图和佗因子临界图的研究过程中，出现了这两个图类的一些变种在这 里我们罗列其中的一部分 在【7 6 】中，y u 定义了七；可扩图一个连通图g 称为尼；可扩的，如果( 1 ) 对于g 中任意 的顶点口，g 一口中存在大小为尼的对集，( 2 ) 对于g 中任意的顶点u ，g 一钞中任意大小 为忌的对集都包含于g u 的一个完美对集中 w e n 和l 0 u 定义了缺失尾可扩图，并在 6 9 】， 7 0 】， 7 3 】，【7 4 ，【7 1 】和 7 2 】中研究了这个 图类的一系列性质一个连通图g 称为缺失尼可扩的，如果g 含有大小为尼( 一3 ) 2 的 对集，且任意大小为南的对集都包含于g 的一个近乎完美对集中 在【31 】中，g l i u 和y u 定义了( 仃，尼，d ) 图令g 为一个连通图，他，尼和d 为满足n + 2 南+ d ( g ) 一2 并且( g ) 一n d 为偶数如果删除g 中任意的几个顶点，所得的g 的子图 包含大小为尼的对集，并且该图中任意大小为尼的对集都包含于该图的一个缺失d 对集， 则称g 为一个( n ，尼，d ) 图由定义可见，( n ，尼，d ) 图可以视为七可扩图