（应用数学专业论文）若干乘积图的消圈数.pdf

摘要 设g 矿 g e g 是一个有限简单无向图 若s y g 且g s 是无圈 图 则称s 为g 的一个消圈集 阶数最小的消圈集称为最小消圈集 图g 的消 圈数就是图g 的最小消圈集的阶数 并记为矽 g 换句话说 图g 的消圈数 g 是指g 中至少要删去的点数 使得余下顶点的导出子图不含圈 本文主要研究若干乘积图的消圈数 由以下三章构成 第一章介绍消圈数问题的一些背景知识及相关的概念 记号和已知结果 第二章研究完全图及笛卡尔乘积图的消圈数 确定了k 口丁 k 口c k 口k k 口k 0 的消圈数 第二二章研究路和圈的义积图只 c 的消圈数 主要结果为 1 对一般的路己和圈c 得到了己 c 的消圈数的一个紧的下界 2 对 些特殊的路已和圈c 得到只 c 的消罔数的准确值 关键词 消圈数 笛卡尔乘积 叉积 路 圈 完全图 a bs t r a c t l e tg 矿 g e g b eaf i n i t e s i m p l e u n d i r e c t e dg r a p h i f s y g a n dg s i sa c y c li 亡 t h e nsi ss a i dt ob ead e c y c l i n gs e to f g t h ed e c y c li n gn u m b e ro fg d e n o t e db y 矽 g i sd e f i n e dt ob et h e c a r d i n a l i t yo fam i n i m u md e c y c l i n gs e to fg i e t h em i n i m u mn u m b e r o fv e r t i c e st h a tm u s tb er e m o v e di no r d e rt oe l i m i n a t ea l lt h ec y c l e si n i nt h i sp a p e r w ed i s c u s st h ed e c y c l i n gn u m b e r so fs o m ep r o d u c tg r a p h s i nc h a p t e r1 w ei n t r o d u c es o m en o t i o n s n o t a t i o n sa n ds o m ek n o w nr e s u l t s r e l a t e dt ot h ed e c y c l i n gp r o b l e m c h a p t e r2d i s c u s s e st h ed e c y c li n gn u m b e ro fc a r t e s i a np r o d u c tg r a p h k 口g m o r es p e c i f i c a l l y t h ed e c y c l i n gn u m b e r so fk f 口丁 k r 口c k 口k a n dk f 口k a r ed e t e r m i n e d r e s p e c t i v e l y i nc h a p t e r3 w es t u d yt h ed e c y c li n gn u m b e ro ft h ec r o s sp r o d u c t 只 c n o fap a t ha n dac y c l e t h em a i nr e s u l t sa r ea sf o l l o w s 1 f o ra na r b i t r a r yp a t h 乙a n da na r b i t r a r yc y c l e c as h a r pl o w e r b o u n do ft h ed e c y c l i n gn u m b e ro f l c i se s t a b l i s h e d 2 f o rs o m es p e c i a lp a t h f 乙 a n dc y c l ec t h ed e c y c li n gn u m b e r so f c 月a r ed e t e r m i n e d k e y w o r d s d e c y c li n gn u m b e r c a r t e s i a np r o d u c t c r o s s p r o d u c t p a t h c y c le c o m p le t eg r a p h 厦门大学学位论文原创性声明 兹呈交的学位论文 是本人在导师指导下独立完成的 研究成果 本人在论文写作中参考的其他个人或集体的研 究成果 均在文中以明确方式标明 本人依法享有和承担 由此论文产生的权利和责任 声明人 签名 濒鼍 脖日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留 使用学位论文的规 定 厦门大学有权保留并向国家主管部门或其指定机构送交 论文的纸质版和电子版 有权将学位论文用于非赢利目的的 少量复制并允许论文进入学校图书馆被查阅 有权将学位论 文的内容编入有关数据库进行检索 有权将学位论文的标题 和摘要汇编出版 保密的学位论文在解密后适用本规定 本学位论文属于 1 保密 在年解密后适用本授权书 2 不保密 请在以上相应括号内打 作者签名 影功亨裤日期 扩叩年g 月2 日 导师签名 日期 年月 日 若t 乘积图的消圈数 第一章引言 本文所考虑的图均为有限简单无向图 用g 矿 g e g 来表示 若 s y g 且g s 是无圈图 则称s 为g 的一个消圈集 阶数最小的消圈集 称为最小消罔集 图g 的消圈数就是图g 的最小消圈集的阶数 并记为声 g 众所周知 一个给定的图g 要消去g 中所有的圈 须去掉边的最小数 目被称为图的圈秩 记作烈g 且夕 g 陋 g 一眇 g i 彩 其中国表示图的 连通分支数 在本文中 我们考虑相应的问题 用去掉顶点的方式消去图中所有 的圈的问题 由消圈数的定义不难看出 图g 中至少要删去矽 g 个顶点 才 能使余下顶点的导出予图不含圈 若用 g 记图g 最大阶导出森林的阶数 则 找到了图的最大阶的导出森林就等价于确定了图的消圈数 且 g 矽 g i g f 于是 这一消圈问题至少要追溯到1 8 4 7 年k i r c h h o f f 研究的成果 当k i r c h h o f f 考虑电子电流电路时 他在文 1 2 中考虑过如何找到图的最大导出树 当时许多 类似的论文考虑如何在图中找到最大导出森林 如 1 6 7 1 0 注意消圈 集有时也被称为反馈点集 见 2 8 1 4 1 5 1 6 1 7 1 8 并有许多重 要的应用领域 如组合电路设计 死锁的预防和程序验证 确定任意一个图的消幽数是一个n p c o m p l e t e 问题 这在文 1 3 中已阐明 事实上 在平面图 二部图 完美图和可比性图 具有一个 口j 迁定向的图 中的 任一类图的消罔数的汁算是一个n p h a r d 问题 因此 本文考虑的是某些乘积 图的消圈数 在文 3 4 5 1 9 2 0 2 1 中得到许多关于消圈问题的结果 文 若t 乘积图的消圈数 2 一 5 9 分别解决了路与路 圈与圈的笛卡尔乘积图的消圈问题 文 2 2 已解决了 路与路的又积图的消圈问题 由此易于提出下面两个问题 完全图与其它基本图 的笛卡尔乘秋图的消圈问题 路卜j 圈的叉积图的消圈问题 本文将在第二 三章 分别讨论这两个问题 以下我们用口 g 与厦g 分别表示图g 的独立数 覆盖数 用k 表示 阶为芒的完全图 用k 表示阶为 l 刀的完全二部图 用k 1 表示阶为疗 l 的星图 下面的结论是显然的 矽 g o 的充要条件是g 是森林 g l 充要条 件是g 至少有一个圈且g 中所有的圈有一个公共的顶点 完全图k 满足 妒 k f 一2 矽 k m m i n 锄一l 刀一1 g 为p e t e r s e n 图时 g 3 引理1 1 设g 是一个有蚓i 条边 i g l 个顶点的连通图 且具有不增加 的度序列矗 矗 霸g i 若矽 g s 则 d 一1 l l g i l i g l 1 f l 推论1 2 吲若g 是一个有蚓i 条边 i g j i g i 2 个顶点的连通图 且最大 度龇咖 g 珐掣 定理1 3 习若g 与日是同胚图 则 g 痧 定理1 4 5 若g 是任意非零图 则矽 g g 一1 弓i 理1 5 2 2 1 若g l g g 2 量g 且矿 g r i 矿 g 2 矽 则 g 芝 g 1 矽 g 2 若t 乘积图的消圈数 第二章笛卡尔乘积图 2 1预备知识 3 一 定义2 1 1 5 1 设g l k e 与g 2 e 2 足两个图 g 与g 2 的笛卡 尔乘积图 c a r t e s i a np r o d u c t 定义为 g 口g 矿 e 其中y k 匕 爿v 巧 且 e u 屹 i y v 且似 e 或 且 v 吃 e 依笛卡尔乘积图定义 可知g i 口g 与g 口g 同构 于是推出下面引理 弓i 理2 1 1 2 2 1 g 口g 2 矽 g 2 口g 1 定理2 1 2 5 1 设g 是任意的图 则2 矽 g 痧 k 2 口g g 厦g 推论2 1 3 5 1 当聊 以 3 时 已口只 竺竺 定理2 1 4 吲当咒 4 时 们口驴卧们口驴阱 矿 只口只 l 们 引一卧 蚍口耻引 觚口只 2 n 1 定理2 1 5 9 3 设m 行 3 且皆为整数 则矿 巳口e 罔 聊 4 刀 4 其它 为方便讨论 我们在作k 口g 的图时只画一个简图 有些边未画出来 若下乘积图的消圈数 4 一 把这样的图称为k 口g 的简图 如图2 1 1 还有1 3 条边未画出来的k 口k 的 简图 设g 和g 是两个图且矿 g 函 y g p v 我们称笛卡尔乘积图g 口g 中由点集 托 v 1 m v 或 导出的子图为g 或g 的第f 个拷贝 并记为g 或g i 同时g 口g 2 中的点 将简记为1 如图2 1 1 中较大的黑点 用1 来表示 若g 2 中的点u 与1 相邻 则称g 与g j 相邻 相应的若g 中的点 与 相邻 则称g 与g 相邻 在g 口g 的消圈集中的点 我们 用较大的的黑点 来表示 当g 口g 的消圈集的阶数较大时 我们用小空 心圆点来表示除去消圈集后余下的点 图2 1 1k 3 口k 4 的简图 2 2主要结论 io f 1 定理2 2 1 当丁表示任一树时 矽 k 口丁 丁 f 2 u 7 1 0 一2 f 3 证明 当t l 时 k 口丁 矽 7 0 现设t 2 且s 是它的一个最小消圈集 设s 为s 在t 的第一个拷贝 丁1 上的 投影 即 s p l y 喊v s 对任一 e sn p i f v y 匕 j 矽 否则v l f 驴v 2 v 2 将构成一个圈 即 边 y v l 和 若下乘积图的消圈数 1 至少有一条被s 覆盖 这说明s 是丁1 的一个覆盖 由此 f 5 k 口丁 l s l p l 丁 另一方面 注意到丁1 的任何一个覆盖也一定是k 口丁的一个消圈集 由此 矽 k 2 口丁 丁 如图2 2 1 5 一 图2 2 1 k 口丁其中l 矿 丁 l 6 下设t 3 易见k 口丁中k 的任何一个拷贝与消圈集有至少f 一2 个 公共点 冈此 矽 墨口丁 f 一2 旷 丁 i 下面对妙 丁 j 归纳 当l 矿 丁 i l 时 k 口丁 妒 k f 一2 结论成立 假设妙 丁 i 2 刀时 k 口丁 玎o 一2 l 矿 r i f 2 结论成立 现设矿 丁 f 2 以 1 任取k 的对应于t 的一个一度点1 的拷贝 不妨设它是第一个拷贝k 则k 口丁一k k 口 丁一v 由归纳假设 矽 k 口丁一k k 口 丁一1 o 一2 以 设s 是k 口丁一k 的一个最小消圈集 则如前所述 与k 相邻的那个k 的 拷贝 不妨设是k 与s 至少有f 一2 个公共点 换言之 k 至多有两个点 不在s 中 若k 恰有两个点v y 不在s 中 令 y k 如 v i 其中 七 f 易验证su 矿是k 口丁的一个消圈集且i su 形i f 一2 刀 1 若k 中 没有或只有 个点不在s 中 则任取 y k 妒 卜 2 显然su 是k 口丁 的一个消圈集 若干乘积图的消圈数 推论2 2 1 若只表示 条路 则 k 口e 觑只 匕 1 0 h o 一2 f l f 2 f 3 6 一 l of 1 推论2 2 2 若k b 表示一个星图 则矽 k 口k 觑k 1 f 2 l 1 o 一2 f 3 f o f l 推论2 2 3 若g 为森林 则矽 墨口g g f 2 l i g l f 一2 f 3 定理2 2 2当刀 3 时 则矽 k 口c 证明 当t 1 时 k 口c c l f l f 2 为偶数 f 2 z 为奇数 3 现设t 2 情况 以为黻舭 呱 可等爿 爿小 纠c 依推论 1 2 另一方面 在k 口c 中存在一个阶为f 兰 l 的消圈集 和l i v 3 一 y l 珂为偶数 如图2 2 2 k 口c s 图2 2 2k 2 口c 8 劲 1 i 1 1 i 一 i r 若干乘积图的消圈数 7 一 情况2 刀为馘舭 降掣1 降m c 依推论 1 2 另一方面 在k 2 口c p l i v 3 v 俨 k 为奇数 如图2 2 3k 口c 图2 2 3k 2 口c 7 综上 当t 2 时定理得证 下设t 3 一方面墨口c 中有胆列不相交的k 的拷贝 贝0 矽 k 口 g 刀 f 一2 另一方面 每列k 的拷贝所含的圈消完后余点有2 个 余点取 法如下 情况1 当 1 m o d o 1 时 第 f 一1 矗 后 磊 o 办 z o 尼sf l 后 z 列取余点为心 f 1 枞 1 m 1 情况2 当 z 三1 m o d o 1 时 除第 z 列的余点取为1 吃 外 余下刀 一1 列中的第 g o 1 五 尼 j l l 0 办 z o 尼 f 一1 七 z 列取余点为v f 1 枞 f 1 柑 综上 当t 3 时 以上二种取法得到的所有余点导出图皆不含圈 所以 k 口c 刀 f 一2 如图2 2 4 k 5 口c 9 的简图 若干乘积图的消圈数 j fi 图2 2 4k 5 口c 的简图 定理2 2 3 矽 墨口k 段f 一2 1 胛 f 一2 f 疗 1 f 刀 2 f 以 1 证明 当t l 1 时 矽 k i 口k i 矽 k 1 0 8 一 现设t 刀 2 首先当t 甩 2 时 k 2 口k 矽 c 4 l 其次 当t2 疗 3 时 一方而在k 口k 中有f 行不相交的e 的拷贝 则痧 k 口 墨 f o 一2 但在同一行及同一列的任意两点都是相邻的 由此得到一个含2t 个点及2 t 条边的余点导出子图 冈而 一定含有罔 这说明矽 k 口k f o 一2 另一方面 在k 口k 中存在一个阶为2t 一1 的余点集 l l v i 2 一 1 v 书 1 2 肌 f 如图2 2 5 所以 定 口 k f f 一2 l 图2 2 5k 口k 的简图 下设t 姐 1 首先当船 1 时 k 口k i k f 一2 其次当聆 l 时 一方面文 口k 中共有玎列不相交的k 的拷贝 则痧 k 口k 刀o 一2 另一方面 每列k 的拷贝去掉f 一2 个点后 共有2 疗个余点 当取余点为 若下乘积图的消圈数 9 一 v l l v y 2 屹 2 l 时 余点形成一条胁m 跏 路 所以 k 口 k 门 f 一2 如图2 2 6k 8 口k 6 的简图 图2 2 6 k 口k 的简图 p k m 试 m l 刀一l f l 定舭2 川c 叩 竺嘿z 2 善l 刀 m m 一1 疗一i f 3 z f 一2 f 4 证明 当t 1 时 矽 k l 口k 矽 k m i n 锄一l 刀一1 现设t 2 情况1 当m i n 妇 z 1 时 不妨设聊 1 则矽 k 口k h l 2 1 一1 l 依推论2 2 2 可得 情况2 当m i n 如 刀 l 时 不妨设m i n k z m 1 一4 方面 k 口k 中存在一个阶为2 2 1 l k 口k 中有2 行不相交的k m 的拷贝 则 k 2 口k m 2 m i n m l 甩一1 2 所一1 的消圈集 l l y l 2 城 y 枷 叱 i 1 屹 卅 1 1 露 m l f 研一1 另一方面 此 消圈集的阶数最小 事实上此时的余点导出子图为阶数最大的一颗树 假如在此 消圈集中还可以再减少某一个顶点 且由于这个顶点的度至少为玎 聊 1 则使 得增加一个点后的余点导出子图的边数不少于顶点数 于是余点导出子图含有 圈 矛盾 如图2 2 7k 口k 的简图 图中较大的的黑点 表示消圈集 中的点 小空心圆点来表示除去消圈集后余下的点 若t 乘积图的消圈数 图2 2 7k 2 口k 4 5 的简图 综上 当t 2 时定理得证 再设t 3 情况l 若m i n m 刀 l 不妨设聊 1 在k 3 口k 中有 l l 列不 相交的k 3 的拷贝 则 托口k 栉 1 另一方面 存在一个阶为刀 1 的消圈 集t p 1 1 屹 v 弦 y y 1 2 刀 所以 矽 k 3 口k 1 z l 刀 l m i n 垅一1 刀一1 情况2 若m i n 锄一1 刀一1 o 为了讨论方便 不妨设m i n 扣一l 行一1 聊一1 0 k 3 口k 中有m l 列k 3 的拷贝且有3 行k m 的拷贝 要消去k 3 口 k 删中的圈 须先消去巧与k 洲的拷贝中所含的圈 则存在 个阶为 m 咒 m i n 如一l 靠一1 的消圈集s p i l v i 2 v i m y 2 m 1 y 2 m 2 1 2 m n v 3 l 1 3 2 b m i j 用反证法证明s 为阶数最小的消圈集 假设还存在一个比s 的阶小一的消圈集s 因为墨口k 舢中每列有e 的 拷贝所含的三圈 且每行有k 的拷贝中所含的圈 于是只能从s 的m 1 个点 v l l y i 2 v 咖一 中少任何一个点 不妨没u 从而第一 三行的余点中分别有 一个星图k 且这两个星图可形成有公共顶点v 的圈 这与假设矛盾 所以s 为阶数最小的消罔集 从而 k 口k m 聊 力 m i n 协一1 刀一1 如图2 2 8k 3 若干乘积图的消罔数 口k 3 4 的简图 壬 壬 王 王王王王 图2 2 8k 3 口k 3 4 的简图 下设t 4 k 口k 巾有垅 刀列不相交的k 的拷贝 则矽 k 口 k m 1 o 一2 另一方面 存在 个阶为2 研 1 的余点集s 1 i v 1 2 1 r 1 i l 1 r l v r 2 卅 1 肼 i l v l m 2 1 l 卅圳 2 如 i 2 册 2 y 2 加圳 于是消圈集的阶为 m 玎 o 一2 即矽 k 口k m 1 o 一2 如图2 2 9k 5 口k 4 5 的简图 圭壬王圭圭圭圭圭圭 图2 2 9 髟5 口k 4 5 的简图 第三章叉积图 3 1 预备知识 定义3 1 1 例 设g e 与g 砭 最 是二个图 g 与g 2 的叉积定义为 g g y e 其中矿 v 刊v k 且 e y 1 v v v 矿 e 且 v 1 e 从定义可知g l g 与g g 是同构的 于是可得如下引理 引理3 1 1 2 2 1 g i g 2 矽 g 2 g 1 若t 乘积图的消圈数 1 2 设g 与g 的点集分别是色 吲j p y v 吲j 那么我们用v 搿 表示g g z 中的点 v 又积只 c 是圈长为6 的圈 一个较复杂的例 了 如只 c 见图3 1 1 它与图3 1 2 同构 对比这两个同构图 可知后者更简单 图3 1 1 只 c 5 图3 1 2 只 c 的同构图 引理3 1 2 2 2 1 若g 日是连通的 则g 与h 都是连通的 引理3 1 3 9 1 设 辞 x 6 y 是g 日的点 且p 是g 中连接口与6 的一条路 q 是h 中从x 至咿的一条路 假设i e p i i e q l 是偶数 那么在g h 中存在一 条从 口 x 到 6 y 的路 定理3 1 4 9 1 设g 与h 是至少有一条边的图 那么g x 何是连通的当且仅 当g 与h 是连通的 且它们中至少有一个非二部图 若g 与h 都是连通的二 部图 则g 何恰有二个连通分支 引理3 1 5 叉积图巴 c 聊 3 咒 3 若刀 2 七 1 尼 即 l 为奇数 则只 e 是连通的 若刀 2 尼 后 j i 1 即 l 为偶数 则只 e 恰有二个连 通分支 此引理由定理3 1 4 易证 当刀为偶数时 为了区分己 c 的二个连通分支 记含v u 的连通分支为瓯 另一个连通分支为g 为了便于讨论艺 c 的消圈数 当以为奇数时 我们可以画只 c 的同 构图 当玎为偶数时 g 与g 一j 构 我们只画己 c 的一个连通分支g 便 可以讨论己 c 的消圈数 若丁乘积图的消圈数 3 2 主要结论 1 3 栅工尚况趟嘶m 印 胃 证明 记己 c g 矿 e 其中矿 v 爿v 已 v c j d i v 2 z 2 历玎一2 2 4 4 垅刀一4 以 2 旧 可得蚓 2 垅力一2 刀 依 q e 矿 推论1 2 得 觚嵋 f 堕等型1 掣1 0 下设 l 2 后 七 七 1 己 c 有二个连通分支g 与g 6 且可推 得g 与g 同构 于是在g 中共有等个点 其中有刀个点的度数为2 其余 点的度数为4 则等个点的度数之和为2 l 4 等一刀 2 m 刀一2 n 从而g 中 共有m 刀一 l 条边 于是 g m 一等 l h 朋嚣一2 刀 2 6 g g g 2 矽 g 2 半 故 综上 定理得证 定 2 螂吲叫糊删c 吲 锃竺三等 证明 g 是 1 个点 则 只 e 0 当玎为奇数时 c 是一个 若t 乘积图的消罔数 幽长为2 n 的幽 则矽 c 1 当n 为偶数时 只 c 有 个幽长皆为咒的 圈 且这二个圈是不连通的 则矽 墨 c 2 定理3 2 3 当以 3 时 矽 只 c 证明 当以为奇数时 下面对门归纳 z 2 后 尼 七 1 刀 2 七 1 后 当 l 3 时 由于 c 3 同构于3 个首尾相接的四圈 如图3 2 1 它与图 3 2 2 同构 在归纳证明过程中我们把只 c 这一复杂图同构于以个首尾相接的 四圈 如图3 1 2 c 5 的同构图 则 只 c 3 2 纠 图3 2 1 只 c 3 的j 一构图 图3 2 2 只 c 3 现设刀 2 后 l 尼 尼 1 结论成立 且i j b c 川 型尹1 七 l 下设玎 2 七 3 岛 露 1 b c 2 m 比只 c 2 m 多二个相接的四圈 蝴只 h 讲2 竿 o 当甩为偶数时 只 c 有二个同构的连通分支g 与g 且每个连通分支 有量个首尾相接的四圈 从而每个连通分支消罔数为 三 则 矽 只 c 2 g 2 三1 若干乘积图的消圈数 方面 定理3 2 4 当以 3 时 只 c 莩1 脚 且例c m 础 莩 脚川且删c 2 m 2 脚心喇 2 降 一池础m 础 1 5 证明 当以 2 七 且甩 1 m o d 3 时 一方面 矽 只 e 尘 另一 情况1 刀暑o i n o d 3 即只 c 6 3 存在阶为 莩 f 半卜椭消圈蛾 川 一川剧胚2 u p j v 6 up 舻 j f 一 屹 6 l 2 f 此消圈集的点不是只 c 9 同 构图的点 而是只x g 图的点 以下消圈集的表示类似 如图3 2 3 只 g 的同构图 图3 2 3 只 g 的同构图 情况2 l 三2 m o d 3 即只瞩 存在阶为 莩 掣卜圳澜集 如 v v 血 v 斯蜘 v 州川v 别 p 加 u k v 2 v 细小v 翩 v 3 6 m 1 3 6 m i 聊 川 如图3 2 4 只 c 的同构 若 下 乘积图的消圈数 图 图3 2 4 只 c l l 的同构图 综上两种情况 可得结论成立 现设 l 2 j i 1 且刀量l m o d 3 即刀 6 l 一方面 只 c 6 f l 中存 在一个阶为4 2 矽 只 e 矽 只 c 6 产1 4 1 的消圈集 p t 5 v 埘 v 6 一 l f z l f u y 6 f v 6 卜 z f u p 2 v 6 j up y p v 却 b 砌 屹驯一4 v 6 一 l m z 一1 聊 另一方 面 此消圈集的阶数最小 事实上此时的余点导出子图为阶数最大的一颗树 假 如在此消圈集中还可以再减少某一个顶点 且由于这个顶点的度至少为2 则使 得增加一个点后的余点导出子图的边数不小于顶点数 于是余点导出子图含有 圈 矛盾 故 只 c 4 z 2 如图3 2 5 只 c 的同构图 图3 2 5 只 c 7 的同构图 再妊2 心础 卜抵纰嵋脚f 竿1 2 f 孚 另 一方面 情况1 当刀兰l m o d 3 即刀 6 4 时 只 g 巾存在阶为 2 里 笋1 4 4 的消圈集 且它的二个连通分支g 与g 同构 则g 口中存在 阶为2 2 的消圈集 v 却 v 川 i m z m u 若t 乘积图的消圈数 札 1 匕 6 f 小 v 6 p f 如图3 2 6 只 c 的一个连通分支g 图3 2 6 只 c o 的一个连通分支e 情况2 当刀兰o m o d 3 即嚣 6 z z 时 只 c 6 中存在阶为 2 里 1 4 2 的消圈集 且它的二个连通分支g 与g 同构 则g 中存在 阶为2 l 的消圈集p v 斯 v 川一 l m 一l 所 u v 引 u 札 1 v 6 f 小 6 一 p 一1 f 如图3 2 7 只 g 一个连通分支g 口 图3 2 7 只 c l 一个连通分支g 口 下设疗 2 尼且刀兰2 m o d 3 耳f j 刀 6 8 一方面 只 c 6 8 中存在一个 阶舢删纰嵋脚降 2 f 孚h 半卜 艄瞧 它的其中 个连通分支瓯中存在一个阶为2 4的消圈集 p up u 妒 y 向 屹 忙 1 u 3 屹加巾 吃 6 k 聊 另一方面 此消圈集的阶数最小 证明它 阶数最小与只 c 6 l 的证明同理 故 只 c 6 m 4 8 如图3 2 8 只 c 的 一个连通分支g 若下乘积图的消圈数 图3 2 8 只 c 的一个连通分支g 口 定理3 2 5 跏弱吼烈酗g 卜t 2 f 半1 f 力 1 刀 2 忌 1 后 栉 2 七 后 证明 当聆 2 露 1 后 时 一方面 矽 只 e f 兰 z 1 2 尼 2 另一方面 只 c 中存在一个阶为2 是 2 的消圈集 p m y 御 u p 匕盈 v m 一 is 七一l i p 3 2 匕盈 v 3 2 七一2 ls 露一l z j 和 1 y 2 f v 础 p 七 f 如图3 2 9 只x c 同构图 图3 2 9 只 c 的同构图 现设以 2 惫 七 1 时 一方面 粥瞩脚 半 2 竿卜化 另一方面 g 口中存在阶为七 1 的消圈集和 v 3 v 5 v 似一 v m v 似 如图 3 2 1 0 忍 c 8 的 个连通分支g 图3 2 1 0e c 8 的一个连通分支g 若下乘积图的消圈数 定理3 2 6 当以 3 时 e 2 爿 2 俎例c m 础 2 肾 删姐例c 删 愕1 1 t 删川且2 例c 删 f 掣1删川且2 例c 一 证明 当刀 2 尼且甩毒1 m o d 3 时 即门 6 4 一方面 圪 c 6 4 中 存在一个黼 啾只吲 2 f 半1 2 阵1 2 舢消圈 集 它的其中一个连通分支g 中存在一个阶为4 z 4 的消圈集 情况1 当疗 4 时 消圈集为以 l v i 心 2 v 易验证此消圈集的阶数 最小 如图3 2 1 l 圪 c 4 的一个连通分支e 情况2 当刀 4 时 消图集为 k v 斯 h k 一l f u p 6 k 一 v 6 9 o u p v 加 v 州 i 加 聊 up v v 川i u 以 l v 6 f 柑v 驯 如图3 2 1 2 只 e m 的一个连通分支e 另 方面 c 6 m 的一个连通分支q 的此消圈集的阶数最小 事实上此时的余点导出 图为阶数最大的一颗树 假如在此消圈集中还町以再减少某一个顶点 且由于这 个顶点的度至少为2 则使得增加 个点后的余点导出图的边数不少于顶点数 于是余点导出图含有罔 矛盾 故 只 c 叭 8 8 可得结论成立 若干乘积图的消罔数 图3 2 1 1 图3 2 1 2 咒 c o 的一个连通分支g 现设刀 2 七且 z l m o d 3 即 l 兰0 m o d 3 或门三2 m o d 3 情况 l 妃吲 2 当以兰0 m o d 3 时 半 2 f 掣 6 ll 3 为射 l 的消圈集 即刀 6 砸 一方面 2 4 z 1 另一方面 在g 中存在一个阶 p 2 4 1 4 4 v 2 6 4 1 4 6 f 4 2 6 一2 1 4 6 一2 i 一l f j up 2 4 1 4 4 v 2 6 4 1 4 6 f 4 2 6 一2 1 4 6 一2 fsz 一上 f v j u 和 6 一 u p 川 y j v 加 v 砌 i 一 y 州一 v h i 聊 一l m 见图3 2 1 3 只 c 的一个连通分支g 情况2 纰瞩 2 图3 2 1 3 c 1 2 的一个连通分支g 当刀三2 m o d 3 时 即以 6 2 一方面 2 刀 1 3 2 4 z 2 另一方面 g 中存在一个阶为4 z 2 的消圈 集p j v 纠 v y 屹川一 屹州一 l m 一1 聊 u p 川 uk p 4 1 4 v 6 巾屹血 1 6 一 6 一 i 一l f 如图3 2 1 4 只 c 8 的一 个连通分支g 若下乘积图的消圈数 型 图3 2 1 4 只 g 的一个连通分支g 综上两种情况 当 l 2 七且刀 l m o d 3 时 定理得证 再设 z 2 七 l 且2 2 三l m o d 3 即刀 6 5 一方面 只 c 6 中存 在一个阶为8 8 乞 c f 4 n 1 3卜川的消圈集 以 l v 3 2 v 3 6 l 1 3 6 m 2 v 3 6 i 3 6 2 l 卵 聊 jn l v 3 2 v 3 6 棚 l 1 3 6 珊 2 v 3 6 i 3 6 2 1 7 卵sf 聊 v u p 5 1 y v 5 州 5 2 1 5 6 l v 邓m i f f u 4 5 叱 6 f 6 f v 6 6 i f f u v v 州 v 柙 y 剧川v 纠 i 另一方面 此消圈集的阶数最小 证明它阶数最小与只 c m 的证明同理 如 图3 2 1 5 只 c l il j 构图 图3 2 1 5 只 c l l 的同构图 下设甩 2 后 1 且2 玎 l m o d 3 即2 z 三0 m o d 3 或2 疗兰2 m o d 3 情况 l 娥 3 f 当2 刀三o m o d 3 时 即刀 6 十3 4 6 3 1 8 5 另一方面 只 一方面 c 叭3 中存在一个阶为8 5 的消圈集 知 v v 却 v 却 v 州小v l m 2 z 聊 u 扣 州 u 若 t 乘积图的消圈数 l 1 i v 3 f 小v 3 f l 一 1 剧小k 澍 扛 2 f 如图3 2 1 6 只 c 的同构 图 图3 2 1 6 只 g 的同构图 情况 2 纰 当2 刀兰2 m o d 3 时 4 6 7 1 8 1 0 的消圈集 3 即刀 6 7 一方面 8 1 另一方面 冗 c 6 m 中存在一个阶为 0 3 6 v 5 6 v 3 6 1 3 6 v 5 6 i f 莩 半卜川的消憔 u y 舢小 v 州 f f u 和 v 州 v 州 u 9 v v j v j v 别一 v 6 一 1 一l u p 2 m 6 f 一 陋 3 一2 办 u 舻 脚 1 6 一 i f 一2 f u 和5 3 v 52 m 5 6 i l 厂 3 一l r 如图3 2 1 8 弓 c l 的i 一构图 图3 2 1 8 弓 c 的同构图 另一方面 此消圈集的阶数最小 事实上此时的余点导出图为阶数最大的一颗树 假如在此消圈集中还可以再减少某一个顶点 且由于这个顶点的度为4 则使得 增加一个点后的余点导出图的边数不小于顶点数 于是余点导出图含有圈 矛盾 莩莩降 若干乘积图的消圈数 故 c 弓 c 掣1 z 3 习已设甩 2 七 l 且刀 l m o d 6 即刀三3 m o d 6 或刀三5 m o d 6 情况1 刀量3 m o d 6 即疗 6 3 一方面 们 莩 f 个阶为l o 6 的消圈集 5 6 3 1 3 1 l 6 另一方面 弓 c 中存在一 和2 吃 6 f 3 2 6 3 i f f u 如 2 v t 6 3 u p 妒 v v 剧i f f j up p 屹加 v 别 厂 z up 纠 u 札妒 如 屹川i up 2 v 埘 v 舶肛 3 j l l u p 5 3 v 5 2 p 3 1 5 1 6 3 i p 3 z p p 5 3 v 5 2 p 3 1 5 6 3 i ps 列 p j 如图3 2 1 9b c 9 的同构图 图3 2 1 9 弓 c 的同构图 情况2栉基5 m o d 6 即行 6 z 5 一方面 妃 f 5 z 1 i5 6 z 5 1 3 个阶为1 0 9 的消圈集 3 1 9 另一方而 弓 c m 中存在一 v 血 y 叭 p f up 加m u 5 v 阿 v i up 7 v 艇 v 彬 p 一1 f u v 御 v p d u v 拼 u 5 2 1 5 2 5 6 2 i j l 3 z l 磊 up 5 2 1 5 2 5 6 2 i ls3 z l 矗 j u 如图3 2 2 0 弓 c 的同构图 v m v 驯 i r 3 1 r 若干乘积图的消圈数 图3 2 2 0 另 c 的同构图 综上两种情况 当 l 2 七十l 且 l l m o d 6 时 定理得证 再设刀 2 尼 且刀 2 m o d 6 即刀兰o m o d 6 或刀三4 m o d 6 情况l 刀兰0 m o d 6 即疗 6 一方面 2 5 肥 c 6 2 等h 半卜 另一施在另 c 6 的一个 连通分支g 中存在 个阶为5 1 的消圈集 v 蛳 v 川i z r u 州 u 刀v 州 u v 脚 y 6 一 i f 一1 f u v 1 一 i 3 一3 女i 图3 2 2 l 另 c 1 2 的一个连通分支g 图3 2 2 1 弓 c 的一个连通分支g 情况2 刀兰4 m o d 6 且p 刀 6 4 一方面 旭 c 6 4 2 f 半h 半卜 s o 另一方面 在另 的一 若下乘积图的消圈数 2 6 个连通分支e 中存在一个阶为5 4 的消幽集 v 斯 v 耐 p u v 川 u v v 州 u v 蛳 y 6 i f z l f up v y 6 陟 3 z l j 如 图3 2 2 2 弓 c l 的一个连通分支g 图3 2 2 2 弓 c 的一个连通分支g 综上两种情况 当 z 2 尼 且刀 2 m o d 6 时 定理得证 下设刀三2 m o d 6 即 z 6 2 情况l 当删时 一施们 c 8 2 f 半1 1 4 另一施 在弓 g 的一个连通分支g 中存在一个阶为7 的消圈集 v 4 v z 8 v 2 v 6 v 8 v 4 y 如图3 2 2 3 弓 c 的一个连通分支g 图3 2 2 3 弓 g 的一个连通分支e 情况2 当刀 8 时 一方面 在弓 c 6 m 的一个连通分支瓯中存在一 若干乘积图的消圈数 个黼 坝 m 脚f 竿h 半卜川 瞧 如 up 即 屹斯 叱州 p 一1 f up 川 v 驯 up u 札 屹 v 一 i f 一l f uk v 5 y 一 l s3 一2 另一方面 在 c 6 m 的一个连通分支g 口 中此消圈集的阶数最小 事实上此 时的余点导出图为阶数最大的一颗树 假如在此消圈集中还可以再减少某一个顶 点 且由于这个顶点的度为4 则使得增加一个点后的余点导出图的边数不小于 项点数 于是余点导出图含有圈 矛盾 故痧 弓 c 6 2 1 0 6 如图3 2 2 4 另 c 的一个连通分支g 栅2 硝w 沪陷 1 证明 当剃m 时 一方面洲只嵋 f 孚卜另一方面 只 q 帱在一个阶为 爿的消熙 情况 当删川时 阶为 竿 1 f 坠竽1 1 2 艄圈集为 p 川 u 若 t 乘积图的消圈数 p 3 v 4 v 曩 v 6 f v 剧 3 v 别一 f z l f u v 舢 v 一 p 一l f u妒3 6 v 3 6 f v 3 一6 p 一i f u v 3 l v 3 射 l y 3 6 i i 歹 f 歹 j u1 v 3 l v 3 6 l y 3 6 1 1 sz v j u v v v 血 v y 一 y 6 一 l r z l u v 细小 v 川 i l 所 z 所 u 川 u p v 舶 州 卅一 1 6 z 一1 6 u p 5 6 1 5 6 6 v 5 6 一6 i d sz l d u v v 6 d v d v 一 1 一 f d 一l d u 和印 u p v y 6 1 j l l 办 up v p v 6 f 一 f p 一l p 如 图3 2 2 5 只 c 3 的同构图 图3 2 2 5 只 c 的同构图 情况2 孙6 时 阶为f 孚h p p v 却小 v 耐 忙 f up 埘 6 6 3 1 1 2 7 消圈集为 u 和 4 v 加 v 一 p z 一1 u 和 l y 小 屹 6 l f z f u 如3 4 v 3 6 4 v 3 6 一2 i z 一1 up 3 4 v 3 6 4 v 3 6 一2 z l j u p 4 4 4 6 p 4 v 4 6 一2 l p 一1 p up 4 4 4 6 p 4 v 4 6 一2 i p 一l p j u p k d v l d d u p v 5 6 州 剧 旧 g u p 4 y 舶 y 5 6 心陋 一l 办 up l y l 一 v 耶 j m z z i j 札 4 y 舶 屹 6 一 i 厂 一1 up y 舯 y 舶6 1 6 6 u 4 向h 4 6 一 k 一l 如图3 2 2 6 只 c 9 的同构图 若干乘积图的消罔数 图3 2 2 6 最xc 9 的同构图 情况3 当 5 时 阶为f 竽1 f 6 6 5 l v v y v v i f z f v 屹 2 v 6 f 小1 斛 v 6 f 1 l f z f k 4 v 4 4 心州 4 陟 un 4 v 4 6 4 心 6 s 川j u 3 1 2 z 1 1 消圈集为 u u p v v 一 i r 一1 u p 列 1 印 v 剐小y 舯 屹 6 小v 拍m 肛 z 办 u v 剧 u p 4 y 御 6 ps d up 5 却 6 一 i p 一l p u p 1 2 加小v 期 1 6 v 6 f ks g 如图3 2 2 7 只xc l 的同构 图 图3 2 2 7 最 c l 的同构图 综上三种情况 当 l 2 尼 1 时 定理得证 现设刀 2 七 一方面 只瓷g 2 6 胛 2 6 另一方面 只 e 的一个 若t 乘积图的消圈数 3 0 l 一 一 连通分支瓯中存在一个阶为f 6 玎 2 6 情况l 当以 6 时 阶为 的消圈集 6 疗 2i6 6 2 v 6 r v 一 i f 一1 f v 3 y 耐 v 6 一 p 一l f u 6 p 吃州 i 屹 6 一5 l d 一1 d u u 6 1 6 1 的消圈集为 k u k 4 k 柳 1 6 一 l 一l u p v 一 1 6 一l 6 u 如7 i 吻却 1 7 6 一5 i p 一l p 如图3 2 2 8 最 c 的一个连通分支q 图3 2 2 8 只 c 1 2 的一个连通分支g 情况2 当刀 6 2 时 阶为f 6 z 2l 6 6 2 2 6 p v 6 f v 一 ps 一l f u p 1 v 6 f v 6 一 i f z l f u 6 p 耐 u 6 3 的消圈集为 p 脚 u k 扣4 4 4 州 4 y 4 6 一2 l z l up 4 4 4 6 4 y 4 6 2 sl l ju u p 屹州小 v 6 一 l 矗 z 一1 d u和 v 一 1 6 z 一1 6 u p i 1 却小 v 6 一 i p 一1 p 如图3 2 2 9 只 c 的一个连通分支 图3 2 2 9 只 c 的 个连通分支g 若下乘积图的消圈数 情况3 当以 6 4 时 阶为 6 玎 2i i6 6 4 2 66 6 5 的消圈集为 p 印 v 斯 v 驯 i f f up v 埘 屹州 i f i u 和 川 u 如 4 屹州 v 刖一 j 一l u p y v 1 6 一1 6 u 图3 2 3 0 忍xc l o 的一个连通分支g 口 p 5 j 5 6 j l 3 6 j i d d u妒5 l 5 6 j l 3 6 j i dsf d 川ju p 7 1 吩 6 p j 7 6 l i p p 如妒7 1 吩 6 j 7 6 l i ps p 川弘如 图3 2 3 0 只 c 的一个连通分支g 综上三种情况 当 z 2 七时 定理得证 参考文献 参考文献 1 n a l o n d m u b a y ia n dr t h o m a s l a 玛ei n d u c e df o r e s ti 1 1s p a r s eg r a p h s j g r 印h t h e o r y 3 8 2 0 0 1 1 1 3 1 2 3 2 vb a f n a p b e m a l la n dt f 由i t o a2 印p r o x i m a t i o na l g o r i t h mf o rt h e 吼d i r e c t e df e e d b a c kv e r t e xs e tp r o b l e m s i m aj d i s c r e t em a t h l2 19 9 9 2 8 9 2 9 7 3 s b a ua n dl wb e i n e k e t h ed e c y c l i n gn u m b e ro f 黟a p h s a u s t r a l j c o m b i n 2 5 2 0 0 5 2 8 5 2 9 8 4 s b a ua n dl wb e i n e k e g m d u z s l i ua n dr c v a n d e l l d e c y c l i n gc u b e s a n dg i r i d s u