（运筹学与控制论专业论文）2连通图的单圈子图.pdf

摘要 由于树图及邻接树图在通讯网络拓扑结构中的应用 它的相关性质被众多的学 者进行了广泛深入的研究 人们尤其对树图中有k p 悬挂点的支撑树的内插性质产生 了极大的兴趣 c h a i n a n d t l p 6 1 0 1 曾提出过这样的公开问题 如果一个图g 具有圈秩p 且 该图g 有两个分别含m 和 1 个悬挂点的支撑树 帕 则该图g 是否有一个含有k 个悬 挂点的支撑树仰 k 露 c a l l 2 1 和s c h u s t e f l 如分别用不同的办法独立她证明了这样 的支撑树是肯定存在的 后来 l i n l 4 也对上述问题提出了新的的办法 但是他们只证 明了这样的支撑树的存在性 在1 9 8 8 年 k a t h e r i n eh e i m i c h 和刘桂珍 5 j 也给出了上述 问题的详细证明 他们不仅证明了存在这样的支撑树 而且还证明了这样的支撑树的 个数与图g 的圈秩有关 并给出了它的最佳下界 类似树图 6 1 我们可以定义2 一连通 图 7 1 g 的0 一图o g 及邻d 一图a g 图g 的单圈支撑子图s 定义为图g 的支撑树r 再加上 一条边e e g 盼 t4 e 则图g 的o 一图定义为 点集 g 是把g 的所有单圈支撑 予图作为o c g 中的点的集合 边s s7 e g 当且仅当1 e s oe s i 2 类似地 我们 定义图g 的邻d 一图a g 如下 a g 为0 g 的支撑子图 且a g 中有边s s e a g 如 果s s 一 v u w 其中边 v s 边 w s 本文从2 一连通图出发 运用一个树的两个基本圈之问存在圈链这一性质 研究了其 邻国一目弘 g 的结构并得到以下的结果 1 利用2 一连通图g 的邻接单圈支撑子图的定义和支撑树的性质 得到了两个邻接单圈 支撑子图s s 具有同一支撑树这一性质 同时利用归纳假设的方法 证明了图g 中连接 圈g g 的初等罔链的存在性 2 通过分情形讨论以及前面所证明的圈链的存在性 得山了邻0 一图a g 及其导出子 图吲的连通性 由此证明得到定理a 即设s s 为2 一连通图g 中两个单圈支撑子图 则 在 g 中至少有2 一1 条内部不交路连s 和s 这里 是g 的圈秩 3 利用2 一连通图g 的o 一图的连通性质 得出了定理b 即如果一个2 一连通图g 有两个单圈 支撑子图 且这两个单圈支撑子图分别含m 和n 个悬挂点 肼 刀 则图g 至少有2 一1 个 含t 个悬挂点的单圈支撑子图 这里圈秩p i e g i v g 9 i l 其中msk n 不难看出 这里的单圈子图实质上是射影平面上的单面嵌入图 而以上结果是定 理j 5 1 5 1 和定理i 1 在射影单面上单面嵌入图方面的推广 沿着这一思路 我们不难提 出和发现一般曲面上单面嵌入图中相应平行理论和结果 而这些将会为一般嵌入图理 论研究打下基础 关键词 2 连通图 单圈支撑子图s 0 圈 邻0 图 a b s t r a c t t h er e l a t e dp r o p e r t i e so ft r e eg r a p ha n da d j a c e n tt r e eg r a p h w h i c hh a v eb e e nw i d e l y u s e di na n a l y s i so f t h et o p o l o g i c a ls t n l c t u r eo f t e l e c o m m u n i c a t i o nn e t w o r k h a v eb e e ne x t e n s i v e l yr e s e a r c h e db ym a n ya c a d e m i c s e s p e c i a l l y s o m er e s e a r c h e r sh a v es h o w nt h e i ri n t e r e s t s o nt h es u b j e c to ft h ei n t e r p o l a t i o np r o p e r t yo ft h es u b g r a p h si ng r a p hgw i t hko n e v a l e n t v e r t i c e s c h a r t r a n d t l 喇1 0 lp r e s e n t e dt h ef o l l o w i n go p e np r o b l e m l fag r a p hgc o n t a i n sb o t h s p a n n i n gt r e e sw i t hma n dw i t l ln o n e v a l e n tv e r t i c e s m d o e sgc o n t a i nas p a n n i n gt r e e w i t hko n e v a l e n tv e r t i c e sf o re v e r yk m 七 以 c a i l 2 a n ds e h u s t e l 4 3 1i n d e p e n d e n t l y v i a d i f f e r e n tm e t h o d s p r o v e dt h a ts u c hs p a n n i n gt r e e sa l w a y se x i s t l a t e r n 1 4 i p r o v i d e dan e w p r o o fo ft h ea b o v er e s u l t h o w e v e r t h e yo n l yp r o v e dt h ee x i s t e n c eo ft h e s es u b g r a p h s i n 1 9 8 8 k a t h e r i n eh e i u r i c ha n dg u i z h e nl i u l 5 1g a v eas p e c i f i ca n db e t t e rp r o o ff o rt h ea b o v e p r o b l e m t h e y n o to n l yp r o v e dt h ee x i s t e n c eo fs u c hs u b g r a p h s b u ta l s oc o n c l u d e dt h a tt h e n u m b e ro fs u c hs u b g r a p h sw i t hko n e v a l e n tv e r t i c e si sr e l a t e dt ot h ec i r c l er a n ko fg r a p h g a n dt h e yg a v eab e s tp o s s i b l el o w e rb o u n d a r yf o rt h i sn u m b e r l i k et r e eg r a p h l 6 1 w ec a n d e f i n et h e0 一g r a p h0 6 3 t na n da d j a c e n to g r a p ha g o f 2 一c o n n e c t e dg r a p hg au n i q u e c y c l es a b g r a p hso fg r a p hg i st h es p a n n i n gt r e eto fg r a p hg p l u so n ee d g ee e g t h a ti s s t e t h eo g r a p ho fg r a p hg i sd e f i n e da sf o l l o w s a l lt h eu n i q u e c y c l es u b g r a p h s o fg r a p hga r et h ev e r t i c e so f0 g s i d es s e 0 g i fa n do n l yi fi e s oe s i 2 s i m i l a r l y w ed e f i n et h ea d j a c e n to g r a p ha g o fg r a p hg 嬲f o l l o w s a g i st h es p a n n i n g s u b g r a p h s o f o g a n d t h e e d g e s s e a g i f s s 一 v w w h e r eu v s 1 w 隹s i nt h i sp a p e r b ys t a r t i n gw i t ht h e2 c o n n e c t e dg r a p ha n db a s e do nt h ee x i s t e n c eo ft h e c i r c l e c h a i nb e t w e e nt w oe l e m e n t a r yc y c l e so nat r e eo fg r a p hg w ee x t e n d e do u rr e s e a r c h o nt h es t r u c t u r eo f t h ea d j a c e n to g r a p ha f 6 3o f g r a p hga n do b t a i n e dt h ef o l l o w i n gr e s u l t 1 b ya p p l y i n gt h ea d j a c e n t0 一g r a p ha n dt h ep r o p e r t yo fs p a n n i n gt r e eo fg r a p hg w e o b t a i nap r o p e r t yo ft w oa d j a c e n tu n i q u e c y c l es u h g r a p h sw h i c hh a v eas a m es p a n n i n gt r e e a n dt h ee x i s t e n c eo f e l e m e n t a r yc y c l e c h a i n v 2 i ne a c hc a s e b yu t i l i z i n gt h ea b o v er e s u l to fe x i s t e n c eo fe l e m e n t a r yc y c l e c h a i n w e o b t a i nt h ec o n n e c t i n gp r o p e r t yo fa d j a c e n to g r a p ha g a n dt h ep r o p e r t yo fi t sg e n e r a t i n g s u b g r a p hh t h e nw ep r o v e dt h a t t h eo c r r a p h0 g o f a2 c o n n e c t e dg r a p hgi s2 0 1 c o n n e c t e d w h e r e p i s t h e c y c l er a n k o f g 3 b yu s i n ga b o v er e s u l t w es h o wt h a ti fa2 c o n n e c t e dg r a p hgh a st w ou n i q u e c y c l e s p a n n i n gs u b g r a p h sa n dt h eo n e v a l e n tv e r t i c e so ft h e s et w og r a p h sa r em a n dn 伽 一 r e s p e c t i v e l y t h e nt h e r ea l ea tl e a s t2 o l u n i q u e c y c l es u b g r a p h so fg r a p hg w h i c hh a sk o n e v a l e n tv e r t i c e s h e r epi st h ec i r c l er a n ko fg r a p hg p l e g i i y g l 1 f o re v e r y k m s k s n i ti se a s yt os e et h a ta u n i q u e c y c l es u b g r a p hi si nf a c ta o n e f a c ee m b e d d e dg r a p ho nt h e p r o j e c t i v ep l a n ea n ds o t h ea b o v er e s u t sa l ee x t e n s i o no ft h e o r e m l 5 1 5 1a n dt h e o r e m l 6 p 1 a l o n g t h i sl i n ew em a y r e a d i l yp o s et h ep a r a l l e lt h e o r ya n dr e s u l t sf o rao n e f a c e de m b e d d e d g r a p ho ng e n e r a ls u r f a c e t h i sw i l ll a yaf o u n d a t i o ni nt h es t u d yo fg r a p he m b e d d i n gt h e o r y k e y w o r d s 2 c o n n e c t e dg r a p h u n i q u e c y c l es p a n n i n gs u b g r a p h o g r a p h a d j a c e n t o g r a p h 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果 据我所知 除文中已经注明引用的内容外 本论文不包含其他个人已经发表或撰写 过的研究成果 对本文的研究做出重要贡献的个人和集体 均已在文中作了明确说 明并表示谢意 作者签名 奎霹 l 乞 日期 堡翌乙壹选 学位论文授权使用声明 本人完全了解华东师范大学有关保留 使用学位论文的规定 学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版 有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅 有权将学位论文 的内容编入有关数据库进行检索 有权将学位论文的标题和摘要汇编出版 保密的 学位论文在解密后适用本规定 学位论文作者签名 j 血 生 开期 丛丝2 车迅 导师签名 缝 瞒丑啤毕 第一章基本概念及主要结果 图论是组合数学的一个重要组成部分 近几十年里 它已经发展成数学的一个重 要分支 因为图论在其它重要学科领域诸如计算机 运筹学 系统工程以及物理学 电子 学 生物学 化学等方面的广泛应用 现在越来越受到科学界尤其是数学界的重视和关 注 由于组合数学 代数学 拓扑学以及概率方法等的结合 现代图论除了传统的研究领 域外已经发展成为包括代数图论 拓扑图论 随机图论等分支在内的多个领域 促进了图 论的发展 同时 图论的迅速发展也带动了其它学科的飞跃和一些困难问题的解决 例如 计算机理论研究的成熟与完善 有限单群分类问题的解决已经生物d n a 遗传结构的逐 步破译等 而我们对图论问题的研究 是联系数学与数学 数学与其它学科之间的重要 纽带 它能更好地帮助我们理解几何学 拓扑学 曲面以及曲线的一些性质 在图论中 一个图g 的圈秩p 定义为p i e g 卜l v g i i 设丁为图g 的支撑树 我们可 以定义g 的树图r g 如下 v t 6 3 是把g 的所有生成树作为 g 中点的集合 v t p y r g t t e c t g 当且仅当耳t 毋e r 2 而g 的邻接树图t g 定义为双g 的 支撑子图 且t g 中有边r r e t g 如果t t 一口v u w 其中 vel u wg 丁 关于树用及邻接树图的相关性质的研究 吸引了众多的研究者 因为它们可以应用 到通讯网络的拓扑结构当中 人们尤其对树图中有k 个悬挂点的支撑树的内插性质的 研究产生了极大的兴趣 c h a r t r a n d l l p 6 1 0 曾提出过这样的公开问题 如果一个图g 具有 圈秽破且该图g 有两个分别含m 和n 个悬挂点的支撑树沏 h 则该图g 是否有一个含 有k 个悬挂点的支撑树 k n c a i t 2 j 和s c h u s t e r l 3 分别用不同的办法独立地证明了 这样的支撑树是肯定存在的 后来 l i n l 4 也给出了上述结果的新的的办法 但是他们的结 果只是证明了这样的支撑树的存在性 第一事基本概念及主要结果 在1 9 8 8 年 k a t h e r i n eh e i n r i c h 和刘桂珍1 5 1 也给出了上述问题的详细证明 得出这样 的支撑树不仅存在 这样的支撑树的个数还与图g 的圈秩有关 给出了它的最佳下界 同时 得到了许多重要的结果 其主要结果如下 定理1 l m 设r 和r 7 为一个困g 的两介支撑械r t 一 i r 即r rer g 那么 在a g 里 r 和r 在j 习一个圈内 定理1 2 1 5 1 设困g 为圈o 0 芝2 的一个困 边e g h t t a g 且f r 那 么日 a g f 1 是2 一连通的 定理1 3 1 s 4 t 和t 7 为围g 的两个支撑树 eg r e 簪t ut 那么有a g 中的一介困c 包 舍r 和r 7 且 c 一 丁u r l ey 1 t te y 似 g 且e t i 定理i a i s j 设l t 力厨g 的两个支撑拭g 的田秩力p 那么在r g 里 有劲务内部不交路 连接l r 定理i 5 1 5 l 今瓦t 为田g 的支撑树且n f t f r 哺p 为a g 中连接l t 的任一 番魄那么存在一 a t ev p r f t t 这里 有m k 儿 定理1 6 侈i 如果一个舀g 的圃秩 所有两个分别舍m 和2 舍悬矬童的支撑树 r m 那么g 至少有劫个舍 个悬挂点的支撑树 其中t 满足坍 k 兀 由于树是平面上的单面地图脚 即 一个面的嵌入图嘲 本文考虑由2 一连通图g 的 支撑树了 再加上一条边p 即图g 的单圈支撑子图 这里的单圈支撑子图就是射影平面 上1 7 j 的单面子图 来研究图g 的单圈支撑子图的性质 可以预见这对于我们今后研究射 影平而上的单面地图拓扑性质8 l 的应用意义 类似树图我们可以定义2 一连通图g 的 一图9 晒 及辱姻一目弘够 图g 的荜圈支撵子 豳s 定义为图g 的支撑树r 再加上一条边e e g 印s t p 则图g 的0 一图定义为 点 集y 0 g 是把g 的所有单圈支撑子图作为o g 中的点的集合 边s s ee o g 当且 仅当i e s o e s7 2 类似地 我们定义图g 的擘姻一戤 g 如下 a g 为e g 的支撑子 图 且a g 中有边s s7 e a g 如果s s 一 v u w 其中边 v s 边 隹s 本文从2 一连通图出发 运用一个树的两个基本圈之问存在圈链这一性质 研究了其 邻0 一龇 g 的结构并穆到如下结果 第一雾基本概念及主要结果 定理ai t s s 为2 一连通压佑中两个单圈支撑子凰剧在o g 中至少习搴 z o 1 务内郝不 交路粕和s 立t i p a g 的圈裁 定理b 如果一个2 一连通图g 有两个单田支撑子图 且这两个单田支撑子图分别舍铆和1 个 悬挂点 m 1 或q 1 那么s 严s 一而 1 f sq p 是g 的单圈支撑 子图 故在a g 中有圈岱 s l s 2 一 s q i s s q p s 1 含s 与s 从而得证 为了以后 方便 我们记路p 为岱 s l s 2 s 口 s l s 2 若g g 只有一个公共点 n e 必在s 的同一个2 一边连通子图g 7 g c xu g 上 由于i e g i 3 我们记g 中的边依次为 l 一 而 恐 卸旬 坼l 而枷却 其 中p 3 或q 3 那么s i s 一x i 1s f sq 是g 的单网支撑子图 故在月 g 叶i 有圈 s l s s 2 s 口 l s s q p s 1 含s 与s 从而得证 3 若gng 0 则由断言2 2 在g 中有一初等圈链 g c o c l c 2 c b q g 1 该圈链满足 g n c 4 l o 0 fs 七 c i n c o 1 i 一月22 0s j 蔓k 1 且c f 上 只有一条边五不在s 中 1 i t 因为gnc i l o o i d 则c fng l 为一个点 或 者为一条路厶 若c fno i 为一条路 为了方便后面的叙述 我们将该路收缩并记为 第二章主要定理的证明 7 点v i 现记图g 的2 一边连通子图g g c o l os is 并记与啮关联的四条边分别 为田 b i 孙h i 其中边4 j 与边阢 g n g j 而边毋与i 盘 j c j ln g 3 o 茎f 七 如图二所 示 图二 前一条路为s 经路只变换到s 后一条路为s 经路 变换到s 参见图二 现在做如下变换 在圈a 中 按照逆时针的顺序 从边 开始记圈c l 中的边 依次为c l 而 而 g o 坼l 坼p 石i 那么s j s 一麓 1s i s 口 p 均 为g 的单圈支撑子图 显然 p j 岱 s 1 s q s t o 与以 s s q p s 目 p i 9m a s q l s h o 为a g 中的两条内部不交路 i 受e l y o m i 考虑图g 的单圈支撑子图s 把s 暑 分别在圈c f 上从不含 第二章主要定理的证明8 边五逆时锻换到不含边g i 1 2 fs 七 1 从而得到g 的单圈支撑s s e 0 l l g j 并记这一从s 变换到s 的路为p 如图二前一条路所示 由变换的过程知道路只e a g 考虑图g 的单圈支撑子图s b 把s h o 分别在圈g 上从不含边五顺肘 产变换到不含 边虹i 2si k 1 从而得到g 的单圈支撑s s o l 一坼 并记这一从s 变换 到s 的路为q 如图二后一条路所示 由变换的过程知道路最ea g 由变换的过程 易 知a g 中的路p 只的内部点均不相交 图三 前一条路为s 经路一 一 巧 店 变换到s 后一条路为s 经路p p 瑶 戎 变换到s 路p i g 如图三 s 缘一母 f 0 l 妁也是g 的单圈支撑子图 对s 依次作以下变 o u 换 s s g o a o s 吞i 毋一嘶 s t 三 o g f 一嘶 s 委u 一 f s 并把 o ui o u 这一从s 到s 的路记为e x c s 把圈c 0 从不含边口0 逆时针变换到不含边自 再分别把 圈c i 从不含边n f 逆对钟变换到不含边a i s 幻 从而得到单圈支撑子图s7 并记这 第二掌主要定理的证明 9 s 勇j s 的路为只 如图三中的路只 弓 显然 路尸 只e g 同理j 主 啊一b 3 t 0 1 盼电是g 的单圈支撑子图 对s 依次作以下变 l 0 1 t王 换 i s s h o b o s 三 一b i s 王 乜一b d 5 互 o 一轨 s l 并把 1 2 ut 5 u f u 这一从s 到s 的路记为只 对s 把圈c o 从不含边 按顺肘 饺换到不含边p l 再分别 把圈c j 从不含边b i 按顺时针变换到不含边五 1si 向 从而得到单圈支撑子图s 并 记s 到5 的路为咒 如图三中的路只 显然 路只 a g 由此可得至归 g 中含s s 的两条路 p 只u 巧u 只和路尸 巧u 只u 圪 由变 换的过程 知n p 内部点均不交 从而得证 口 引理2 4设2 一连通困g 的圈老如 3 r 边ee 烈g o g 为图g 的邻 一图 点集v i g 且h i s s 是g 的单圈支撑予困且边e s 剧h a g m 是2 一连通图 其 c a g 为邻0 一图a g 中点集 的导出子母 证明 要证日是2 一连通图 则需要证明对任意s s ev t s s7 都有h 中的一个圈包 含s s 用数学归纳法对i s s i 的大小进行证明 第1 步 若i s s i l 且s s e l 一 那么在g 中j 有两个初等圈g 与0 假设旬e c ec 根据g 与g 不同的位置关系来分情形进行讨论 口 若c ln c 2 o 则e l 必在5 的同一个2 一边连通子图g 7 上 其中g 7 如下定义 若 cng 为 一个点 则取g c xuc y 若 e c dn 以c y 0 则取g 为gug 中包含边e l e 的一 个子圈 这里记g 的边依次为e g 7 柏 x 2 卸e l 知 1 x q p 柏1 则s j s 一而 1sj 茎口 p 是g 的单圈支撑子图 若etg 则e s 从而在a g 中有 i 羽 s s l s 2 s 9 i s s g p s 含s s 且边e e s j 1 f sq p 故假设eeg 不妨设e k 2 t p 由于p 3 故一定有一边e g 且矿 su s 令e 龇如果点yg g 7 那么必有一边f 满足f sn s7 日 g 所 以s s e 一厂也是g 的一个单圈支撑子图 令s s q 一蕾 1 isq p 那么 在日 a g h 1 l f 我们有路p l s s s s s o l s 矿一f s 其f f l 所有的内 点都包含边e 以及引理2 3 0 的路矿 其中所有的点都不含e 得到所需要的圈p l 第二章主要定理的证明 故令矿 h v 且点虬y 点集v g 假设在g 中 点h 与边卑 1 矗关联 点v 与边而和矗 关 联 曲 分三种情况讨论 1 a 若边e 与边集蜀 弼 而 恐 五州 p 1 邻接 令s s e 一而 s s 矿一而 s 7 s 一再 s s i s 一而 1s i s r l 或s l f 口 1 那么在日中我们有路p t 岱 s s s 乙 s d l x r s l 一 s s l s 和路危 岱 s s 一 s l s 一毛 s i s s 备l s7 其中路p l 的点均含毛 而 路p 2 的点均不含毛 故p l p 2 为日中含s s 的圈 1 b 若边矿与边集历 e l 孙l 孙和 x q p x t 邻接 则边暑 毛中至少有一条边不为厶不妨设而 e 类似可以证而 p 的情形 令s s e 一而 s 产 s 一而 1 蔓i q 1 可得路p 3 岱 s s s i s 结 合引理2 3 1 中的路p 故得到日中的圈p t p 3 含s s 7 1 c 若e 狂v 且点h 与边集蜀关联 点屿边集局关联 令s s 矿一而 s s 一而 1 fsr 1 s s 一玉卜l 且5 s 并一x i r 1 蔓f q 1 那么在日中我们有路1 4 岱 s s s l s l s s 基l s7 其中所有内点都包含边矿 结合引理2 3 1 的路p 褥到h 中的圈p p 4 仞若g n g o 则由断言2 2 在g 中有一基本圈链连接圈g 与g 该圈链依次为 g c o c l q g c 量 t g 其中满足q n c i l 0 osfst c in c j 0 1 i j k i i 一舅 2 且c 止只有一条边五不在s 中 1sf 妁 由于c fnc i 为一个点或者一条路 若为一 条路厶 为了后面的叙述方便 不妨将路厶收缩 并记点gf ic o l 为点n 类似引理2 3 3 对 该圈链中的边标记 令guc o i g f g f 为g 的2 边连通子图 记与n 关联的四条边分制 为a i 玩毋 h i 其中a i b ie q n g i g f h f c 0 ln g i 0 j 的 若e c f o f t 1 则由引理2 3 3 4 g 中有两条内部不交路p 乃 连接s s 且 p 一 内的各个单圈支撑子图都包含边p 故p p 构成日中含s 与s 的圈 故假设边p c i 0 f 茎k 1 则分以下情况讨论 2 j e g 或者e c v 不妨假设p g 类似可证e g 的情形 边e 在g 中的位置有以 下三种情况 1 e c x 且enc l 0 2 弦 c x 且e 只有一个端点在c i 内 3 弦 gna 现 1 0 第二孝主要定理的证明 在对这三种情况分别进行讨论 2 1 1 若eeg r e nc l o 按照逆时针的顺序记圈g 中的边为 i x l a o 耽 l i 南 6 0 而 a d 并记边集蜀 l x l2 a o 恐 e l2 札l e 22i e l2 x t l x t 2 因为边e c j 不妨假设eee i 2 j 以后 2 1 2 2 1 3 的证明均假设如此 按照逆 时针顺序 记圈c i 中 i 到g o 的边依次为c i l x l 而 g o 一 坼l 孙p j l 则s 产s 五一而 1s f sq p 均为g 的单圈支撑子图 彳艮显然 p t 岱 s i s q 与p 2 岱 s 叮 p s p p i s 计l s 五一 i l o 为a g 中的两条内部不交路 如图四 记e l f o 瓜卜对图g 的单圈支撑子i s s 中的圈g isi sk 1 依次作逆 时针变换 把圈c f 依次从不含边鼻逆时针变换到不含 i 2 g t i 1sisk 1 得到单圈 支撑子图s 岱 u g i d 并记s 到s i 的路为只 显然只 a g 同理 e s e 的 圈c f 依次从不含边正顺时针变换到不含边h l i 1sf k 1 得到g 的单圈支撑子 图s s u 一h i 0 并记这一从s 变换到s 的路为足 最 a g 显然a g 中的 路只 只内部点均不交 吖 圈四 前一条路为s 经路p i p u 巧u 店u 瑶 变换到s 后一条路为s 经路p 成u 瞄u 成u 成 变换到s 7 第二孝主要定理的证明 因为s 恤一嘶 osm st 也是g 的单圈支撑子图 对s 依次作这样的变 t o iti 换 i s s i g o a o s j 互 一口i 一 s j 互淞i n 1 s 互 一n i s 并把 这一从s 变换到s 的路记为巧 同理 因为s 魄一以 0 ms 的也是g 的单圈支 t o ii 撑子图 x c s 依次作这样的变换 l s s 一i o s 暑 臃一岛 s 4 三 一岛 l 烈jl o u t s z o t b t 武 并把这一从s 变换到s 的路记为只 图g 的单圈支撑子图s s 如 图四所示 由变换知只 只也是a g 中的两条内部不交路 x c s 把圈c o 中从不含边伽顺时针变换到不含边 得到s s a o p l 并把 路s 到s 的路记为只 x c s 把圈g 从不含边 顺时针变换到不含边 得到单圈支撑子 图s s 一旬 并把这一从s 到s 的路记为吒 见图四中的巧 咒 因弓中的各单圈 支撑子图均含边6 而只中的各点均不含边岛 f 0 1 0 故只 只内部点不交 考虑s 把s 中的圈c f 1sfs 七 分别做逆时针变换得到s 并把这一从s n s7 的 路记为尸 而x c s 把s 中的圈o 1 茎js 的分别做顺时针变换 编4 n s 并把这一 从s n s 的路记为焉 如图四 记p 只u 只u 只u 弓 和路p 墨u 只u 咒u 只 由 变换的过程及示意图四知p 即为a g 中连s s 的两条内部不交路 2 1 2 若e g 且e 有一个端点在圈c i 内 那么p 4 0 或e b o 不妨设e o o 类似可证 明e b o 的情形 同时假设边 o e l 氩l 边集臣 历t 1 1 2 1 1 所示且假设e e 1 1 2 第二事主要定理的证明 r m 0 0 0 3 了翟孩 x o 图五 前一条路为s 经路p t q u 巧u 弓u 弓 变换到s 后一条路为s 经路p 弓u 只u u 变换到s 如图五 与2 j j 中的路只和哎的变换方式一样 这里先沿路只将s 变换到s s o 一g l i 及沿路呸将s 变换到s s 王u h l i 由前面2 j 珀q 证明知a g 中的路只 最内部点均不交 见图五 此时考虑将s 变换到s 的路只 由于e 0 o 故与 1 c o 的路只变换不同之处是 对s 中的m c o 变换时 先将s 变换到s g o 一 而对其他圈c i c 2 一 a 均类似 1 中 的路只作变换 故得到s 到s 的路玛 s s g o 一1 1 0 s g o 一 g l a l s 壹协一a i g o b o s 而这里从s 交换到s 的路只与 1 中的路只变换方式一 蚓 2i 样 即只 岱 s 一b o s 塞 岛一岛 s 蚤 臃一岛 s 由变化的过程及图五 中的路只 只所示 知a g 中的路e 只内部点不交 x o s 将s 中的圈c 0 从不含边 顺时针变换到不含边 得到单圈支撑予图s s 一 并把这一从s 变换到s 的路记为只 对s 将s 中的圈c o 从不含边 顺时针 变换到不含边 得到单圈支撑子图s s b o p 并把该路记为只 因在变换的过程 中 路 各中的单圈支撑子图的圈g 中均不含边d f 1 f t 而路r 中的各单圈支撑子 图中的圈c 中均含边口f 1 f 幼 易知路只 最是a g 中内部点不交的路 1 3 第二章主要定理的证明 x o s 将s 中的各圈c f 1si 驴从不含边4 i 逆时针变换到不含边五得到s 并把这 一从s 变换到s7 的路记为弓 对s 将s 中的各圈g 1 i 驴从不含边岛逆时针变换到 不含i 蛳 得到s 并把这一从s 变换到s 的路记为只 显然a g 中的路弓 内部点也 不交 所以在a g 中得到两条内部不交路户 p 均含s s 其中路一 只u 巧u 弓u 弓 路 助 e u 只u 圪u 最 2 1 3 考虑边e c onc j 的情形 我们如2 j j 定义a i 岛 毋 h f 及厶 c inc j 1 故ee c o n c i l o 如图六所示 x o 兰o x o i f m 图六 前一条路为s 经路p q u 弓u 乓u 弓 变换到s 后一条路为s 经路p 足u 只u 吒u 最 变换到s 由图入所示 我们可得到a g 中连接s 到s7 的两条内部不交路p t p 其中p 一u 巧u 只u 尸 p n 弓u 只u 吒u 最 而a g 中的路只 1 i s8 解释如下 这里的路p p 2 与 2 1 j j 仁j 刃中的路 最变换相同 即沿路 将单圈支撑子 图s 变换到s t l s 熏u g j 1 沿路最将单圈支撑子图s 变换到s s e 0 5 一h j 1 由图s 变换到s l u g j 1 沿路最将单圈支撑子图s 变换到s 一j 1 由 1 4 第二章主要定理的证明 前面的证明知a g 中的路只 最内部点均不交 而路弓 只也与偿j j j 中的路巧 只变换方式一样 那么单圈支撑子图s 经路巧 s s g o 一 t o s 臼f 一口1 s g j a i s u k i a i s 变换到s 卢 1 2 ul o 町 s 三b 一毋 单圈支撑子图s 经路只 s s h o 一6 0 s z h i b 3 s 王 啊一岛 12钟ij2ui o 却 s 量魄i b i s 变换到s s 圣 啊一b i 由前面的证明知a g 中的路巧 一也 内部不交 而路只 只解释如下 把s 中各圈g 1sf 助依次从不含边a i 逆时针变换到不含 i 左 1sfs 七 得到单圈支撑子图s s 互慨一五 并把该路记为e 把s 中各 圈c f 1sfs 幻依次不含边6 j 逆时针变换到不含i 盘五 得到s s b i f 3 并把该路 记为只 由于变换的过程中均保持各单圈支撑子图中的圈c 0 不变 从而路只中的各单圈 支撑子图不含边n o 而路圪中的各单圈支撑子图均含边4 0 所以巧 只内部点均不交 把s 中的圈c 0 中的不含边 t o 沿圈c o 顺时针变换到不含边p 即得s 并把这一 从s 变换到s7 的路记为j p 把s 中的圈c o 从不含边 沿圈c o 逆时针变换到不含边 得 到单圈支撑子图s 并把该路记为只 由变换的过程及图六 知p 最内部点均不交 故我们可得a g 中连s s 的两条内部不交路岛 易 其中p p ueu 只u 巧 呓u 只u 圪u 由变换的过程及图六 知n p 内部点均不交 类似可 证e 易的情形 2 2 若e e g 1s f 妁 则考虑以下两种情况 2 2 i 若存在某个t 使得e g 但e c iuc f l 1 st 如2 j 中的边4 h i h i g i 的标记方法 对s 中的边作相同标记 并记e 1 f o 彰 五 1 先证e g 的情形 不妨设e n 类似可证p c 且e a t 的情形 由下面的证明可知在a g 中能找到连接s s7 的两条内部不交路p 只u 只u 呓u 弓 p u 只u 只u 最 且p p 中各单圈支撑子图均含边p 其中a g 中的 路只 1 f 8 t d 释如t 如图七 把单圈支撑予图s 中的圈c f 分别从不含边五沿逆时针变换到不含边g f l 1 f k 1 得到s s 研一g i i 并把这一从单圈支撑子图s 变换到s 的路记 为只 路最解释为 把s 中的圈c f 依次从不含边 沿圈o 顺时针变换到不含边h f l 1 1 5 第二掌主要定理的证明 isi l j o 对i i i c 按顺时针的方式变换到不含边缸l 由此得到单圈支撑子 i l i i i l l s s 五一 善 i l 一跏卜显然4 g 中的路只 巧内部点不交 见图七 i 1扭l 旃 图七 前一条路为s 经路p p u 弓u 巧u 变换到s 后一条路为s 经路n 吒u u 吒u 吒 变换到s 路弓解释为 把s 中的圈c f osf 七 1 依次作如下变换 岱 s g o a o s g f 一嘶 s 毋 口f 一以 s g j a i 函一所 0 l a t 1 一 s z g i a i 白一岛 而 i o i o i o k n 一 路只解释为 把s 纠 的网c f o f s t 1 依次作如下变换 s s l 一b o s l t 2 乜一 2 tt 1 2 0 6 j s 曼 鬼一b d g i i 一6 一l s s h i 一 b i g 1 如图七路只 一所 示 显然a g 中的路只 只也内部不交 路只解释为 单圈支撑子幽s 中保持圈c o 不变 依次把圈c i 1sf k j i l 1 时针 变换到不含边五 得到s 而路只解释为 单圈支撑了图s 中保持圈c 0 不变 依次把 圈c i 1sf 七 从不含边6 f 顺时针变换到不含边五 得到s 如图七路只 e 所示 因 1 6 第二聿主要定理的证明 为只中各单圈支撑子图的圈岛中不含边咖 而只中各单圈支撑子图含边n o 故弓 吒内部 点不交 路弓解释为 把s 中的圈c 0 从不含边6 0 逆时针变换到不含边 得到s 而路只解释 为 把s 中的圈c o 从不含边 顺时针变换到不含边 得到s 如图七路弓 所示 显 然4 g 中的路弓 墨也内部点不交 由此得a g 中连s s 的两条内部不交路竹 p m 其中n 一ueu 弓u p h 最u 只u 圪u 只 2 2 国若e g n c o i 1s t s d 则我们可得到a g 中两条内部不交路p 只u 巧u 只u 弓 p n e u 只u 圪u 连接s s 如图八所示 其中a g 中的路只 1sis8 解释如下 吖毛 图八 前一条路为s 经路p 一u 弓u 只u 尸 变换剑s 后一条路为s 经路尸 最u 巧u 吒u 乓 变换到s 记边旬 f o q 五 1 那么路 解释为 把单圈支撑子图s 中的圈c f i f k 1 从 不含姊逆时针变换到不含边肌 使得s 变换到s s 圭鼻 一 kg f li o 1 7 第二事主要定理的证明 而路只解释为 把单圈支撑子图s 中的圈g 1sisk4 l f f 从不含边五顺 时针变换到不含边虹 再把圈c 从不含蛳逆时针变换到不含逆z h l 使得s 变换 到s s 五4 一 h j 1 2 il 钿 路弓为岱 s g o a 0 9o s 丕 靠一a d s v 4 为 s s i l o 一 o s 丕 一 b k s 显然 只 只也内部不交 路巧为先将s 中的圈c o l 从不含边钆t 逆时针变化到不含边厶i 得到s 路圪为先 将彤中的圈c 0 i 从不含边钆l 逆时针变换到不含边 i 仟z u o 6 t 路尸 为将s 中各圈c f os isk i t 1 分别从不含边n f 逆时针变换到不含i 盘石 得 到s 7 而路磁为将s 中各圈c j 0sf t i t i 1 分别从不含边岛顺时针变换到不含 边五 得到s 见图 k 由变换的过程及图八 易知p 只u 只u 弓u 弓 p h g u 只u 圪u 最 为a g 中 连s s 的两条内部不交路 第 步 继续归纳法 假设i s s7 i r 时 均有s s 在日中的同一圈上 现令s s ev i 点 集key 0 g 且 l s s 是g 的单圈支撑子凰且边 s 且i s s i r 很显然我们 需要证对任意的s n j s 或s7 都有一条日一s 日 a g 中的路连s s 现 在假设i s s i 2 且l e 岱 一s 令c f 为s 中新产生的不同于s 中的圈的初 等圈 1s i 2 那么必存在边毋 g n 岱一s 令s f s e 一e l 可知s j v 1 假设 s s r 如果s s l t 则假设s s 2 由于i s s l i l 由前面所证可知在日中有圈包 含s s 1 又因为峪 一s l i r 1 那么必存在一条边ee g l su s 图g p 是连通的且有圈秩p l 1 由 归纳假设 在 g 一曲中有2 一2 条不交路连接s s 且这些子图中均不包含边p 由 于a g 是0 g 的一个子图 由引理2 3 可知 在a g 中有圈c 连接s 与s 且 c 上的其他 点均包含边e 来证明 即o g 中有2 驴一1 条内部不交路连接s s 1 由于p l 时只有p l 3 未证 因此由r 2 开始证 3 令s7 s 呸一旬一e 2