（应用数学专业论文）基本极大m1k2free二分图.pdf

河南大学硕士学位论文 摘要 我们称图g 的一个匹配m 是导出匹配，如果e ( y ( m ) ) = m 图g 的导出匹配数是指图g 的最大导出匹配的边数，用i m ( g ) 表示。日叫做 图g 的真导出子图，如果日是g 的导出子图且h g 我们称图g 是 一个极大( m + 1 ) k 2 一f r e e 二分图，如果图g 是一个连通非完全简单二分 图，使得对图g 中任何不相邻的两点z 和，其中g + z 不含奇圈，都 有i m ( g + x y ) = i m ( g ) + 1 = 仇+ 1 我们称图g 是一个基本极大 ( m + 1 ) 鲍一f r e e 二分图，如果图g 是一个极大( m + 1 ) ( 2 一f r e e 二分图，而 且图g 的任何一个真导出子图都不是一个极大m + 1 ) 鲍- - f r e e 二分图，其中 佗为任意自然数。我们已经发现了1 2 ，1 3 ，1 4 ，1 5 和1 6 个顶点的2 ( 2 一f r e e 图，并对基本极大( m + 1 ) k 2 一f r e e 二分图的结构进行了深入探讨。本文研 究基本极大( 仇+ 1 ) k 2 一f r e e 二分图的结构，刻划基本极大( m + 1 ) k 2 - - f r e e 二分图的顶点数，最大度，连通度和最小度，特别地，研究了最小顶点割 t = u 1 ，u 2 的基本极大( m + 1 ) 鲍一f r e e 二分图，并且刻划g t 的连通 分支的顶点数，最大度和最小度。 关键词：导出匹配，导出匹配数，真导出子图，基本极大( m + 1 ) k 2 一f r e e 二分图 河南大学硕士学位论文 a b s tr a c t am a t c h i n gmo fgi si n d u c e di fe ( v ( m ) ) = m t h ei n d u c e dm a t c h i n g n u m b e ro fg ，d e n o t e db yi m ( g ) ，i st h en u m b e ro fam a x i m u mi n d u c e d m a t c h i n go fg hi sc a l l e dap r o p e ri n d u c e ds u b g r a p ho fgf fhi sa ni n d u c e d s u b g r a p ho fgw i t hh g w ec a l lgam a x i m a l ( m + 1 ) 鹧一行e eb i p a r - t i t eg r a p h ，i fgi sac o n n e c t e db u tn o tc o m p l e t es i m p l e b i p a r t i t eg r a p h ， s u c ht h a tf o re a c hp a i ro fn o n a d j a c e n tv e r t i c e sxa n dyw i t hg + 珂b e i n g b i p a r t i t eg r a p h ，w eh a v ei m ( g + x y ) = 1 m ( g ) + 1 = m + 1 w es a y gi sab a s i cm a x i m a l ( m + 1 ) 鲍一e eb i p a r t i t eg r a p h ，i fgi sam a x i m a l ( m + 1 ) 恐一丘e eb i p a r t i t eg r a p hw i t h o u ta n yp r o p e ri n d u c e ds u b g r a p ho fg b e i n gam a x i m a l ( 钆+ 1 ) 尬一h e eb i p a r t i t eg r a p hf o ra n y 礼n w eh a v e f o u n ds o m em a x i m a l2 k 2 一行e eg r a p h so fo r d e r1 2 ，1 3 ，1 4 ，1 5a n d1 6 i nt h i s p a p e r ，w ew i l lc o n s i d e rt h es t r u c t u r eo fab a s i cm a x i m a l ( m + 1 ) ( 2 一f r e e b i p a r t i t eg r a p h f o rab a s i cm a x i m a l ( r e + 1 ) k 2 一f r e eb i p a r t i t eg r a p hg ，w e c h a r a c t e r i z et h en u m b e ro fv e r t i c e s ，t h em a x i m u md e g r e e ，t h ec o n n e c t i v i t y a n dt h em i n i m u md e g r e e w ec o n s i d e rab a s i cm a x i m a l ( 仇+ 1 ) 硷一f r e e b i p a r t i t eg r a p hgw i t hav e r t e xc u tt = u l ，u 2 s p e c i a l l ya n dc h a r a c t e r i z e t h en u m b e ro fv e r t i c e s ，t h em a x i m u md e g r e ea n dt h em i n i m u nd e g r e eo fa c o m p o n e n to fg 一7 k e y w o r d s ：i n d u c e dm a t c h i n g ，i n d u c e dm a t c h i n gn u m b e r ，p r o p e r i n d u c e ds u b g r a p h ，b a s i cm a x i m a l ( 仇+ 1 ) 鲍一丘e e b i p a r t i t eg r a p h i i 河南大学硕士学位论文 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位中请人( 学住论文作者) 釜名：盎丞趑 2 0 酮年兮月f o 目 关于学位论文著作权使用授权书 本人经河南大学审核批准授予硕士学住。作为学位论文的作者本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学住获得者( 学位论文作者) 签名：盔丞邀 2 0oc 年孓月一目 学住论文指导教师釜名：室墼堑 2 0 矿c 年孓月f b 目 第一章引言 匹配是图论中很重要的内容，在现实生活中有许多具体问题，如工作分 配问题，交朋友问题，球队比赛问题以及军事上部队的部署方案的制定等问 题都可化为一般的匹配问题加以解决。早在上世纪初，图的匹配理论就以不 同的方式受到学者的普遍关注，h a l l ：】和t u t t e 2 】定理为图的匹配理论奠定 了坚实的基础。h a l l 定理给出了一个二分图有完美匹配的充要条件。近百年 来，图的匹配理论迅速发展，( l o v a s z 和p l u m m e r ) 1 3 1 的专著匹配理论极 大促进了图的匹配理论的研究，t u t t e 和l o v a s z 给出了一般图具有完美匹 配的充要条件，p l u m m e r 提出如下的n 可扩图的概念：设p 和n 为正整数， 且n ( p 一2 ) 2 一个p 个顶点的图g 称为n 可扩的，如果图g 的每一个 包含n 条边的匹配都能扩充为一个完美匹配。h e t y i e 4 】研究了二分图n 可 扩性。一个图g 称为二临界的，如果对图g 的任意一对不相同的顶点u ，v ， 图g u u 有一个完美匹配。如果一个图是二临界的，则它是1 可扩的。 一个有趣的结论是，如果一个图是2 可扩的，则它或者是二分图或者是二临 界的。另外，如果一个图是n 可扩的，则它也是一1 可扩的。 八十年代以来，图的匹配理论在组合数学，运筹学与控制论中的作用日 益突出，近年来更成为图论及组合最优化中更为活跃的核心课题之一，而图 的导出匹配是近年来兴起的新的研究方向。关于导出匹配，( c a m e r o n ， 1 9 8 9 ) 5 1 ，( f a u d r e ee ta 1 ，1 9 8 9 ) 6 j 和( h o r a ke ta 1 ，1 9 9 3 ) 7 j 对此已经有所研 究。原晋江( 8 】8 提出了图的导出匹配可扩性的问题，对一个简单有限图g ，如果 图g 的任意一个导出匹配都包含在一个完美匹配中，则称图g 是导出匹配可 扩的。为了方便，g 是i m - e x t e n d a b l e 表示g 是导出匹配可扩的。很容易证 明每一个，m - e x t e n d a b l e 图一定有偶数个顶点。一个，m e x t e n d a b l e 图是 极大，如果对每一对不相邻的顶点z 和y ，g + x y 不是一个，m e x t e n d a b l e 图。图的m e x t e n d a b i l i t y 可以看作是n e x t e n d a b i l i t y 的一个变形( p l u m m e r ，1 9 8 0 ) 1 9 j ，一个连通图g 是n 一可扩的，如果 y ( g ) 22 n + 2 ，g 有一个完美匹配，并且对g 的每一个匹配m 满足l m i = n ，存在g 的一 个完美匹配m + 满足mcm + 对一个简单图g ，记 河南大学硕士学位论文 i m ( g ) = m a x l m i ：m 是图g 的导出匹配) m ( g ) = m a x i m i ：m 是图g 的匹配) m i m ( g ) = m ：m 是图g 的导出匹配且l m l = j m ( g ) ) 宋晓新提出了一个十分有趣的o p e np r o b l e m ：是否存在一个连通不完全 简单图g ，对其中每一对不相邻的顶点x 和可，都有i m ( g + x y ) = i m ( g ) + 1 = m + 1 7g 是一个极大( m + 1 ) k 2 一f r e e 图，如果g 是一个连通非完全简 单图，使得任意给定一对非相邻的顶点x 和可，m ( g + x y ) = i m ( g ) + l = m + 1 【1 0 】我们已经解决了极大( m + 1 ) k 2 一f r e e 图的存在性i ；- j 题，并且已 经找到了1 2 ，1 3 ，1 4 ，1 5 和1 6 个顶点的2 k 2 - f r e e 图。三正则基本极 大( m + 1 1 k 2 一f r e e 图的存在性问题仍然是o p e n 的，宋晓新研究了可能存 在的三正则基本极大( m + 1 ) k 2 一f r e e 图的一些基本结构性质，找出了x c 的一些禁用子图，其中= f g ：g 是一个基本极大( m + 1 ) ( 2 一f r e e 图，其中m 为导出匹配数，而且g 是三正则图- 。谢炎涛找出了顶点数为 1 2 ，1 3 ，1 4 的基本极大2 k 2 一f r e e 图，为导出匹配数和顶点数较小的基本极 大( m + 1 ) ( 2 一f r e e 图的研究提供了基础。还给出了的一些禁用子图和 一些相关的其他结论。 二分图又称作二部图，是图论中的一种特殊模型。求二分图最大匹配可 以用最大流或者匈牙利算法。那么对于二分图中，任意两个不相邻的且连接 之后不形成奇圈的顶点，连接之后导出匹配数加1 ，这样的二分图是否存在 呢? 换句话说，那么是否存在一个连通非完全简单二分图g ，使得图g 中任 何不相邻的两点z 和可都有i m ( g + x y ) = i m ( g ) + 1 呢? 这是一个有待 解决的问题。如果存在的话，这种图的结构性质又如何呢? 这就是本篇文章 中要探讨的问题。在这篇文章中，我们将考虑基本极大( m + 1 ) 鲍一f r e e 二 分图的结构。对一个基本极大( m + 1 ) 一f r e e 二分图g 来说，我们将刻划 它的顶点度，最大度，最小度和连通度。对于有最小顶点割t = u 1 ，? 2 2 ) 的 基本极大( m + 1 ) k 2 一f r e e 二分图g ，我们还将特别考虑g t 的连通分支 的顶点数，最大度和最小度等问题。 2 第二章记号及定义 为了叙述方便，我们首先给出全文最常用的一些符号及基本概念。在全 文中，所考虑的图均为有限的非平凡连通简单图。 给定一个图g ，v = v ( g ) 和e = e ( g ) 分别表示它的点集和边集。 对于x y ( g ) ，q y ( g ) ，x 在q 中的邻集 记作q ( x ) = 秒q x ：存在一个点x x 满足x y e ( g ) 】- 如果q = y ，q ( x ) 简单记作( x ) 对任意的z y ( g ) ，q ( _ z ) ) 简记为心( z ) ，如果q = v ，简记为( z ) z 在q 中的闭邻集记作醌( z ) = xu ( z ) 如果q = v ，简单记作( z ) 对任意的t v ，q v ，u 在q 中的度记作奶( u ) 图g 中的以q 为顶点集的导出子图记作g 【q 】 对于x v ( g ) ，记e ( x ) = u v e ：u ，勘x ) 对于x ，y v ( a ) ，从x 发向y 中的边集记作e ( x ，y ) ，从x 发向y 中 的边数记作 e ( x ，y ) i 对于m e ，记v ( m ) = v ：存在一点x v 满足u z m ) 对一个简单图g ，记 i m ( g ) = m a x l m i ：m 是图g 的导出匹配 - m ( g ) = m a x l m i ：m 是图g 的匹配 m i m ( g ) = m e s m ：m 是图g 的导出匹配且l m i = ，m ( g ) 】 仡( g ) 表示图g 的连通度。 下面介绍本文所使用的一些基本定义： 定义1 2 1 设g = ( ，k ，e ) 是一个无向图，k 是两个互不相交 的顶点集，并且图中的每条边( i ，歹) 所关联的两个顶点i 和j 分别属于这两 个不同的顶点集( i ，歹) ，则称图g 为一个二分图。 3 河南大学硕士学位论文 定义1 2 2m e 是图g 的一个匹配，如果对m 中任何不相同的 两边e ，厂，都有y ( e ) nv ( ) = 0 定义1 2 3图g 的匹配m 是完美匹配，如果v ( m ) = y ( g ) 定义1 2 4 图g 的匹配m 是导出匹配，如果e ( y ( m ) ) = m 定义1 2 5h 叫做图g 的一个真导出子图，如果日是g 的导出子图 且日g 定义1 2 6 我们称图g 是一个极大( m + 1 ) 恐一f r e e 二分图，若果图 g 是连通的非完全简单二分图，使得对图g 中任何不相邻的两点x 和可，其 中g + 删不含奇圈，都有i m ( g + x y ) = i m ( g ) + 1 = m + 1 定义1 2 7 我们说图g 是一个基本极大( m + t ) 9 2 - f r e e 二分图，如 果图g 是一个极大( m + 1 ) 魁一f r e e 二分图，而且图g 的任何一个真导出 子图都不是一个极大( 礼+ 1 ) 鲍一f r e e 二分图，其中n 为任意自然数。 4 第三章相关的已知结果 3 1 典型实例 首先，我们来介绍一个1 2 个顶点的极大2 ( 2 一f r e e 图。这个图是由 我的师兄谢炎涛同学找到的。这个图的发现巩固和完善了基本极大( m + 1 ) k 2 一丘e e 图相关的若干研究课题的理论基础。现在我们已经找到了具有 1 3 ，1 4 ，1 5 和1 6 个项点的极大2 鲍一f r e e 图。 对i = 1 ，2 来说，设置= ( ，最) 是一个5 圈，其中k = a t ，玩，q ，也，e t 】， 易= q 扣t ，6 t q ，c i d i ，d i e t ，e i a i ) 设g 1 是这样一个图：顶点集合y ( g 1 ) = u u h i ，危2 ) ，和边集e ( g 1 ) = u 邑，其中e 3 = 忽1 危2 ) u h l x l ，h 2 x 2 ： x l k ，x 2 k ) ，e 4 = a l a 2 ，a l c 2 ，a l d 2 u b l b , ；，b l d 2 ，b l e 2 u c l c 2 ，c 1 e 2 ，c l a 2 u ( d l d 2 ，d l a 2 ，d 1 6 2 u e l e 2 ，e 1 5 2 ，e l c 2 ) 则g 1 是一个极大2 k 2 一f r e e 图，证明 略，图形如下： 5 河南大学硕士学位论文 3 2 几个定理 定理3 1 【1 1 l 设g = ( ve ) 是一个顶点数为1 1 ，导出匹配数为m 的 基本极大( m + 1 ) k 2 一f r e e 图，那么对每一对不相邻的顶点z 1 和x 2 ，都有 n o ( z 1 ) g ( z 2 ) 定理3 2 1 1 2 】 设g = ( ve ) ，其中x c = g ：g 是一个基本极大 ( m + 1 ) 尥一f r e e 图，其中m 为导出匹配数，而且g 是三正则图) ，l v l = n ， 而且设v 0 v 和t = ( 如) = 如，u 1 ，u 2 ，u 3 ) 那么有如下结论： ( a ) g t 有唯一的一个分支日1 或者有两个分支日1 和凰 ( b ) 如果g t 有唯一的一个分支日1 ，令n 1 = i y ( h 1 ) i ，则n 1 1 0 ，凡 1 4 ( c ) 如果g 一? 有两个分支日1 和飓，令n 1 = i y ( h 1 ) l ，n 2 = l y ( 日2 ) i ，则 n 1 三l ( m o d2 ) ，n 1 1 3 ，n 3 0 定理3 3 1 1 3 l 设g = ( ve ) 是一个顶点数为1 3 ，导出匹配数为m 的基 本极大( m + 1 ) k 2 一f r e e 图，那么有如下结论： ( a ) 设x ，箩，z vx y e ，y z 隹e ，那么n ( x ) 一( ，z ) ) d ( b ) 设u ，t ，u 伽隹e ，那么i m ( g 一( l 且m m i m ( g ) ，显然有v o 隹y ( m ) ，否则i m ( g ) = 1 ，与i m ( c ) 1 矛盾。则 m 还是g v o 的一个导出匹配，则l m i i m ( g 一 v 0 ) i m ( g ) = i m i 因此z m ( g ) = i m ( g v o ) = l m i 得证。 引理4 2 设g = ( ，k ，e ) 是一个连通非完全简单二分图，其中 ( ，k ) 是图g 的一个二划分。设z 1 是g 中的一个最大度点，且 i m ( g ) = 1 ，则有e ( g n ( x 1 ) ) = o 证明：假设e ( g 一( z 1 ) ) 0 ，设y l y 2 e ( g 一( z 1 ) ) ，其中 可1 ，耽k 由于z 1 为g 中最大度点。而且x l y 2 隹e ，则存在x l 的一个邻点z 2 使得y l x 2 圣e ，则 z l z 2 ，y l 耽) 是g 的一个导出匹配，矛 盾。 引理4 3 设g = ( ，e ) 是一个连通非完全的简单二分图，g 1 是 g 的一个连通子图。设x 和y 是图g 1 中不相邻的两点，则g + z 可为二分 图当且仅当g 】+ z 可为二分图。 证明：假设g + z 夕不是二分图，g 1 + z 可是二分图。则g + z 可中有一 个包含新加边x y 的奇圈，则g 中含一条偶数条边的z 可路p 由于g 1 为 连通图，则g 1 中包含一条z 可路q 由于g 1 + z 可是二分图，因此q 有奇 数条边，从p 和q 可知g 中含有奇圈，与g 是二分图矛盾，引理4 2 得证。 引理4 4 设g = ( ，k ，e ) 是具有二划分( ，k ) 的一个基本极大 ( m + 1 ) 娲一f r e e 二分图，那么对于任意两个相异顶点z 1 ，。2 ，都有 7 河南大学硕士学位论文 n g ( x 2 ) 一n a ( z 1 ) 0 证明：设i m ( g ) = m ，x 1 ，x 2 k ，并假设n o ( z 2 ) 一g ( x 1 ) = 0 对g z 2 中每一对不相邻的顶点x 和y ，g + x y 不含奇圈，如果能够证 明i m ( g x 2 + x y ) = i m ( g z 2 ) + 1 成立，则g z 2 也是一个极大 ( i m ( g z 2 ) + 1 ) 鲍一：f r e e 二分图。就与给定的条件矛盾。设x 和y 是使 得g + 鲫不含奇圈的不相邻的两点，且z ，y x 2 ，令m m i m ( g + x v ) 我们有如下结论； 断言：i m ( g z 2 + x y ) = i m ( g z 2 ) + 1 为了证明这个断言，我们 分两种情形讨论。 情形1 z 2 圣y ( m ) 在这种情形下，m ( g z 2 + 列) = l m l = j m ( g + x y ) = i m ( g ) + 1 = i m ( g x 2 ) + 1 ，断言成立。 情形2z 2 y ( m ) 在这种情形下，设z 2 2 3 e ( m ) ，令尬= m z 2 x 3 + z l z 3 ，那么舰m i m ( g z 2 + z 可) ，从而i m ( g z 2 + x y ) = i m ( g + x y ) = i m ( g ) + i = i m ( g - x 2 ) + 1 断言成立，因此引理4 4 得证。 引理4 5 g = ( ，k ，e ) 是具有二划分( ，k ) 的一个基本极大( m + 1 ) k 2 一f r e e 二分图，设t = u 1 ，u 2 ) 是g 的一个最小点割，其中u 1 ，u 2 k 设皿是g t 的一个连通分支，g 1 = g v ( h 1 ) u u 2 则在g 1 中一 定存在两个不相邻的顶点x 和y ，使得g + z 可不含奇圈，而且任给m m i m ( g + z 可) ，都有u l y ( m ) 证明：由引理4 4 可知，存在k 中两点u 1 和u 2 ，使得 e ( u l ，u 2 ， 0 1 ，口2 ) ) = u l v l ，u 2 v 2 设于= 扎2 ，u 1 】- ，u = v 一( 于) 设m 1 m i m ( g + u 2 u 1 ) 且 m 1 = m u 2 u l ， 则y ( 尬) u ，f m l i = i m ( g ) = ，m ( g u 】) 设日1 ，凰，凰，风是g t 的连通分支，对每一个i l ，设 暇= y ( 凰) o u 2 ，g t = g 眦】，阢= uny ( 凰) 显然我们有u = u _ 阢：1 i s ) 8 河南大学硕士学位论文 则有 对每一个i l ，我们断言，m ( g 矾 ) = j m ( g t ) 否则，假设 i m ( g u 1 】) i m ( g u i ) + ，m ( g 1 = 2i = 2 矛盾。因此， 由于 因此， = i m ( g u d ) = ，m ( g ， i m ( c ) = j m ( g 【明) = j m ( g 阢】) = i m ( g t ) i m ( g ) = i m ( g 一 u 1 ) ) = ，m ( g 网) ， m i m ( c 一 乱1 ) ) m i m ( g ) 这样一来，对于每一个 m m i m ( g 一 u 1 ) ) 和每一个i o l 来说，由于 i m ( g ) = i m ( g - u ) ) = m = i m n e ( c t ) l - x m ( g ) ，矛盾。因此i m ( g ) = i m o i = z m ( g t ) 因此， i = l 对每一个m m i m ( g ) ，由于 我们有 88 t m ( g ) = m = i m n e ( c t ) i m + 5 1 4 河南大学硕士学位论文 u l吃 f i g u r e l 2 4 3 基于( m + 1 ) ( 2 一f r e e 二分图与它的最小 点割的分析 定理4 7 设g = ( ，k ，e ) 是一个基本极大( m + 1 ) t ( 2 一行e e 二分图， 且i y l l = n 1 ，l k i = n 2 ，i m ( g ) = m 设t 是g 的一个最小点割，而既 是g t 的一个连通分支。则我们有下面的结论： ( a ) 设x 和y 是图g 中使得g + x y 不含奇圈的不相邻的两点，若( z ，可 - ) 2 t ，贝0i m ( 9 1 ) = i m ( h 1 一( z ，可) ) ) ( b ) 设x 和y 是图g 中使得g + z 可不含奇圈的不相邻的两点，g 1 = g v ( h 1 ) u 卅，7 1 = t 一( 【z ，可) ) 若e ( g t 一( z ，可) ) ) e ( t ) 则 i m ( h 1 一( 乃) ) = 0 ( c ) 设日1 = ( x 1 ，m ，e 1 ) ，z 1 x 1 且i n ( x 1 ) ny ( m ) i = ( h t ) ，并设 i n ( x 1 ) n y ( t ) i = m a x i n ( v ) n y ( t ) i ：u y ( h 1 ) 且l n ( v ) n y ( 研) i = ( 研) 】，其中x x = y ( 凰) ny l ，m = y ( 皿) nk ，e 1 = e ( 研) 设 g o = h 1 一n ( z 1 ) ，n o = i v ( c o ) l 且v ( g o ) = x ouy o ，其中x o = x 1 z 1 ) ，y o = h ( z 1 ) 设x o = x i ：2 i f 1 ，y o = y j ：1 歹 1 2 ) ，若t = 乱1 ，u 2 ) 且g 十u l u 2 不含奇圈，则c 1 5 ，f 2 3 如 果地z 1 e ，则有f 1 + 1 2 9 证明：( a ) 设m m ，m ( g + x y ) 且庇= m x y ，则v ( m ) y 一( k ! ) ) sv t 设肌= v ( h i ) u t ，则有z m ( g m ) + j m ( 皿) 河南大学硕士学位论文 i m ( g ) = i 砑i = i m ( g 一眦) + ，m ( 凰一( z ，可 ) ) ，因此i m ( h 1 ) ，m ( 皿一( z ，可 ) ) ；另一方面i m ( h 1 ) i m ( h 1 一( z ，可) ) ) ，因此我们 有，m ( 凰) = i m ( h t 一( _ z ，可 ) ) ( a ) 得证。 ( b ) 反证法：设 m m i m ( g + z 箩) ，m = m z 可 由于 e ( g 1 一( ( z ，可) ) ) e ( t ) ， 则 v ( m ) ( v y ( 凰) 一t ) uy ( 五) 设e e ( h t 一( a ) ) ，则砑+ e 也是g 的一个导出匹配，矛盾。( b ) 得 证。 ( c ) 设u 1 ，u 2 ，由定理4 4 ( d ) 可知，u l u 2 e 则有n ( x 1 ) = 协：1 2 + 1 j 1 2 + ( 日1 ) ) ，礼o = f 1 + 1 2 1 ，则h i = x ( h 1 ) + n o + 1 如 图f i g u r e2 2 3矗 ，- y i y 2 y 3 y ，2 f i g u r e2 ( 1 ) 断言1 ：对每一个x v 来说，我们有i m ( h 1 一( z ) ) = i m ( h 1 ) 不妨设x k 分三种情形讨论； 情形1当x = u 1 时，设y 是k 中一个与x 不相邻的顶点，则 ( z ，可) ) t 1 6 河南大学硕士学位论文 则由( a ) 可知， i m ( h 1 一( z ，可) ) ) = i m ( h 1 ) 而 ，m ( 皿一( ( z ，可) ) j m ( 研一( z ) ) i m ( h 1 ) ， 因此 i m ( h 1 一( z ) ) = i m ( 皿) 情形2 当x u 2 隹e 时，则( z ，u 2 ) 2t 则由( a ) 可知， i m ( h t 一对( z ，u 2 ) ) ) = ，m ( 研一( z ) ) = i m ( h 1 ) 情形3 当x 让1 且z t 2 e 时，由引理4 4 可知，存在u 1 的一个邻 点y ，使得y 不是x 的邻点，而且( z ，秒) ) 2t 则由( a ) , - 7 矢n ， i m ( h 1 一( k 可 ) ) = j m ( 玩) 巾 i m ( h 1 一( z ，y ) ) j m ( 研一( z ) ) i m ( h i ) ， 因此 t m ( h 1 一( z ) ) = i m ( 日1 ) 断言2 ：i m ( h 1 ) 2 不妨设x 2 y 1 e ，由于z 1 是日1 中最大度点， 则存在x l 在研中的一个邻点不是x 2 的邻点，不妨设x 2 y l 。+ 1 譬e ，则 z 2 y l ，x t y l ：+ 1 是皿的一个导出匹配，断言成立。 ( 2 ) 如果7 t 2 x 1 e 设v o = v ( g o ) u u 1 ) 断言3 ：m a x d ( y j ) ：1 歹1 2 l l 2 否则，不妨设d ( y 1 ) i 1 1 分两种情形来讨论： 情形1 如果y l u t 隹e ，则有n ( y 1 ) = x o ，则( u 1 ，y 1 ) ) 三t ，则由 ( a ) 我们有 m ( 既) = ，m ( 研一( “1 ，1 ) ) 1 ， 由断言2 可得矛盾。 情形2 如果y l u t e ，则( z 1 ，可1 ) ) 三t ，则由( a ) 我们有 j m ( 日1 ) = i m ( 研一( z 1 ，可1 ) ) 1 ， 1 7 河南大学硕士学位论文 由断言2 可得矛盾。 断言4 ： u v ( g o ) ：l n ( v ) nu o l = 1 ) = 0 假设断言不成立，设v 0 是g o 中一点而且满足i n ( v o ) nu o i = 1 分两种情形来讨论： 情形1 v o x o 而且n ( v o ) nu o = y o 此时，y o s o ，y o 不是x l 的 邻点，由定理4 6 ( a ) 可知； n ( v o ) 一( 珈，x l 】- ) o ， 因此 n ( v o ) nu o 一 可o ) = n ( v o ) 一( z 1 ) 一( 珈 _ 0 ， 矛盾。 情形2v 0 y o 而且n ( v o ) n v o = 知 - 此时，x 0 ) c o u u 1 ) ，g 一 z o ) 是一个不连通图，与t 是g 的一个最小点割矛盾。 断言5 ：g o 中没有孤立点。假设断言不成立，分两种情形来讨论： 情形1 中有一点在g o 中为孤立点。不妨设x 2 为g o 中的一个孤 立点。则n g ( x 2 ) 一g ( z 1 ) = 0 ，与引理4 4 矛盾。 情形2k 中有一点在g o 中为孤立点，此时日1 是一个不连通图，矛 盾。 注断言2 ，断言3 和断言5 的结果是基本极大( m + 1 ) k 2 一f r e e 二 分图的独有性质，这些性质将带给我们更加丰富和有趣的结果，而基本极大 ( m + 1 ) k 2 一f r e e 图却没有类似的性质。 由断言4 和断言5 可知，对于g o 中任意一点劲，我们有d u o ( z o ) 2 ， 则有f 1 2 ，1 2 2 由定理4 6 ( e ) 可知m a x d ( y j ) ：1 j 2 2 】- 3 ，则由断言3 可得 1 1 5 如果2 2 = 2 且f 1 5 ，由断言4 和断言5 可知，任给2 i 1 1 ，n ( x i ) n y o = 可1 ，耽】- ，则有弱n ( y 1 ) ，我们已经知道d ( y t ) ，d ( y 2 ) 1 1 2 ，矛盾， 因此我们有1 2 3 因此1 2 3 ，1 1 5 如果f 2 = 3 且1 1 = 5 由定理4 6 ( e ) 和断言3 可知 d ( y 1 ) 1 - d ( 可2 ) = d ( y 3 ) = 3 1 8 河南大学硕士学位论文 我们断言u 1 是g 【 中的一个孤立点，否则，不妨设 n ( y 3 ) = x 4 ，x 5 ，u 1 ) ， 由( a ) 可知 i m ( h 1 ) = i m ( h 1 一( z 1 ，蜘) ) ) = 2 ， 不妨设 x 2 y 1 z 3 y 2 是 i m ( h 1 一丙( z 1 ，蜘 - ) ) 的一个导出匹配，则有d u o ( x 2 ) = 1 ，与断言4 矛盾。 儿 f i g u r e3 由于y o 中的点的度都等于3 ，它们的邻点集互不包含而且都是凰的 子集，因此在中恰有一个点在a u o 】中的度为3 ，不妨设d u o ( x 2 ) = 3 ， 则g o z 2 是一个- - i n - - 分图，也就是一个六圈，不妨设( 如图f i g u r e3 ) e ( g o x 2 ) = x 3 y 2 ，x 3 y 3 ，x 4 y l ，x 4 y 3 ，x 5 y l ，x s y 2 ， 设 m m i m ( g + x l y l ) ，尬= m x l y l 则有 m 1 m i m ( g ) ，y ( 尬) v ( c ) 一( z 1 ) 一( 可1 ) = ( y ( g ) v ( a 1 ) ) u 乱1 ，z 3 ，y 2 ，蜘) ， 1 9 河南大学硕士学位论文 我么断言2 , 3 y ( 舰) ，否则，我们有y ( 尬) nv ( h i ) = d ，则有m 2 = 尬+ x 3 y 2 也是图g 的一个导出匹配，而且l 尬i = i 她f + 1 ，矛盾，由于沈 和伽的对称性，不妨设z 3 耽尬，则有 y 3 譬y ( 尬) ，m 3 = 舰u z 4 可1 - 是图g 的一个导出匹配，而且i i = i 舰i + 1 ，矛盾，因此f 1 + f 2 9 ( 3 ) 如果u 2 x l 隹e 则设g o = v ( g o ) u u 1 ，u 2 ) 断言6 ： u v ( g o ) ：i n ( v ) nu o l = 1 ) = 0 类似于断言4 的证明可得 此结论。 类似于断言3 ，下面我们分析k 中顶点的最大度与中顶点个数的 关系。 断言7 ：m a x d ( y j ) ：1 j 2 2 ) 1 1 2 否则，不妨设d ( y 1 ) 1 1 1 分两种情形来讨论： 情形1 如果y l u l 隹e ，类似于断言3 可得矛盾。 情形2 如果y l u l e ，不妨设 n ( y 1 ) = ( z 2 ) ) u 镪) 设 m m i m ( g + x l y l ) ，舰= m x l y l 则有 m 1 m i m ( g ) ，y ( 尬) v ( g ) 一n ( x 1 ) 一n ( y 1 ) = ( y ( g ) y ( g ) ) ux 2 ，u 2 ) u ( y o 可) ) 由断言6 可知，y o 中一定有一点为z 2 的邻点，不妨设x 2 y 2 e ，假设 x , 2 隹y ( 尬) ，则有 y ( 尬) ( y ( g ) y ( g 1 ) ) u 乱2 ) ，尬+ x 2 y 2 是g 的一个导出匹配，与m 1 m i m ( g ) 矛盾，因此z 2 y ( 尬) 设 e o 尬是与2 ：2 相关联的一条边，其中e o = x 2 u 2 或者e o e ( g o ) 设 m 2 = 慨一e o ，则有 y ( 尬) ( y ( g ) y ( g ) ) u u 2 ) 2 0 河南大学硕士学位论丈 由断言1 和断言2 可知 i m ( h 1 一n ( u 2 ) ) = i m ( h 1 ) 2 ， 则存在h 1 一n ( u 2 ) 的一个导出匹配 e 1 ，e 2 ) ，使得u e 1 ，e 2 】是g 的一 个导出匹配，而且 m 2 + 2 = 尬 + 1 ，矛盾。断言7 得证。 断言8 ：g o 中没有孤立点。假设断言不成立，分两种情形来讨论； 情形1x o 中有一点在g o 中为孤立点。不妨设z 2 为g o 中的一个孤 立点。由引理4 4 可知，x 2 u 2 e ，则( z 2 ) 一霄( z 1 ) 一( u 2 ) = 0 ，与定理 4 6 ( a 1 矛盾。 情形2k 中有一点在g o 中为孤立点，此时凰是一个不连通图，矛 盾。 由断言6 和断言8 可知：对于g o 中任意