（运筹学与控制论专业论文）图的某些连通性问题.pdf

6 ,-, 士手 : : 苦 又 定 理3 . 5 设 g 是2 边 连 通 且 极 小 ( k , k 一 1 ) 边 连 通 图 ， ig i = n , n _ k 十 4 , k ? 6 ， 则 e ( g ) = 2 n 一 k 当 且 仅当g- g ., , g z 或g_( 如 图1 ) a 定 理3 . 。 如 果 g 是 2 边 连 通 且 极 小 ( k , k 一 1 ) 边 连 通 图 ， ig 卜n , k ? 4 ， 那 么 : i ) 当 k 一 1 - k 一 1 , 1 5 ib ( g ) 卜k 一 4 , k ? 5 ， 则 e ( g ) 2 n 一 k + 1 。 关 挂 词 : (k / .) 遭、 不 可 分 离 圈 、 极 小 达 , 1) 边 连 通 、 等 价 类 j b 士学二 论天 v 4 ti 1 g r i从 丁 ?丁ti p , a b s t r a c t 少 a ( k ; g ) - c a g e i s a g r a p h o f m i n i m u m o r d e r a m o n g k - r e g u l a r g r a p h s w i t h g i rt h g . a c o n j e c t u r e t h a t e v e r y g - c y c l e i n a ( k ; g ) - c a g e i s n o n - s e p a r a t i n g i s p r e s e n t e d i n 7 . f o r e v e n g , i t i s p r o v e d i n 7 . i n t h e s e c o n d c h a p t e r o f t h i s p a p e r , w e s h o w t h a t t h e s a m e i s t r u e f o r o d d g . f o r a n in t e g e r 1 1 ， t h e 1 - e d g e - c o n n e c t i v i t y a , ( g ) o f g i s d e f i n e d t o b e t h e s m a l l e s t n u m b e r o f e d g e s w h o s e r e m o v a l l e a v e s a g r a p h w i t h a t l e a s t 1 c o m p o n e n t s , i f iv ( g ) i ? 1 ， a n d a , ( g ) = iv ( g ) i i f iv ( g )卜 1 * g r a p h i s ( k ,l ) - e d g e - c o n n e c t e d i f t h e 1 - e d g e - c o n n e c t i v i t y o f g i s a t l e a s t k . a s u f fi c i e n t a n d n e c e s s a ry c o n d i t i o n i s p r o v i d e d i n t h e t h i r d c h a p t e r o f t h i s t h e s i s a s w e l l a s t h e b o u n d o f s u c h g r a p h s w i t h o r d e r g i v e n i s d i s c u s s e d . t h e m a i n r e s u l t s a r e a s f o l l o w s : t h e o r e m 3 . 3 l e t b e a c o n n e c t e d g r a p h , ig i k 一 1 ， t h e n “ b e a m i n i m a l l y (k , k - ) - e d g e - c o n n e c t e d g r a p h i f a n d o n l y i f e a c h o f t h e f o l l o w i n g h o l d s : ) i b ( g ) i k 一 3 ; “ ) ,u ( g ) k 一 !b ( g ) 卜 2 ; i i i ) f o r v e e e ( g ) - b ( g ) ， ,u ( g 一 e ) _ k 一 】b ( g ) 卜i e l l c o r o l l a r y 3 . ， l e t “ b e a 2 - e d g e - c o n n e c t e d g r a p h , ig i ? k 一 1 ， t h e n t h e f o l l o w i n g a r e e q u i v a l e n t : i ) g b e a m i n i m a l l y ( k , k - 1 ) - e d g e - c o n n e c t e d g r a p h ; “ ) ,u ( g ) k 一 2 ， a n d f o r d e “ e ( g ) ，k ( g 一 e ) k 一 ( e l l c o r o l l a r y 3 . 2 l e t “ b e a c o n n e c t e d g r a p h . ig i k 一 1 ， i b ( g ) 卜k 一 3 ， k : 4 ， t h e ni s a m i n i m a l l y ( k , k - ) - e d g e - c o n n e c t e d g r a p h i f a n d o n l y i f a l l c o m p o n e n t s o f g b( ga r e m i n i m a l l y 3 - e d g e - c o n n e c t e d . t h e o r e m 3 . 4 l e t b e a 2 - e d g e - c o n n e c t e d a n d m i n i m a l l y ( k , k - 1 ) - e d g e - c o n n e c t e d i i i 石 贞 士学位论文 s i k sc e r s t h e si s g r a p h , ig 一 n , n : k + 2 , k : 6 ， t h e n e ( g ) 2 n 一 k 。 t h e o r e m 3 . 5 l e tb e a 2 - e d g e - c o n n e c t e d a n d m i n i m a l l y ( k , k - l ) - e d g e - c o n n e c t e d g r a p h , ig i = n , n _ k + 4 , k 2 : 6 ， t h e n e ( g ) = 2 n 一 k i f a n d o n l y i f g = g , , g 2 . o r g , . 。 t h e o r e m 3 . 6 l e t g b e a 2 - e d g e - c o n n e c t e d a n d m i n i m a l l y ( k , k - 1 ) - e d g e - c o n n e c t e d g r a p h , ig 二 n , k ? 4 ， t h e n e a c h o f t h e f o l l o w i n g h o l d s : i ) i f k 一 1 _ 1 ; e ( g ) ， 如 果 v ( g ) 卜1 . 了lesjil 一一 必慈 璧a , ( g ) 但g o l d s m i t h 在文 2 0 1 , 2 1 1 中更早地提出了 此概念， 只是将其称为高阶边连通度而己。 厂义边连通己被许多人研究过 ( 见文【 2 0 一 【 2 5 1 , 3 1 ) 。特别地，如果1 =2，则 r 2 ( g ) = 双g ) 。 讨 论 某 类 图 阶 一 定 时 边 数 的 界 一 直 是 图 论 中 有 趣 的 问 题 之 一 例如 文 4 ) , 5 1 就是研究极小3 边连 通图 阶一 定时边数的界 。本文 第三章 将给出 极小( k , k 一 1 ) 边连 通 图的一个充分必要条件并讨论此类图阶一定时边数的界。 硕士学位: 仑 又 一 第二章 一个关于( k， 动一 笼的猜想的证明 2 . 1 定义及引理 定义2 . ，图g的围长是指g中最短圈的长。 定 义2 . 2 ( k ; r ) 一 田是 指具 有围长8的k 一 正则图， 而(k ; 9 ) jv iii 是指具 有最小 阶的 ( k ; 图。 定义2 . 3 设c是图g的一个圈， 称c老不7 分离0， 如果g - v ( c )仍是连通的。 文 7 中 提出了 下 面的 猜想: . mg 迢一价 ( k; s ) - .r i 刃1 av每一价r曰婚不可 分离mi l = 定理 2 . 1 8 1 若g是简单图， 且v _ 3 , d ?v l 2 ， 则g是h a m ilt o n图。 定义2 . 4设g是 一个 ( k : % ) 一 笼， h是 它的 一个导出 子图 且 其最小度为k - 1 , b是h中 所有度为k - 1 的顶点构成的 集合。对于b上的每一个置换v, 记 d o ( x , y ) = d h ( x , y ) + d h ( a ( x ) , a ( y ) ) + 2 我们称h是g的一 个 特殊子图， 如 果存在b 上的一个置 换， 使 得对所有的x , y ( $ x ) e b， 都 有 “ h ( x , y ) : 9 r a 飞 一 4 且 d o ( x , y ) : s 。 引 理 2 . 1 7 如 果 。 是 一 个 (、 g ) 一笼 ， 、 是 。 的 一 个 特 殊 子 图 ， 那 么 iv ( h ) i ? jv ( g ) i1 2 。 引 理2 . 2 7 设图g的围长g ? 3 , scv ( g ) 且d i a m ( g s ) = d _ 4 为 偶数， g是一 个 ( k ; g ) 一 笼。 则g的 所 有g - 圈 都是 不 可 分离的。 定义 25设g是一个图，我们称竹 g ) 上的一个置换口是一个特殊置换，如果对所有 ( x , y ) 。 e ( g ) , 都 有( 试 x ) ,a ( y ) ) e e ( ( i ) ， 其 中 g c 表 示g 的 补 图 。 引 理2 . 3 设 c : 是 一 个 长 为 g _ 5 的 圈 】 则 存 在 v ( c 8 ) 上 的 一 个 特 殊 置 换 。 骑 石 不 士下二 ; 全 文 , , . , ; a 、 1 、上 、 证 明 : 情 形1 . g = 5 ， 将c ， 的 顶 点 按 顺 时 针 依 次 标 为1 ,2 ,3 ,4 ,5 ， 则 圈1 3 5 2 4 1 是 c 5 . 的 一 个 h a m i lt o n圈，将其记为c 。 情 形2 . g 5 ， 可 直 接 验 证 c 二 满 足 定 理 “ ， 的 条 件 ， 所 以 存 在 c 套 的 一 个 h a m ilt o n 圈，也将其记为c。 对 以 上 两 种 情 形 ， 作 一 个 映 射 a ， 使 得 它 将 c ; 中 的 点 按 顺 时 针 方 向 依 次 映 射 到c 中( 也 按 顺 时 针 方 向 依 次 排 列 ) 的 点 ， 由 定 义 可 知 a 是 v ( c r ) 上 的 一 个 特 殊 置 换 。 引 理2 . 4对于 任 意 路p ( n _ 4 ) ， 必 存 在v ( p ) 上 的 一 个 特 殊 置 换。 证明: 将p的 项 点 沿凡依次 标为1 , 2 , - . . , n . 情形 1 . n = 4 ，令a = ( 1 3 4 2 ) ， 其中 ( 1 3 4 2 ) 是 一 个 循环置 换， 可直 接验证a符合要求。 情 形2 . n 4 ， 用尺十 ( 1 , n ) 表示 一 个 长 为n 且 它的 顶 点 按 顺时 针 方向 依 次 标为 1 . 2 ， 二n 的圈。 由 引 理 2 .3 ， 必存在v ( p + ( 1 , n ) ) 上的一 个 特殊置 换a。 由 定 义可 知二也 是v ( p , ) 上 的 一 个 特 殊置 换。 引 理2 . 5设 g = c g + 凡， g 5 , n y 2 y , 。 用p表 示 x ix 2 . . . x g - 1 路 ， 由 于 9 一 1 _ 4 ， 根 据 引 理2 .4 , 必 存 在v ( p ) 上 的一个 特殊置 换q i 。 情 形1 . g = 吼+ 几， 令 6 ( x ) y l ,x = x g ; x g , x = j; x , x 气1 泛; v i ( x ) ,x e v ( g ) 一 x g ,y i, y 2 flll、 一一 q士宇位论又 i a s i e k %l i i e s i s 情 形2 . g= c x + 几， 令 二 ( x ) y 2 ,x = x g ; x g , x = 为; x , x = y , y 3 ; a l ( x ) , x c v ( g ) 一 x % , y 4 2 , y 3 1 了ijee厄、 - 可 直接按定义验证o是v ( g ) 上的一 个 特殊置换。 ix g 一 艺 几 i g， n 1 ， 示v ( g ) 上的一个置换口 0是v ( g) 上 的 一 个 置 换 ，其中 i = 1 , 2 , . . , n ， 我 们 用q o 2 二 氏表 使 得当x e v ( g , ) ( i = 1 ,2 , . , n ) 时， 有fi x ) = 6 ( x ) 引 理 “ 设 g 一 (又 p (o ) 十 (冗 二1c (a ) ， 其 中 跳w 分 别 表 示 路 和 圈 ， 且 对 所 有 j = l, , . . ;q ， 有 1 ( c ) ? 5 ， 并 且 当 q = 0 , r- 1 时 ， 有 1 ( p (0 ) ? 3 ， 则 存 在 v ( g ) 上 的 一 个 特 殊置换。 证 明 : 如 果q # 0 ， 那 么 对 于 c v ) ， 由 引 理2 .3 ， 分 别 存 在v ( c m ) 上 的 一 个 特 殊 置 换r , ， 其 中 j = 1 ,2 , . . . , q 情 形， . 云 = 、一v ( p ()i ? 4 且 。 ， ， 则 有 v ( p (0 )i 4 ， 此 时 eh q 理 2 .4 , 必 存 在 v ( p ( 0 卜v ( g ) 上 的 一 个 特 殊 置 换o , ， 当q 0 时 ，令。 = q t 7 2 . . r q ， 否 则， 情 形 2 . 艺 二.iv (p _ 4 且 。 ， 记 p( ， 的 始 点 和 终 点 分 别 为 u ;,v , =1 , 2 , . . . , t ， 令v“6 , 。 其中 我 们 通 过 对 所 有 的 7 二 以二 ，., t - 1 ， 在p c。 和 p ( ,. i) 之 间 用 一 条 边(v ， ui + 1 ) 连 接 的 方 式 形 成 一 条 顶 点 数 为 艺 _ , iv (p (i ? 4 的 路 尸 。 由 ” ，理 2 .4 ， 存 在 v (p ) 的 一 个 特 殊 置 换 ， 当 q “ 时 ， 令 q - 6 i z .t 2 . 凡 ， 否 则 ， 令 6 二 2 时 冷 c= c , 几 t 3 一t y ， 否 则 ， 令u = q , c 可直 接按定义验证， 对于 上述情形 l , 2 和3 , q符合要求。 设c为一个长为g的 圈， 其中g为奇数，对于c上 任意 给定的一 点u ， 必定 存在c上 两 点v . * 使 得d , . ( u , v ) = ( g 一 1 ) / 2 峨( u , w ) = ( g 一 1 ) / 2 我 们 称v 和、 为c上u 的 对径点，1 u , v j j r l j u ,w 为c上的对 径偶。 2 . 2猜想的证明 定理2 . 4 如果k ? 3 , g ? 5 为奇数， g为 一个( k ; g ) 一 笼， 则g的 所有的g - 圈 都是不可 分离的 证明:设g是一个 ( k ; g ) 一 笼，记g中所有的g 圈 构 成的 集合为a c ， 令 n s c = mi n i v ( h ) i : h 是 g 一 v ( c ) 的 一 个 顶 点 数 最 小 的 连 通 分 支 。 选 取 一 个 c e a c ， 使 得 g 一 v ( c ) 有 一 个 连 通 分 支 h 满 足 】v ( h ) 卜n s c 。 因 为 d i a m ( c= (g - 1) 2 - c 上 所 有 对 径 偶 的 数 目 = g - 断 言3 如果g ， 仅仅是一 条 路p ， 则1 ( p ) ? 3 ， 或者当1 ( p ) 3时， 存在一个顶点 、e n ( c ) 一 a。 事 实 上， 假设1 ( p ) _ 3 可 知 ， g 一 c o 是 不 连 通 的 ， 并 且 必 存 在 g 一 c “ 的 一 个 连 通 分 支h o ， 使 得 风c h - 恤 v ,咐 ， 但 ly (t l 4 k h ) - u v 叫 i叫 ， 这 与 h 的 选 取 方 法 相 矛 盾 。 现在开 始寻 找一个n试c ) 上的 置 换二， 使 得对于 每个n ( c ) 中 的 坏 偶 x , 对， 都 有 ( ( x ) , q ( y ) 不 再 是n ( c ) 中 的 坏 偶。 情形 1 .如果g 、 仅仅是一条路p且 1 ( p ) _ 1 ; e ( g ) ， 如 果 v ( g ) i 3 , s ce ( g ) 称为 的一 个k 边一1 部创 集， =k 月 r e ( g一 s ) = 1 。 对于极小k 边连通图， m a d e r 和苏键基已分别证明了如下定理: 定 理3 . 1 4 设 “ 是 极 小 k 边 连 通 图 ， 叫一 。 ，k _ 2 , 。 3 k ， 则 e ( g ) k ( 。 一 k ) 且 e ( g ) = k ( n 一 k ) 当 且 仅当g- 凡。 _ * 。 定 理3 . 2 5 设 是 极 小k 边 连 通 图 ， ig 卜n , k 2 , k + 2 _k。 由a , ( g一e ) =k一1 ， 有a , ( g) k。 如 果 .1 , ( g ) k 一 1 ， 则 存 在 t 二 e ( g , 川 k 一 1 ， 使 得 。 ( g 一 t ) = 1 。 于 是 取 “ e t ， 则 w ( g 一 。 一 ( t 一 e ) ) = co ( g 一 t ) 一 / 1 但 t 一 e 卜k 一 2 ， 与 a , ( g一 。 ) = k 一 1 矛 盾， 所以a , ( g) =k。 i i ) = : 0 ”依定义a , ( g) _ k，对h e e e ( g ) , a , ( g - e ) k。若存在 e e e ( g ) , 使 得a . , ( g一 e ) - k 一 2， 则 存 在t 二 e ( g - e ) , it i _ k - 2 ， 使 得 cu ( g 一 e 一 t ) = 1 ， 而 t u ( e ) 1 5 k 一 1 ， 与 a , ( g ) ! k 矛 盾 ， 故 a ., ( g 一 e ) 一 k 一 i ， 对d e 。 e ( g ) 都成立。 定 理 3 . 3 设 是 连 通 图 ， 司? k 一 1 ， 则 是 极 小 (k , k - 1 ) 边 连 通 的 当 且 仅 当 下 列 都 成 立 : ) 1 b ( g ) 卜k 一 3 ; “ ) ,u ( g ) k 一 b ( g ) i 一 2 : “ ) 对 b e e ( g 卜b ( g ) ， 有 ,u ( g 一 e ) “ k 一 !b ( g ) 卜 fe ll 。 证明: 设 是极小( k , k - 1 ) 边连 通图， 则a k _ , ( g) ?k。 假 设 b ( g ) i “ k 一 2 ， 则 可 取 t 二 b ( g ) ， 使 得 国一 k 一 2 ， w ( g 一 t ) = k 一 1 ， 与 r * 一 ， ( g ) ? k 矛 盾 ， 故 】b ( g ) 卜k 一 3 。 假 设 p ( g ) ? k 一 b ( g ) 一 1 ， 则 可 取 s ， 使 得 它 由 b ( g ) 中 所 有 边 及 g 中 某 个 最 大 等 价 类 中 的 k - ib ( g - 1 条 边 构 成 ， 则 囚= k 一 1 ， 且 4 g - s ) = 1 + jb( g j 十 (k 月 班洲 - = k - 1 , 与 兄 * _ ， ( g ) : k 矛 盾 。 因 此 ,u ( g ) k 一 b ( g ) i 一 2 。 假 设 存 在 e e e ( g ) 一 b ( g ) ， 使 得 ,u ( g 一 e ) e , ， 价 ， e * 一 : ， 令 j = ( e ,lra ( g 一 e 一 e e 2 , ., e ) 一 。 ( g 一 e 一 e , e 2 ，二 e ,_ , j ) , i = 1 ,2 , ， 二 ， k 一 1 ) 。 则 t i j = e , lw ( g 一 e 一 e : , e 2 , . . . , e ) 一 。 ( g 一 e 一 e , ， e . . . . . . e ,- , ) ) + 1 ) ， 因 此 冈 = 叫 一 件 / 川 一 川 一 o) ( ( g 一 e ) 一 t ) 一 1 一 1 。 故 可 不 妨 设 j = e i ， 则 由 命 题 3 . 2 , : 只 可 能 包 含 g - 。 的 割 边 以 及 ( e , l a - 。 中 的 边 。 但 由 于 、 ( g 一 e ) - k - ib ( g ) i 一 f e l l 一 ， 所 以 t i _ 2 。 不妨设h 连 通， 则,u ( h ) = 1 且gh- e ) - k 一 】b ( g ) 卜 ie 卜k 一 !b (g ) 卜 1 。 当 ib ( 训 k 一 4 时 ， 有 k 一 b ( g ) i 一 2 ? 2 由 引 理 “ 得 ， / .( g - e ) - 2 显 然 ， i( e ) h 卜1 。 由 于 e o b ( h ) 及 命 题 3 . 4 ， 有 e 。 二 e 。 又 由 命 题3 . 2 i i i ) ， 有b ( g一 e ) c_ e 、 一 ( e ) 二 中 因 此6 - 。 是2 边 连 通的。以 下 证明 : 一 。 是 ( k , k - 1 ) 边连通的。 因为u ( h) _ 2 ， 所以l x ( h一 e ) - 4( 否则， 若u ( h一 e ) ? 5 ， 则 ,u ( h) 2 : 3 ，与i ) 矛 盾) 。由 引 理3 . 1 , gg - 匀 - m a x 逐 d g ) , 仄h - e ) ) - 4 ， 则,u ( g ) ? 2 。 证 明 : 假 设 k ( g ) = 1 ， 则 b e e e ( g ) ， 有 ,u ( g 一 e ) _ 6 ， 则 e ( g ) 5 2 n 一 k。 证明:由于 是极小( k , k - 1 ) 边连通的，所以由命题 3 . 3 存在 的k 边一 ( k - 1 )部割集。 任 取 “ 的 一 个 k 边 一 ( k 一 1 ) 部 割 集 s , 则 囚= k 且 。 ( g 一 s ) = k 一 t o 再 取 e ( g 一 s ) 的 一 个 有 序 边 割 集 分 解 s s z ,., s , ， 则 t 一 n 一 。 ( g 一 s ) = n 一 * + 1 且 s 。 一 * + 、 卜1 由 引 理 3 . 2 ， 对 所 有 的 一 1,2 ，二 。 n 一 * . ，有 s 卜 2 ， 所 以 e (g) - i司 + e = k+iis ,卜 k + (n - k ) x 2 + 1 硕士学位论又 , 1 s 丁 e r s t h e s i s = 2 rz k + 1 - k + 4 , k _ 6 , g ,p . g 2 。 和g , ,( 如 图1 . ) 由 一 个 完 全 二 分 图 k - k . 1.2 = ( u l ,u 2 , .,u - k + l ) i ( vv 2 ”分别与一条长 为k - 2 的路v 2 y : y 2 . .y k - 3 v l , u i y i y 2 . .y k - 3 n - * 十 。 或u i y , y 2 二 凡 一 ， v : 构 成。 定 理3 . “ 设 g 是 “ 边 连 通 且 极 小 ( k , k 一 1 ) 边 连 通 图 叫 = n , n ? k 十 4 , k ? 6 ， 则 e ( g ) = 2 n 一 k 当 且 仅 当 g - g , , g z ,。 或炕、。 证明:设g是2 边连通且极小( k , k 一 1 ) 边连通图且e ( g ) = 2 n 一 k。 从口 肇 石 行 士学 u入 、一 二 假设 s 是g的 一 个k 边一 ( k 一 1 ) 部 割 集， s s ， 二 ， s 是e ( g一 s ) 的 任 意 一 个 次 序 边 $ 11 集 分 解 ， 则 一 。 一 k + 1 , is - k 卜1 且 由 引 理“ . 2 ， 对 所 有 i 二 1 ,2 ,. ., 。 一 k ， 有 is : 2 首先，证明g一s只有一个非平凡连通分支。 情 形1 . 假 设 g 一 s 有 三 个 以 上 非 平 凡 连 通 分 支 ， 则 至 少 还 有 边 集 ss , ( i , j # n 一 k 十 1 ) n -kt t 使 得 is 卜 “ 一 ， 所 以 e ( g ) = is i + 1 is , i 竺 书 k- 3 ) , 3 由 定 理 3 . 的 证 明 过 程 可 知 ， 仅 还 存 在 某 一 个 i, ， 卜 十 ， ， 使 得 is , 一 ， ， 而 对 其 余 的 j ， 1。 ，。 一 十 ， ， 有 : 二 2 。 可 设 以 二!s , 一 e (g ,) 且 i, i2 - 3 由 a ( g 一 s ) = is , 卜2 ， 可 取 e ( h ) 的 次 序 边 割 集 分 解 t , i . . . , t _ k , , ， 使 得 t , 二 e , ， it , 一 2 。 因 为 e ， 一 t , 中 的 边 都 是 h 一 。 的 割 边 1 所 以 t z i = a (g - s - t ,) = 1 0 由 于 e ( g ) = is l + 艺 了 . 11t i - 2 。 一 ， 故 对 所 有 i = 3 , . , 。 一 * (? 4 ) ， 有 囚 一 2 。 因 此