（应用数学专业论文）关于k阶限制边连通度若干问题的研究.pdf

山东师范大学硕士学位论文 关于七阶限制边连通度若干问题的研究 桑镇 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 图的限制性边连通度问题及许多理论都是源自大型网络的设计和可靠性分析 另外限制性边连通度在实际问题中有着广泛的应用，是图论研究中一个很活跃的课 题，各类限制边连通度问题被相继提出并加以发展、应用 当研究网络可靠性的时候，经常考虑这样一种图模型，它的节点不失效，但是 它的连线，也就是边可以独立地等可能地失效，失效的概率是p ( 0 ，1 ) 这就是非 常有名的m o o r e - s h a n n o n 网络模型【1 ，2 】令g 是个m o o r e - s h a n n o n 网络模型，边 数为h 的边割的数目用瓯表示，如果g 恰好有e 条边，则它不连通的概率p ( a ，力 就可以表示为： e p ( v ，p ) = 倪矿( 1 一p ) 卜 h = l 显然，p ( c ，p ) 的值越小，网络的可靠性越好如果能确定所有的系数瓯，那 么这个网络的可靠性就确定下来了但是对于任意图，p r o v a n 和b a l l 在文献 3 】中 指出，确定所有的系数瓯是个p 困难问题 用q ( n ，e ) 表示n 个点e 条边的图的集合，当p 充分小时，在q ( n ，e ) 中为了最 小化p ( a ，p ) ，边连通度a ( g ) 起了非常重要的作用b a u e re ta l 在文献【4 】中指出， 当p 充分小时，对g 1 ，g 2 a ( n ，e ) ，如果a ( g 1 ) a ( g 2 ) ，则p ( g 1 ，p ) a ( g 2 ) ，t h ep ( g 1 ，p ) 入( g 2 ) ，则p ( g 1 ，力 入7 ( g 2 ) ，则p ( g 1 ，力 冬+ 1 ，则入( g ) 靠( g ) 9 山东师范大学硕士学位论文 如果a k ( g ) = & ( g ) ，则g 称为入七一最优图 如果顶点集ucv ( c ) 对应的边割瞄习是个入七一割，则沙称为是个又七一 碎片显然c v 】和g 【】都是连通的最小的a 七一碎片称为是k 一原子 入七原 子的阶数用符号亿( g ) 来表示显然，k 仉( g ) 【世掣j 碎片和原子的概念是 由m a d e r 在文献【1 5 】中提出的，这两个概念在图的连通度研究中占有非常重要的 地位 对于些图类，当我们找到了a ( g ) 的上界，接下来要研究的问题就是满足什 么条件的图可以达到k ( g ) 的上界，就目前的研究现状，达到a k ( g ) 的上界的图可 以认为是具有最好可靠性的图k 阶限制边连通度的最优性的研究已经取得了一 些成果； 定理l 。1 1 1 6 】( h e l l w i g 和v o l k m a n n ) 设g 是个入2 连通图，对于所有不邻的 不在三角形中的点对u ， ，有i n ( u ) n ( t ，) l 2 ；对于所有不邻的至少一个点在三角 形中的点对饥，t ，有l ( t ) n ( ) i 3 ；则g 是个入2 一最优图 定理1 1 2 【17 l ( u e i t i n g 和v o l k m a n n ) 设g 是个a 2 一连通图，对于所有不邻的 点对u ，秒，有i n ( u ) nn ( v ) l 1 ；f ( g ) 【华j ，每个三角形t 至少存在一个顶点 y ( t ) 使得d ( ) l j ，则g 是个入2 一最优图 定理1 1 3 1 8 】( c b a l b u e n ae ta 1 ) 设g 是一个恐连通图，围长g 是奇数且 6 ( g ) 2 ，若对所有的满足d ( 札，t ，) = 9 1 的点u ，钞，使g 【( 9 1 ) 2 ( u ) n ( 9 1 ) 2 ( 口) 】包 含边，则g 是a 2 最优图 其中( 夕一1 ) 2 ( u ) = 倒z v ( g ) ：d ( z ，u ) = ( g 一1 ) 2 定理1 1 4 1 9 】( t s o n e k ae ta 1 ) 对直径为d ，围长为g 的图g ，若d 2 【 一x ) 2 j ， 则g 是k 最优图 1 0 山东师范大学硕士学位论文 定理1 1 5 2 0 l ( 王应前) 设g 是阶数佗6 的图，对g 中任意对不相邻的顶 点z ，y 都有d ( x ) + d ( y ) 亿十3 ，则g 是一个入3 最优图 对于二部图的k 阶限制边连通度最优性的研究，最近也取得了很大的进展主 要结果有： 定理1 1 6 ( j y u a ne ta 1 ) 设g = ( xuy , e ) 是二部图，阶数n 之2 k 若有 占( g ) 学，则g 是入七一最优图 定理1 1 7 【2 2 】( 尚莉和张和平) 设g = ( xuy , e ) 是二部图，阶数n 4 若对 所有的满足d ( x ，y ) = 2 的点x ，y 有d ( z ) + d ( 可) 2 ( n + 2 ) 4 j + 1 ，则g 是a 2 一最优图 如果对于一个k 最优图的每一个k 割都孤立出一个k 阶连通子图则我们 称这样的图为超级k 连通图 定理1 1 8 【2 1 】( j y u a ne ta 1 ) 设g = ( x u y , e ) 是二部图，i g i = n ，若最小度 6 ( g ) 芈，则g 是超级入七一连通图 山东师范大学硕士学位论文 第二章二部图的最优性 二部图对于一般图而言结构有些简单，但这并没有给我们对于k 阶限制边连 通度的研究带来方便目前为止得到的这方面结果并不是很多a h e l l w i n g 和l v o k m a n n 得出： 定理2 1 【2 3 】t 令g 是连通的二部图，其中亿( g ) 1 0 ，任意满足d ( x ，y ) = 2 的 点z ，y 满足d ( x ) + d ( y ) 2 l ( n ( g ) + 2 ) 4 j + 4 ，则g 是a 2 一最优图 我们得出如下结果： 定理2 2 ：若g 是连通的二部图且6 ( g ) 3 ，对于使d ( x ，y ) = 2 的点z ，都 有d ( z ) + d ( 可) 2 l - - 孕4 gj + 4 ，则g 是a 3 最优图 证：由6 ( g ) 3 知n ( g ) 6 ；据定理1 3 可得g 必是入3 连通图，且入3 ( g ) 岛( g ) ， 只须证a 3 ( g ) 6 ( g ) 令s 是g 的a 3 割，x 是g s 中点数较小的分支，y 7 ，y 为g 的二划分 令x ，= x n v 7 ，x ，= x n ，不妨设i x ，i i x ，l ，贝0 由i x l l - - 字2 gj ，得i x 7 i l - - 竽3 - 4 gj 情形1 ：x 7 中只有一点，设其为x 1 在g x 】中取点t , 2 ，x 3 ，使a x l ，x 2 ，x 3 】连通，对于u n ( x 1 ) 1 7x x 2 ，x 3 ， 由6 ( g ) 3 可得，i g ( v ) n 叉j 2 a 3 ( g ) 乏二j n ( x i ) n 叉j + j f ( z 1 ) nx x 2 ，z 3 ) ，_ 】j 。函 3 i g ( x i ) n x i + i g ( x 1 ) n x x 2 ，x 3 l 6 ( g ) 石i 故可得a 3 ( g ) 6 ( g ) 1 2 情形2 ：i x i 2 此时存在三阶连通子图a x l ，x 2 ，z 3 ) 】，使z l ，x 2 x 7 ，x 3 x 情形2 1i x 7 i = i x i = l 4 - 竽j 情形2 1 1 ：m a x i n ( x i ) n x z 3 ) i ：i = 1 ，2 ) 2 ，且i n ( x s ) n x z 1 ，z 2 l 2 不妨设m 凹 i n ( x i ) n x z 3 ) j ：i = 1 ，2 ，= i n ( x 1 ) r l x z 3 ) j ，n ( x 1 ) n x z 3 ) = 山东师范大学硕士学位论文 a l ，a k 若k = 2 p ，对于d ( x ，) = 2 的点有d ( z ) + d ( y ) 2 【华j + 4 由于i x ，i = 【华j ， 则存在p 对点( a l ，a 2 p ) ，( a 2 ，a 2 p - 1 ) ，( 唧，唧+ 1 ) ，使i n ( a i ) n - z i + i n ( a 2 p + 1 一i ) n - x i 4 ， i = 1 ，p 若k = 2 p + 1 ，则至少存在一点a i ，设该点为a 2 p + 1 ，满足i n ( a 2 p + 1 ) n 又i 2 ，此 时仍有i n ( a i ) n - z i + i n ( a 2 p + 1 一i ) nx i 4 以上两种情况均有l 【( z 1 ) nx 【z 3 ，- 】i 2 n ( x 1 ) nx x 3 1 同样类似于上面分析可得i n ( x 3 ) nx 7 z 1 ，z 2 ) ，叉】i 2 i n ( x 3 ) nx z 1 ，x 2 l ， 则此时a 3 ( g ) i g ( x i ) n 叉i + i n ( x i ) n x z 3 ) ，习i + l n ( x z ) n x 7 z 1 ，z 2 ) ，叉】i i = 1i = 1 32 i ( 啦) n x i + i n ( z dn x z 3 ，x i + i n c z z ) n x x l ，x 2 l i = 1i = 1 3 2 i n ( z dn x l + i n ( x i ) nx ” z 3 ) i + i n ( x 3 ) nx 7 【z 2 l i = 1i = 1 如( g ) 故得, x 3 ( a ) 6 ( a ) 情形2 1 2 ：不存在满足上述情形的3 阶连通子图，存在3 阶连通子图a x l ，x 2 ，z 3 ) 】， 使m a x l n ( x i ) nx z 3 ) i ：i = 1 ，2 ) 2 ，f n ( x s ) nx z 1 ，z 2 】1s 1 同样不妨设m a x l n ( x i ) nx z 3 ) i ：t = 1 ，2 ) = l n ( x 1 ) nx z 3 ) f ，则类似于 上面情形的分析可得，i 【( z 1 ) nx ( z 3 ) ，一】i 2 i n ( z 1 ) nx z 3 取等号当且 仅当u n ( x 1 ) n x z 3 ) 与a x 7 j 中每一点都相邻 若l n ( x 3 ) n x 7 z 1 ，z 2 ) l = 0 ，则有a 3 ( g ) i n ( x 1 ) n x l + l n ( z 2 ) n x i + i n ( x 3 ) n 叉i + i ( n ( x 1 ) un ( x 2 ) ) nx ” x 3 1 i 6 ( g ) 若l n ( x 3 ) nx 7 ( z 1 ，x 2 i = l ，对于 乱) = ( x 3 ) nx 7 z 1 ，z 2 ) ，有以下两种情 况： 当l ( 缸) n 叉i 1 ，则有入3 ( g ) i n ( z 1 ) n 贾l + l n ( x 2 ) n 叉l + l n ( x 3 ) n y i + i n ( z 3 ) n x 7 ( z 1 ，x 2 ，_ 】i + i ( n ( x 1 ) u ( z 2 ) ) nx “ x 3 1 1 6 ( g ) 当l n ( u ) n 叉l = 0 ，此时取3 阶连通子图g 【 z 1 ，u ，z 3 】则此时d ( u ，x 2 ) = 2 ， 则i n ( x 2 ) n 叉i 4 不妨设m a z i n ( z 1 ) nx z 3 1 1 ，l g ( u ) r lx x 3 1 1 = i n ( x 1 ) n x x 3 l ，类似于上面分析可得， j n ( x 1 ) n x z 3 ) ，) - 】i 2 1 n ( z 1 ) n x z 3 ) i i n ( x , ) n x z 3 ) i + l n ( u ) n x x 3 1 1 则有, x 3 ( a ) l n ( x 1 ) n 叉i + i ( 乱) n 又i + l n ( x 3 ) n 又i - 4 - i ( n ( x 1 ) u ( u ) ) n x ” 6 ( g ) ，矛盾，故这种情况不存在 1 3 山东师范大学硕士学位论文 情形2 1 3 ：不存在满足上述情形的3 阶连通子图，但存在连通子图a x l ，z 2 ，z 3 ) 】， 使m a = i n ( z i ) nx z 3 i ：i = 1 ，2 ) s1 i ( 正3 ) nx 7 z 1 ，z 2 ) i 2 此时做类似于情形2 1 1 的分析可得| 【( z 3 ) n x 7 z 1 ，z 2 】，- x l i i n ( z 3 ) n x 7 z 1 ， 沈 j + 2 ，同样可得a 3 ( g ) 2 岛( g ) 。 情形2 1 4 ：对任意三阶连通子图g 【 z 1 ，沈，z 3 ) 】 都有m 口x i u ( z i ) nx z 3 i i = 1 ，2 ) l ，i ( z 3 ) nx z l ，z 2 ) i 1 ，不妨设m a = i n ( z i ) nx z 3 i ：i = 1 ，2 ) = i n ( z 1 ) n x z 3 | 若i n ( z 3 ) nx 7 z 1 ，z 2 i = 0 ，当i n ( z 1 ) nx z 3 ) i = 0 时必有入3 ( g ) 6 ( g ) 否则令 让) = n ( ：r 1 ) nx z 3 ，选取三阶连通子图g 【 【缸，z l ，z 3 ) 】由6 ( g ) 3 仍有 入3 ( g ) 6 ( g ) 若l ( z 3 ) n x 7 z l ，z 2 l = 1 时分以下两种情况 当m i n i n ( z i ) nx z 3 ) i ：i = 1 ，2 ) = 0 ，则此时情形平凡，有入3 ( g ) 6 ( g ) 当m i t , i u ( = i ) n x z 3 i ：i = 1 ，2 ，= 1 ，设 ) u ) = ( n ( z x ) u ( z 2 ) ) nx z 3 ) u ) = n ( z 3 ) c l x 7 【z 1 ，z 2 ) ，则由6 ( g ) 3 ，l ( u ) n 叉l 1 ，又分以下两种情况 若t ，伽不重合，且i u ( v ) n - x l 1 ，i u ( w ) n 叉i 1 ，则a 3 ( g ) 6 ( g ) ，否则 不妨设i u ( w ) n 叉i = 0 若a ( v ，伽) = 2 ，有l u ( v ) n 叉i + i u ( w ) n 叉i 4 ，此 时a 3 ( g ) 6 ( g ) 矛盾，故该情况不存在若a ( v ，w ) 2 ，则存在 0 3 1 ( 叫) ，由 6 ( g ) 3 则i n ( w x ) n 叉i 1 ，对 1 1 同样成立，则此时有入3 ( g ) 6 ( g ) 若t ，伽重合，则若i u ( v ) n 叉i 2 ，则有入3 ( g ) 已( g ) ，否则设l u ( v ) nx i 1 ， 取三阶连通子图g 【 z 1 ，。2 ，v l ，则c z ( v ，z 3 ) = 2 ，l n ( z 3 ) n - x i 3 ，则有沁( g ) 26 ( g ) 情形2 2 ：1 x 7 i = 【竽j ，i x i = 【竽j + 1 情形2 2 1 ：m a z i n ( z i ) n x z 3 ) i ：i = 1 ，2 ) 2 ，且i n ( z 3 ) n x 7 z 1 ，z 2 ) i 2 不妨设m a z i u ( = i ) f i x 6 ( g ) 矛盾故这种情况不存在 情形2 2 3 ：不存在满足上述情形的图，但存在g x l ，x 2 ，z 3 ) 】，使m a x l n ( x i ) n x z 3 ) ：i = 1 ，2 1 l ，i n ( x 3 ) n x 7 x l ，x 2 i 2 做类似于情形2 1 1 的分析可得i n ( x 3 ) n x 7 z l ，x 2 ，叉】i i n ( x 3 ) n x 7 z 1 ，z 2 i 若在n ( x 3 ) nx 7 茁1 ，z 2 ) 中有两个点，使其在g x 】中的度和至多为2 【掣j ， 则有i g ( x 3 ) nx 7 z 1 ，x 2 ，_ 1 l i n ( x 3 ) nx 7 z 1 ，x 2 i + 2 ，可得入3 ( g ) 6 ( g ) 否则在n ( x 3 ) f lx 7 x l ，z 2 ) 中至多存在1 点，使其与x 中至多有个不相邻 的点，设 u ) u w ) = ( n ( x 1 ) u n ( x 2 ) ) n x z 3 ) 若u ，叫不重合，则d ( v ，叫) = 2 ，i n ( v ) n - z l + i n ( w ) n x i 4 ，此时有a 3 ( g ) 如( g ) ， 可得矛盾 若秽，伽重合，由i x 7 l i x l ，a 3 ( g ) 6 ( g ) ，则在x ”中除t ，x 3 至少还有两点， 则此时矛盾 情形2 2 4 ；对于任意三阶连通子图g x l ，x 2 ，z 3 ) 】，都有m a x l n ( x i ) c ：i x z 3 ) i ： i = 1 ，2 ) 1 ，且i n ( x 3 ) f lx 7 z l ，x 2 i 1 此时l x 7 i i x | a 3 ( g ) 6 ( g ) ，则m i n i n ( x i ) f lx 【z 3 ) i ：i = 1 ，2 ) = 1 ，令 m ) = n ( x i ) nx z 3 ，i = 1 ，2 且v i 不能重合，由6 ( g ) 3 ，可得a 3 ( g ) 6 ( g ) 情形2 3 ：i x 7 i 【竽j 一1 情形2 3 1 ：存在三阶连通子图g x l ，x 2 ，z 3 ) 】 使m a x i n ( x i ) nx z 3 ) i ：i = 1 ，2 ) i n ( x 3 ) nx 7 z 1 ，z 2 ) i ，且m a x i n ( x i ) nx x 3 l ，i = 1 ，2 ) 2 ，不妨设 m a x i n ( x i ) nx ( z 3 ) i ：i = 1 ，2 ) = i n ( x 1 ) nx x 3 1 类似于情形2 1 1 的分析可得i ( z 1 ) nx x 3 ，_ 】i 3 1 n ( x a ) nx x z l ，则 此时可得a 3 ( g ) 已( g ) 情形2 3 2 ：不存在满足情形2 3 1 的子图，但存在g 【 z 1 ，x 2 ，x 3 】，使m a z i n ( x i ) n x k x 3 i ：i = l ，2 ) l n ( x 3 ) n x 7 z 1 ，z 2 ) i ，且m a x ( i n ( x i ) n x z 3 ) i ：i = 1 ，2 ) 1 此时l x 7 i 矗( g ) ，矛盾，故此情况不存在 情形1 1 3 ：不存在满足上述情形的图，但存在g x l ，2 ：2 ，2 ：3 ，z 4 扎使m a z i n ( x i ) n x 【z 4 】- i i = 1 ，2 ，3 ) 1 ，i n ( x 4 ) n x 7 x l ，x 2 ，z 3 i 2 此时做类似于情形1 1 1 的分析可得l n ( x 4 ) f a x 7 z 1 ，x 2 ，z 3 ) ，叉i l n ( x 4 ) n x 7 【z 1 ，x 2 ，x 3 l + 4 此时有a 4 ( g ) & ( g ) ，矛盾 情形1 1 4 ：对任意4 阶连通子图g 【 z 1 ，x 2 ，x 3 ，x 4 】都有m a z l n ( x i ) n x z 4 ) i i = 1 ，2 ，3 ) 1 ，l n ( x 4 ) i - ix 7 x l ，x 2 ，x 3 i 1 当i n ( x 4 ) nx 7 z 1 ，, t 2 ，z 3 ) i = o ，m a x i n ( x i ) nx z 4 ) l ：i = 1 ，2 ，3 ) = 0 时显然有a 4 ( g ) 矗( g ) ，否则不妨设m a x i n ( x i ) nx z 4 ) i ：i = 1 ，2 ，3 ，= i n ( x 1 ) nx x 4 l = l u l ，取4 阶连通子图g 【 矗( g ) ，矛盾若d ( v l ，v 3 ) 2 ，此时有l x 7 i i x i ，可得1 j 1 与 t ，硼与u 不相邻，取4 阶连通子图g f 仁1 ，v 2 ，x 2 ，z 4 ) 】，则d ( x 3 ，乱) = 2 ，f n ( x s ) n 叉i + i ( 乱) n 叉i 6 ，此时有入4 ( g ) 矗( g ) 矛盾 若秽1 ，v 2 ，瑚不重合，若有l ( 砍) n 叉i l ，i = l ，2 ，3 。则会有有a 4 ( g ) 2 & ( g ) 。否 则不妨设i n ( v a ) n - 2 i = 0 ，若v 3 与v l ，v 2 中有一点，不妨设其为有d ( v 3 ，v 1 ) = 2 ， 则l n ( v 1 ) n 叉i + l n ( v s ) n 叉i 6 ，此时有入4 ( g ) 矗( g ) ，矛盾否则对t i j n ( v i ) n x 7 z 3 0 = l ，2 ，3 ) ，由6 ( g ) 3 有i g ( w ) n 叉i21 ，则此时有a 4 ( g ) 矗( g ) 情形1 2 ：i x ，l = t 华j t x i 叫华j + 1 情形1 2 1 ：存在4 阶连通子图g f z 1 ，z 2 ，x 3 ，拟) 】满足m a z l n ( x i ) nx z 4 ) j i = 1 ，2 ，3 ) 2 ，且i n ( x 4 ) n x 7 【z 1 ，x 2 ，z 3 ) i 2 ，不妨设m a x i n ( = i ) n x z 4 】i ：i = 1 ，2 ，3 = i n ( x a ) 1 3 x z 4 ) i 类似于情形1 1 1 分析可得i n ( x 1 ) n x z 4 ) ，习i 3 1 n ( z 1 ) n x z 4 ) i ，i n ( x 4 ) 1 3 x 7 z 1 ，x 2 ，。3 ) ，了- 1 l 2 i n ( x 4 ) 1 3x 7 x l ，z 2 ，z 3 ) i ，则可得入4 ( g ) & ( g ) 情形1 2 2 ：不存在满足上述情形的图，但存在4 阶连通子图研( z 1 ，x 2 ，x 3 ，z 4 ) 】， 使m a x i n ( x i ) nx z 4 i ：i = 1 ，2 ，3 ) 2 ，而l n ( x 4 ) n x 7 z 1 ，z 2 ，z 3 ) i 1 类似于情形1 1 2 的分析，若l n ( x 4 ) nx 7 l ，x 2 ，z 3 ) i = 0 ，或对钍n ( x 4 ) n x 7 z 1 ，z 2 ，z 3 ) ，有i ( u ) n 叉i 1 ，则仍有a 4 ( g ) & ( g ) 否则若i g ( u ) n 叉i = 0 ，则 对4 阶连通子图g i x l ，x 3 ，z 4 ) 】，有l n ( x 2 ) n 叉i 4 ，可得a 4 ( g ) & ( g ) ，矛盾 情形1 2 3 ：不存在满足上述情形的子图，但存在g 【z 1 ，x 2 ，2 ：3 ，z 4 ) 】使m 仳 i ( 奶) n x z 4 ) l ：i = 1 ，2 ，3 ) l ，i n ( x 4 ) nx 7 z 1 ，x 2 ，z 3 ) l 2 做类似于情形1 1 1 的分析有，i n ( x 4 ) nx 【z 1 ，x 2 ，z 3 ) ，- 】l i n ( x 4 ) nx 7 z 1 ，z 2 ，z 3 ) i + 2 若m i n n ( = i ) nx i x ，i 且6 ( g ) 3 类似于情形1 1 4 的分析可得入4 ( g ) 矗( g ) 情形1 3 ：1 x 7 i 【芈j 1 情形1 3 1 ：存在4 阶连通子图g 【 z 1 ，2 c 2 ，x 3 ，z 4 ) 】，使m a x n ( x i ) nx 【z 4 ) i ： i = 1 ，2 ，3 】- i n ( x 4 ) 1 3 x 7 【z 1 ，x 2 ，z 3 ) l ，且m a x i n ( = i ) 1 3x z 4 ) i ：i = 1 ，2 ，3 】- 2 ， 不妨设m a x i n ( x i ) n x z 4 】- | i = 1 ，2 ，3 ) = i n ( x 1 ) nx x 4 1 类似于情形1 1 1 的分析可得i n ( x 1 ) nx 【z 3 ) 1 l 4 i n ( x 1 ) nx z 4 ) i ，则此 时可得a 4 ( g ) 矗( g ) 情形1 3 2 ：不存在满足上述情形的图，但存在g 【( z 1 ，2 , 2 ，z 3 ，z 4 ) 】，使m a z i n ( x i ) n x z 4 ) i ：t = 1 ，2 ，3 ) 1 由l x 7 i i n ( x 4 ) n x 7 ( z 1 ，t , 2 ，z 3 ) l 矛盾与假设的情 形所以有i n ( x 4 ) n x z 1 ，x 2 ，z 3 ) ，- z i 4 n ( x 4 ) n x 7 z 1 ，x 2 ，z 3 ) i ，故a 4 ( g ) 矗( g ) 情形2 ：若不存在情形l 中的4 阶连通子图，存在4 阶连通子图g z 1 ，x 2 ，z 3 ，z 4 ) 】， 使z 1 ，z 2 ，x 3 x ，z 4 x 7 ，此时m a z l n ( = i ) n x 囟( g ) ， 矛盾 情形2 2 ：i n ( x 4 ) 1 3x z 1 ，z 2 ，x 3 i 1 若i n ( x 4 ) n x z 1 ，x 2 ，z 3 ) l = 1 ，令n ( x 4 ) n x z 1 ，x 2 ，x 3 = _ 【u ) 若r n a z i n ( = d n x 7 矗( g ) ，矛盾 若三点重合于一点，则当i n ( v 1 ) n x l 3 ，由f n ( u ) d x 1 可得a 4 ( g ) & ( g ) 否则选4 阶连通子图g 【 u 1 ，z 1 ，z 2 ，z 4 ) 】，则同样可分析得a 4 ( g ) & ( g ) ，矛盾 若三点互不重合则n ( v 1 ) ，i v ( v 2 ) ，n ( v s ) , u 不能有重合的，否则会有情形l 情 况出现 当i n ( v i ) n 叉i 1 ，则可得a 4 ( g ) 矗( g ) 否则选取4 阶连通子图g v l ，x l ，x 2 x 4 】 由d ( x 3 ，u ) = 2 则i n ( x s ) n 叉l + i n ( u ) n 叉l 6 则可得x 4 ( g ) 矗( g ) 若i n ( x 4 ) n x z 1 ，z 2 ，2 ：3 ) i = 0 ，若v l ，v 2 ，v 3 重合于一点，当i n ( v 1 ) a x i 3 ，则 可得证否则d 0 3 ，z 2 ) = 2 ，【n ( x s ) n - f i + i n ( x 2 ) n 叉i 6 ，则不妨设i n ( x s ) n - f f 3 ，选4 阶连通子图g 【 u 1 ，x l ，x 2 ，x 4 】可得k ( g ) & ( g ) ，矛盾 若有两点重合，不妨设砚， 0 2 重合，则选4 阶连通子图g f u l ，x 4 ，z 1 ，z 2 ) j ，或 g 【 t 1 1 ，2 ：4 ，x l ，z 3 】类似于上面分析可得a 4 ( g ) 矗( g ) 若三点互不重合，或者i n ( v i ) n 叉l 1 ，或者i n ( v i ) n x ” 观) l 2 ，可得出 k ( g ) 已( g ) 若m 饥 | ( 现) nx z 4 ) ：；= 1 ，2 ，3 = 0 ，类似于上面分析则同样可得x 4 ( a ) 已( g ) 情形3 ：对于a x 7 1 中任意一点至多与g x 1 中两个点相连，不妨设y , 1 ，x 2 x 7 ，z 3 ，y , 4 x ，此时由6 ( g ) 3 ，可得, x 4 ( g ) 矗( g ) ，故定理得证 定理2 5 ：若g 是连通的二部图，且6 ( g ) 5 ，对于使d ( x ，y ) = 2 的点都 有d ( z ) + d ( 芗) 之2 【竽j + 8 ，则g 是a 5 一最优图。 证：由烈g ) 5 ，据定理1 。7 可知a 5 ( g ) 存在有定理1 9 有沁( g ) 6 ( g ) ， 只须证沁( g ) 6 ( g ) 设s 是g 的一入5 一割，x 是g s 中阶数较少的分 支y ，y ，为g 的二个划分，令x 7 = xny 7 ，x = xny 不妨设i x i i x i 则i x l 【华j ，i x 7 i 【竽j 情形1 ：在g 】e e 存在- 5 阶连通子图g 【z 1 ，2 ：2 ，x 3 ，x 4 ，z 5 ) 】，其中z 1 ，x 2 ，x 3 ，2 4 x 芦x h 山东师范大学硕士学位论文 情形1 1 ：i x 7 l = 【华j ，i x i = 【华j 情形1 1 1 ：若存在5 阶连通子图g x l ，z 2 ，x 3 ，z 4 ，z 5 】，满足m a x i n ( x i ) nx z 5 】i ：i = 1 ，2 ，3 ，4 ) 2 ，且i n ( x 5 ) nx 7 x l ，x 2 ，x 3 ，z 4 ) i 2 不妨设m a x i n ( x i ) nx 【z 4 ) l ：i = 1 ，2 ，3 ，4 ) = i n ( x 1 ) nx x s 1 设 n ( x x ) n x z 5 ) = a l ，a 七) 若k = 2 p ，由条件对d ( z ，y ) = 2 的点，有d ( z ) + d ( y ) 2 【掣j4 - 8 ，且i x i = 【竿j 则存在p 对点( a l ，n 2 p ) ( 0 2 ，a 2 p 一1 ) ，( 唧，o t + i ) ，使i n ( 0 4 ) n 叉i + i ( + 1 一i ) n 叉i 8 ，i = 1 ，p 若k = 2 p4 - 1 ，则至少存在一点a i ，设该点为0 2 升1 ，则有i n ( a 2 p + 1 ) nz i 4 ， i n ( a i ) n 叉i4 - l n ( a 2 p + l t ) i 1 叉i28 ，由以上两种情况可得i n ( x 1 ) nx 【z 5 ) ，叉】| 4 1 n ( x 1 ) n x z 5 ) 卜