（应用数学专业论文）一些八边图的填充与覆盖.pdf

河北师范大学硕士学位论文 摘要 设a k 是a 重玑女 完全图 其任二不同顶点 和 间都恰有a 条边 z 相连 对于有限简单图g 图设计g g d f l 州圈填充g 一 d 图覆盖g c d x 是一个序偶 x 召 其中x 是凰的顶点集 b 为k 中同构于g 的子图 称为区组 的族 使得凰中 每条边恰好 至多 至少 出现在8 的 个区组中 一个图填充 图覆盖 被称作是最大 最 小 的 如果不再存在同阶数的其它图填充 图覆盖 含有更多 更少 的区组 本文所研究的是两个六点八边图与8 长圈岛的最大圈填充和最小图覆盖的问题 在统一的构作方法下 对于两个六点八边图所有可能的 和a 给出了相应的最大图填 充和最小图覆盖的构造 对于q 的所有可能的 和a l 应用递归构造给出了最大图 填充和最小图覆盖 本文同时研究了完全二部图尥 加一条悬边的两类图p s q 的图设计 文 4 1 已给 出了口i0 1 m o d2 s 1 时图设计b g d v 1 与q 一c d v 的存在性本文则对2 s q1 5 q 且口础沲口 1 的进一步情况讨论了这两类图设计的存在性问题 给出了q l o 3 三2 0 t 6 3 0 1 0 f r o o d5 眦 1 5 及q 1 0 t 9 三4 0 t 3 6 1 0 1 0 r o o d5 0 t 4 5 时 图设计b g n v 与魄一g d v 的存在性 关键词 图设计 图填充 图覆盖 k 长圈 完全二部图 一些八边因的填充与覆盖 a b s t r a c t ac o m p l e t em u l t i g r a p ho fo r d e r w i t hi n d e xa d e n o t e db ya k j i sa l lu n d i r e c t e dg r a p hw i t h 口v e r t i c e s w h e r ea n yt w od i s t i n c tv e r t i c e sza n d 掣a r ej o i n e db y 入e d g e s z 3 l e tgb eaf i n i t e s i m p l eg m p l l ag r a p hd e s i g ng g d u g r a p hp a c k i n gg p d x v g r a p hc o v e r i n gg c o a v o f a 甄i s a p a i r x b w h e r e x i s t h e v e r t e x 蛾o f 凰a n d 3 i s a c o l l e c t i o n o f s u b r a p h s o f 耽 c a l l e d b l o c k s s u c ht h a te a c hb l o c ki si s o m o r p h i ct oga n da n yt w od i s t i n c tv e r t i c e si n 凰a r e j o i n e di ne x a c t a tm o s t a tl e a s t ab l o c k so fb ag r a p hp a c k i n g c o v e t i n g i ss a i dt ob em a x i m u m m i n i m u m i f n oo t h e rs u c hg r a p hp a c k i n g c o v e t i n g w i t ht h es a m eo r d e rh a sm o r e f e w e r b l o c k s i nt h i sp a p e r t h em a x i m u mg r a p hp a c k i n ga n dt h em i n i m u mg r a p hc o v e t i n go ft w og r a p h s d 1 d 2w i t hs i xv e r t i c e sa n de i g h te d g e sa n dt h e8 c y c l ec a r er e s e a r c h e d b ya nu n i f i e dm e t h o d w e s o l v et h ep r o b l e m so ft h em a x i m u mg r a p hp a c k i n ga n dt h em i n i m u mg r a p hc o v e t i n gf o ra l lp o s s i b l e 口a n da n ya f o rg r a p h sd 1a n dd 2 o fa 1 f o r g r a p hc k b yr e c u w e o c ec o n s t r u c t i o n s i na d d i t i o n t h eg r a p hd e s i g no fc o m p l e t eb i p a r t i t eg r a p hk 2 3w i t ha p e n d e n te d g e i n c l u d i n g t w ok i n d so fg r a p h 只a n dq s i sr e s e a r c h e d f r o m 4 t h ee x i s t e n c eo f 只一g d v a n dq s g d v f o r 口 0 1 m o d2 s 1 h a sb e e nk n o w n i nt h i sp a p e r t h ef a r t h e rr e s u l t sa r eg i v e nf o rt h e c a s e2 s 1 5 qa n dg o d 5 q 1 d i s c u s st h ee x i s t e n c eo f 只一g d v a n dq 8 一g d v f o r 口i 2 0 t 6 3 0 t t o f m o d5 0 t 1 5 w h e n 穹 1 0 t 3a n d 妒三4 0 t 3 6 1 0 t 1 0 m o d5 0 t 4 5 w h e n 口 1 0 t 9 k e y w o r d s g r a p hd e s i g n g r a p hp a c k i n g g r a p hc o v e t i n g k c y c l e c o m p l e t eb i p a r t i t eg r a p h 学位论文原创性声明 本人所提交的学位论文 一些八边图的填充与覆盖 是在导师 的指导下 独立进行研究工作所取得的原创性成果 除文中已经注明 引用的内容外 本论文不包含任何其他个人或集体已经发表或撰写过 的研究成果 对本文的研究做出重要贡献的个人和集体 均已在文中 标明 本声明的法律后果由本人承担 论文作者 签名 奎明超 协呵年年月7 日 学位论文原创性确认书 学生奎明超所提交的学位论文 一些八边图的填充与覆盖 是在本人的指导下 由其独立进行研究工作所取得的原创性成果 除 文中已经注明引用的内容外 该论文不包含任何其他个人或集体已经 发表或撰写过的研究成果 指导教师c 签名 曩藏序 研年争月7 日 河北师范大学硕士学位论文 l l 引言 设g 是一个由t 1 个顶点和e 条边组成的简草图 a j 0 是a 重 点完全图 其任两个 不同顶点z 和g 间都恰有a 条边 相连 对于有限简单图g 所谓的图设计g g d 口 图填充g p d x v 图覆盖g c 仇 口 是一个序偶 x b 其中x 是j l 的顶点集 b 为 j 0 中同构于g 的子图 称为区组 的族 使得甄中每条边恰好 至多 至少 出现在8 的 a 个区组中 显然 存在g g d v 的必要条件为 移 珏 a v v 1 三0 m o d 2 e 如一1 三o m o dc 玟 其中d 表示g 中各顶点度数的最大公约数 一个图填充 图覆盖 被称为最大 最小 的是指不再存在其它同阶数的图填充 图 覆盖 含有更多 更少 的区组 记为1 7 1 m 2 g p d v m i n g c d v 最大的图填充 最小 的图覆盖 的区组数称为填充数 覆盖敷 记作p g a c g a 显然 p 扣 g a su 扣 g a l 高等蟊 i i 智等茜 f y q g a 冬c g a 这里扛j p 1 分别表示满足y 的最大 最小 整数y 将填充数为u v g a 的图填充 覆盖数为y g a 的图覆盖 称为9 目 i 的 记为o p d a v o c d x v 显然 图设计g g d 存在当且仅当p v g a c v g a 因此 一个图设计g g d x v 亦是 一个正则的图填充及正则的图覆盖 图填充g p d u k 7 9 的余边圈l x p 是a 虬的子图 其边集是p 图填充中各 区组所对应子图的多重并 在a 中的补 当p 最大时 i p i 称为此图填充的余边数 记作h 类似地图覆盖g c d x v v c 的重边图瞰 c 也是a k 的子图 其边集 是入 在c 图覆盖中各区组所对应子图的多重并 中的补 当c 最小时 l 取 c 称为此 图覆盖的重边数 记作r a 口 为简便 队 p l x v 与取 c n 口 通常可简记为l x h 与 风 r a 本文中对应于图职的r a h 厶 r x 分别记为r i z i 以 瞰 称a u 置 e 为一个 至坌全兰塑堕 其中i x i 仉 诸五两两不 交 且比 x j 边扛 在e 中出现a 次 当i j 时 或不出现 当i j 时 图g 的型为t n 畦n 的带塑里毽生指的是a j 0 一肌的一个分拆 所分 拆成的各子图均与g 同构 为 6 伯1 带洞图设计的型t 常被表达为指数形式 例如 n 磅 嘲表示n l 长洞出现惫1 次 长洞出现 次 这样的带洞图设计常 记为g h d a t 或g 日d n 啦 佗静 4 g h d x 1 1 2 1 0 钟1 称为丕塞全盟垦 矍盐 记为g i d 口 t l v w 棚 其中i 卅 口 i w l 且wcv 为简洁 当a 1 时 符 号g d h d x i d x o p d x o c d x 的下标a 均可省略 2 一些八边图的填充与覆盖 国内外对图填充和因覆盖的研究已有相当一段时间 主要涉及的图有甄 甄 酶 五点图 六点图等 yr o d i t t l y 见 l s l 完全解决了不超过四点的完全图的填充和覆盖问 题 1 9 9 4 年 殷剑兴教授解次了完全图蚝的填充问题 1 9 9 9 年 葛根年教授解决了加一 条悬边的五点星图的填充问题 文 5 1 4 已对全部六点七边图的图设计 图填充和图覆 盖问题给出了系统完整的解决 文 8 9 1 7 已完全解决了其中六个图的填充和覆盖问 题 文 1 5 2 3 已对全部六点八边图的图设计问题给出了基本完整的解次 但它们的图 填充与图覆盖问题尚未研免 本文第一部分书对如下两个六点八边图d l 和d 2 的图填充和图覆盖进行研究 分 别构作了其最大图填充和最小图覆盖 图d l图d 2 对于n 长圈c 其图设计问题已对任意的n 完全解决 见 而对于n 3 4 6 完 全图上g 的图填充与图覆盖也已解决 见 6 1 i 1 2 1 3 2 0 2 2 1 本文第二部分将进一步 研究c 的图填充与图覆盖 图鲍 加一条悬边的图设计自2 0 0 2 年开始研允至今尚未完全解决 这种图分为 以下两类 澎 蝴 图只图仉 由 式知 只一g d v 及q 一g d v 存在的必要条件是 2s 3 v v 一1 e0 m o d4 s 2 但它们的存在范围取次于s 的值 文 4 已对公共的范围u 0 l m o d 2 s 1 进行了讨 论 文 2 q 在此基础上讨论了当2 s l 3 q 且g c d 3 q 1 时 只一g d v 及q r o d v 的存在性问题 给出了基本完整的答案 本文第三部分进一步讨论了当2 s 1 5 q 且 a c d 5 q 1 时此两类图设计的存在性问题 河北师范大学硕士学位论文3 2d l 与d 2 的图填充与图覆盖 盒甜 图d 1图d 2 引理2 1l 厕存在d 1 g 巩 u o l 2 茸a v v 一1 i0 1 m o d l 6 u 1 6 在构作h d i d o p d o c d 的区组集时 常应用循环群或循环群的直积作为自同 构群 对于基区组b 当自同构群为z 时 b m o d m 表示区组族 b i t 磊囊 而当自同构群为磊 磊时 b m o d m n 表示区组族 b j i z m j z i b m o d m 一 表示区组族 b i 0 i z b m o d 一 n 表示区组族 b 0 j j 磊 至于设计的点集中不属于所用自同构群的元 则在自同构群作用下保持不变 它们通常 被记为z 或五 2 1 图填充与图覆盖的一般构作方法 引理2 2 司对于图g 和正整数h 若存在有g i d h w u 和g o p d w g o c d w 则存在g o p d h u g o c d h u 且它的余r 重j 边图与前者一玩 引理2 3 阎对于图g 及正整数 u m m 2 若存在g h d h m 和g x d h 十u u 则 1 当g o p d w 或g o p d h u 存在时 g o p d m h u 亦存在 2 当g o c d w 或g o c h 九 存在时 g o c d m h u 亦存在 引理2 4 阎对于口元集x 图g 和正整数 a 1 若存在g o p d v x 功 其余边图以 p cg 则存在有g o c d v 其重 边图为g 么 尹 4 一些八边图的填充与覆盖 2 若存在g o p d x v x p 和g o p d u v x 其余边图分别为 p 和 p 如果l 厶 p l i l z 仲 则存在有g o p d x p x p u p 其余边图 为l p u l p 3 若存在g o c d x v x c 和g o c d u x c 其重边图分别为风 c 和 r p c 如果i 取 c i f 量p c i r a p 则存在有g d c d p 口 x c uc 其重边图为 r c ur u c 4 若存在g o p d v x p 和g o c d u 口 x c 其余边图和重边图分 别为以俨 和吼 c 如果厶 p 吼 c 且l 厶 p l i 吼 c i z p 则存在有g d p d p x p u c 其余边图为l p 吼 c 5 若存在g o c d v x c 和g o p d p v x p 其重边图和余边图分 别为r c 和l p p 如果r c d 乩 p 且 凡 c i 一 p i p 则存在有g d c 巩 p u x p u c 其重边图为凡 c p 引理2 5 对给定的阶数弘设a a o 是使得g g d v 存在的最小的正整耗 1 若对1 ss 知一1 g o p d 口 和g o c d s v 皆存在 则v 九g o p d 和 g o c d v 都存在 2 若g o p d v 轰g o c d v 不存在 但对于2ss a o 一1 和s a o 1 g o p d s 口 或g o c d 皆存在 则va 1 g o p d x v 或g o c d v 都存在 证明 1 设g g d 知 u x 嚣 v a 0 令a s m o d 如 其中0 s 知一1 由已知 对于l 8 a o l 存在g o p d u x p s 及g o c d x c s 则 当s 0 时 x 絮8 u p s 即是一个g o p d v x 案8 u c s 即是一个g o c d v 当s 0 时 x 熹8 即是g a d d v 它亦是g o p d x v 和g o c d v 2 仅需对a 1 m o da o 且a 1 的情形说明如下 其它情形同 1 x 半8 u p 知 1 即是一个g o p d x v x 生 p 8 u c a o 1 即是一个g o c d v 口 对于本文所讨论的图d l 和d 2 由引理2 1 及2 5 可知仅需对以下范围分别构作其 图填充和图覆盖 1 口兰2 3 4 6 1 0 l l 1 4 1 5 m o d l 6 且t 6 时 知 8 1 a 7 2 口e5 7 1 2 1 3 m o d l 6 且 6 时 知 4 1sa s3 河北师范大学硕士学位论文 5 3 口e8 9 m o d l 6 且 1 6 时 h 2 入 1 4 口 6 时 正则的图覆盖不存在 将单独讨论 2 2a 1 的图填充和图覆盖 n 阶拟群 厶 是带有一个满足结合律的二元运算 的n 元集厶 且对任意的n 6 厶 方程n z b 和z o b 均在厶中有唯一解 一个拟群称为是对称的 若对任意元 n b 厶均有n 6 6 n 一个拟群称为是幂等的 若对任意元n 厶均有口 o 口 熟知 见 3 1 对任意奇数n 存在n 阶幂等对称拟群 若集合j 2 l l 2 2 n 一 1 2 n 上的2 n 阶拟群含有诸 2 一1 2 讣上的n 个2 元子拟群 称为洞 1 i s n 记去掉 这些子拟群后的带洞拟群为h q 2 j 轨 文 7 1 中证明了 n 3 时 存在对称的 带洞拟群 记为h s q 2 设g 为e 边简单图 厶 为n 阶幂等对称拟群 考虑集合磊x k 上的带洞图设计 g h d e 其中洞集合为 磊x 订 i 厶 我们希望找到其区组集以磊为自同构群时 的基4 它应当由 个基区组a 1si jsn 构成 基区组集a 中连接点 z u 与扛 d 口 的边记为d 口 它代表一个混差轨道 z u 0 d z z e 任一个 2 子集n 口 c j i j 记d u 口 d d u 口 a j 文 1 6 中给出了区组族a 可构成此带洞图设计的基的充分条件 见引理2 6 2 7 引理2 6 设n 3 h 是一个h s q 2 其中竹 2 r l 2 r 1 r n 对于给 定的简单e 边图h 如果下面的条件满足 则 a j 1 i j 2 n l j 譬 可作为带 洞图设计日 h d 2 e 在自同构群磊作用下的一组基 1 d i i j d 鼻i j 2 d 佤j u d z i j u d i j j 磊 引理2 7 设n 3 厶 是厶上的幂等拟群 对于给定的简单e 边图g 如果下面的条件 满足则4 4 j 1 i 1 的图填充和图覆盖 引理2 2 0 对于 e2 1 5 m o d1 6 口 6 a 1 及i 1 2 存在d 一o p d v 和d l o c d v 证明 由引理2 5 后的讨论可知 仅需对1 a 墨7 构作 而在此范围内z j 1 氓 a 今 应用引理2 4 2 对a 递归地构作d 0 p 巩 即由d r o p d v 与b d 尸巩一l 口 产生 助一o p d x v 因媛 a 等式 i 暖一l 1 a 一1 a 强恒被满足 在a 由2 递增到7 的过程中 每步都增加一个n o p d v 的区组集 而余边集则每步增加一边 为了使增 加后的余边集始终保持为n 的子图 需对每次增加的区组集通过点集置换调整诸区组 中点的标号 这是恒可做到的 al234567 o p d l x l2 3 45 6 7 l l l u l x 1 o c d 哇 765 4 3 21 瞰 d e 至于诸功一o c d x v 的构作则很容易由引理2 5 1 完成 口 在引理2 2 1 2 2 6 中 为了使d t o p d v 的余边集保持为d i 的子图 均需对每次 增加的区组集通过点集置换调整诸区组中点的标号 至于诸甄一o c d x t 的构作则很容 易由引理2 4 1 完成 为了简单 以下不再赘述 河北师范大学硕士学位论文 2 1 引理2 2 l 对于口兰5 1 2 m o d1 6 7 a 1 及i l 2 存在d t o p d x v 和d 1 o c d x v 证明 由引理2 5 后的讨论可知 仅需对1 a 3 构作 如图所示 al23 氓 2 4 l j f 6 垃 f o p d r食b r l 64 2 0 c d 啜d l l i职 髓d 聪 其中d 一o p d x v 由d 1 o p d v 和d o p d 一l 拼合而成 根据引理2 5 2 余边图为 l j l x l 如图所示 口 引理2 2 2 对于 3 1 4 r o o d1 6 u 7 a 1 及i 1 2 存在d r o p d x v 和日 o c d x 证明 由引理2 5 后的讨论可知 仅需对1 sa 7 构作 如图所示 a1234 f x 3 6 f i q1 f 一鸭4 2 i 强 0 p d qq l kl r 5274 0 c d 戤d l qn 岛d 日历 日 a 56 7 氓7 f i 强 2 f 一r 5 l i 培 o p d 台 以 r l63 d e d 戢d l d n 日 其中 3 6 时 d 一o p d x v 由b o p d v 和d 1 o c d x l 口 拼合而成 根据引理2 4 4 余边图为l i d l 1 a 2 4 5 7 时 d z o p d x v 由n o p d v 和d i o p d x l 口 拼合而 成 根据引理2 4 2 余边图为日 l l 廿 口 引理2 2 3 对于口18 9 r o o d l 6 a 1 及i 1 2 存在功 o p d x v 和d t o c d x v 证明 由引理2 5 后的讨论和定理2 1 3 可得 口 一些八边图的填充与覆盖 引理2 2 4 对于t z7 1 0 r o o d1 6 口 7 a l 及i l 2 存在破 o p d v 和现 d e d 证明 由引理2 5 后的讨论可知 仅需对1sa 7 构作 如图所示 图d l a l23 4 f i 5 2 f 一r 7 f i 曝4 f 一r 0 p d l 盥 隧奠 囟 36i4 o c d 磁d l l i d 1 l 5d t 聪d i 日 图d l a567 暖1 z 一r 6 f 碹 3 f 一r 0 p d b i 叠 正直 r 土 725 0 g d 烈d 1 碓d l 联d i 珥 图d 2 al234 联 5 2 碍一r 7 2 睦4 曙一谔 d p d 珐 r 幽 岔金一 r 3614 o c d r 2 d 2 日现 鼋d 2 上告d 2 瑶 疆d 0 a567 氓 1 f 一r i6 l 嗜 3 吁一嘻 l 岔 0 j 厂 d p d l i蠹 f 纠 r i 7 25 o c d 磁d 2 瑶d 2 瑶 d 2 日 其中a 2 4 5 7 时 d 一o p d v 由d i o p d v 和d l o c d x 一1 拼合而成 根据引理 2 4 4 余边图为l 一磁 1 a 3 6 时 d i o p d v 由皿 o p d v 和n o p d x l v 拼 合而成 根据引理2 4 2 余边图为l i 鼋 1 如图所衣 口 引理2 2 5 对于 兰4 1 3 r o o d1 6 u 7 a 1 及i 1 2 存在d i o p d x v 和功 o c v a v 河北师范大学硕士学位论文 证明 由引理2 5 后的讨论可知 仅需矸1 a 3 构作如图所示 a 1 23 嘎 6 4 2 t r t2 l i 一鸣 o p d 工i卤 璺 嘎 246 0 c d 砖n l i皿 岛n 日 其中b o p d v 由现一o p d v 和d l o c d x t v 拼合而成 根据引理2 4 4 余边图为 髓一磁 l 如图所示 口 引理2 2 6 对于 三6 1 1 r o o d1 6 a l 及i 1 2 存在b o p d x v 和b o c d a v 证明 u 6 时 由引理2 1 知图设计对a 8 存在 而由2 5 2 知 仅需对2 a 7 及 a 9 构作d t o p d v k 碍 它包含l 警j 个区组 赵生硬 1 2 3 4 0 5 4 3 1 5 0 2 5 3 0 1 2 4 如 1 3 1 4 2 4 2 5 3 5 4 5 磅 2 3 1 4 0 5 3 5 1 2 0 4 0 3 2 4 5 1 l 1 2 1 3 1 4 2 4 3 5 4 5 芷旦碍 1 0 4 5 2 3 5 1 3 0 4 2 0 2 4 5 3 1 0 5 2 1 4 3 1 0 2 4 3 5 聪 1 2 2 3 2 5 3 4 3 5 瑶 1 0 4 3 2 5 2 0 3 5 1 4 4 3 0 1 5 2 5 4 0 1 2 3 3 2 4 0 5 1 鼋 1 3 1 4 2 4 3 4 3 5 对4 a 7 a 9 的构作如图所示 需列入a 2 3 的余边图 a23 4 5 歧 65 4 您 r 3 强一r 0 p d 佥医 匕二 l i r i 2345 o c d 冗 d l d l 鼠 瑶d l 日 a679 氓2 2 一r 1 培一呓7 l 手 呸 o p d 磁 l 一 囟 r 孟 67l o c d r id l id l 雠d l 工 一些八边图的填充与覆盖 其中a 4 5 6 7 时 余边图均由引理2 州 得到 a 4 时 d t o p d 4 v 由两个d i o p d 2 v 拼合而成 余边图为如一磁 a 5 6 7 时 d i o p d a v 由d z o p d 2 v 和 d t o p d 一2 拼合而成 余边图为l l 2 一r 墨 9 时 d i o p d 4 v 由d r o p d 2 v 和 n o p d t v 拼合而成 根据引理2 4 2 余边图为q 埘 如图所示 口 6 时 由引理2 5 后的讨论可知 仅需对l a 7 构作如图所示 困d 1 al234 强 7 6 f 一r 5 c 一r 14 f 一以 d p d 毋 s h 仑 窿垒 r 土 i23 4 0 c d 磁d 1 l id l 醍d l 聪d 1 日 图d 1 a567 畦3 l i r j2 l 一咭1 f i r 3 o p d b麒 釜羹 r i 567 o c d 硪d i 二 d 1 d l 二 图d 2 l23 4 z 7 6 f 一r 5 碍一r 4 埒一r o p d l 2岔q 金 陵 r i i234 d e d 磺d 2 研d 2 鼋d 2 嵋d 2 朋 圈d 2 567 瑶3 f 一嵋2 碍一唁1 l 一唁 0 p d 冀防 l r 567 0 c d 磁d 2 d 2 l 2d 2 工 其中d f o p d x v 由d i o p d 3 和d l o c d x l v 拼合而成 根据引理2 4 4 余边困为 q 一磁一1 如图所示 口 定理2 2 7 对于t 0 1 r o o d l 6 口27 a 1 及t l 2 存在耽 o p d v 和d t o c d x v 证明 由引理2 2 0 2 2 6 可得 口 河北师范大学硕士学位论文 z 4 结论 定理2 2 8 对于 7 a l 及i 1 2 存在d s o p d 和n 0 e 巩 v 仅有的例外是 e 6 d t 1 3 证明 由定理2 1 9 和定理2 2 7 可得 口 一些八边图的填充与覆盖 3g 的图填充与图覆盖 以下出现的如图所示区组c 可简记为 a b c d 岛 g h 或 a h g e d c b 例3 1z 1 7 上的魄 g d 1 7 0 l 1 6 3 8 5 1 3 7 r o o d l 7 例3 2 一个岛一o p d 8 1 3 2 0 5 7 4 6 1 4 2 5 3 7 6 o 1 5 4 0 3 6 2 7 余边图 l 1 2 3 4 5 6 7 o 于其中再添加一个区组 1 2 3 4 5 6 7 o 即得到一个c 8 一o c d 8 重边图r o 1 2 3 4 5 6 7 3 1 主要递归构造 为奇数时的v 1 6 构造 令i x f v 1 1 y l 1 6 设 x u a 是一个余边图为 的c s o p d v 重边图为 r 的q o c d v yu o 8 是一个岛 g d 1 7 x r c 是一个岛 h d v 一1 1 1 6 1 则 xu y u o o a u 层u c 是 余边图为l 的魄 o p d v 1 6 重边图为r 的岛一 d c d v 1 6 口为偶数时的 8 构造 令i x l l y i 8 设 x a 是一个余边图为 的c s o p d v 重边图为r 的 国一o c d v y 1 3 是一个余边图为 的0 8 一o p o s 重边图为尉的c s o c d 8 而 x y c 是一个g h d v 1 8 1 则 x u y a u b o c 是一个余边图为l u l 7 的q o p d v 8 重边图为r u r 7 的c 一o c d v 8 引理3 1 1 0 l 存在c 2 h d m l n l 当且仅当m n 缸2 k m n 且m n 均为偶托 由此定理可知 u 为奇数时存在c s 一日d 0 1 1 1 6 1 口为偶数时存在0 8 h d v 1 8 1 而由 例3 i 知存在0 8 一g d 1 7 由例3 2 知存在岛一o p d 8 和白 o c d 8 故上述两个构造可 写为以下的递归引理 引理3 2 对于任意奇数 若存在0 8 o p d v 岛 d e d 口 则存在q o p d v 1 6 岛一 o c d v 1 6 河北师范大学硕士学位论文 引理3 3 对于任意偶数u 若存在c s o p d v g o c d v 则存在c 8 o p d v 8 c 8 o c d v 8 此二引理中的正则图填充 覆盖 可替换为最大图填充 最小图覆盖 3 2 余边 重边 数的余边c 重边 图 o i r o o d l 6 最大图填充的余边数最小图覆盖的重边数需构作的小阶敷口 i 1o01 7 i 3351 9 i 52 852 l i 753 2 3 i 9 44 9 l l7l 81 1 i 1 362 81 3 z 1 51 871 5 t 0 88 l 2 1 0 6 l o i 4 1 2 4 1 2 z 6 1 4 4 6 1 4 余边 重边 图的特点 为奇数时 每点均为偶度 为偶数时 每点均为奇度 最大图填充的余边图 若口是奇数 k 每点的度都是偶数 而因白每点的度均为2 故q 的最大填充之 余边图中 必然每点都是偶度 已经知i 色 1 r o o d1 6 时 c 8 一o p d v 存在且余边图为 空图 当口i3 m o d1 6 且 21 9 时 8 一3 t 余边图只能为3 条边的白 当口i5 m o d l 6 且 2 1 时 8 l 一2 因图中无重边 故岛一o p d v 不存在 而m 口 魄一p d v 中余边图有1 0 条边 例如c 1 0 当口17 m o d l 6 且口22 3 时 8 i 一5 则余边图有5 条 边 c 5 当ui9 m o d1 6 时 8 l 韵一4 1 最小的余边图有4 条边 a 当 i1 1 m o d1 6 时 8 i 一7 余边图有7 条边 例如g 当口 1 3 m o d1 6 时 8 i 一6 余边图有6 条边 例如c 6 当口e1 5 m o d l 6 时 8 l 一1 在m n z c s p d v 中余边图有9 条边 例 如3 个不相交的岛的并 若t 是偶数 因为甄 的每点的度均为奇度 易知余边图必然是凰的每 专 都是奇度 的生成子图 对于口io 2 8 1 0 m o d1 6 且口28 因为8 i 一 故c 8 一o p d v 不存 在 在m zq p d v 中余边图是一个l 因子 当口i4 6 1 2 1 4 m o d1 6 且口21 2 时 8 i 劫一l 一4 因此白一o p d v 不存在 在m n q p d v 中余边图有扣 8 2 条边 一些八边图的填充与覆盖 最小图覆盖的重边图 已知 当口 1 r o o d1 6 时 c 8 一o c d v 存在且重边图为空图 当口13 r o o d1 6 且 口 1 9 时 8 i 5 因此重边图有5 条边 岛 当v 5 r o o d1 6 且 2 1 时 8 i 6 重边图有6 条边 例如c 6 若 i7 m o d1 6 且u22 3 8 l 3 则重边图有3 条边 岛 若 s9 m o d l 6 8 1 4 重边图有4 条边 a 若口i 1 1 r o o d l 6 8 f 1 在 r a i nc 8 c d v 中重边图有9 条边 例如c 9 若 兰1 3 m o d1 6 8 l 2 在m i n c 8 一 c 1 9 v 中重边图有1 0 条边 例如c l o 若 e1 5 m o d1 6 8 i 7 重边图有7 条边 例如o 若 是偶数 对于 o 4 8 1 2 r o o d l 6 且口 8 因为8 l 故c 8 o c d v 不 存在 在m i ne 8 一c d v 中重边图是一个l 一因子 当口i2 6 1 0 1 4 m o d1 6 且口 8 时 8 i 6 因此c 8 一o c d v 不存在 在m i ne 8 一c d v 中重边图有扣 t 2 2 条边 3 3 小阶数的构作 以下对于所需要的小阶数口 给出q o p d v 与c 8 一o c d v 当它们不存在时给出 m n 岛一p d v 及m i nc 8 一c d v 除特别声明外 点集均取自乙 塑三 q m o z c 8 一p d i o z 5 z t 3 l o l 1 1 3 0 4 l 2 0 1 0 4 0 r o o d 5 一 0 0 0 t 1 0 1 1 2 0 2 1 3 0 3 1 4 0 4 1 m i n 岛一c d 1 0 8 3 2 4 6 5 7 9 8 7 6 2 1 3 5 9 7 3 4 l 5 o 6 9 0 9 5 3 1 7 4 2 4 5 1 8 0 7 2 9 9 1 6 8 5 2 0 3 3 6 2 8 4 0 1 9 冗 1 9 3 5 7 9 8 9 0 2 2 4 2 6 1 3 9 5 女三1 2 m 岛一p d 1 2 5 7 9 1 1 8 2 6 1 0 1 1 1 0 4 8 5 9 6 1 1 5 2 4 6 7 3 1 0 3 9 4 0 6 8 7 1 1 1 7 2 1 0 9 8 3 o 1 2 3 5 4 7 0 8 1 4 3 6 5 0 2 9 1 3 2 1 1 4 1 1 5 1 1 6 1 1 1 1 o 1 0 o 9 0 7 1 0 8 1 0 m 规岛一e d 1 2 z 3 z 4 2 0 1 3 0 3 0 2 1 1 2 2 2 1 0 0 2 l 1 0 1 3 l l 2 3 0 2 0 0 0 1 1 2 2 3 3 1 3 3 2 0 0 2 2 2 r o o d 3 一 尼 0 0 0 2 1 0 1 2 2 0 2 2 o l 0 3 1 i 1 3 2 1 2 3 女三 垒撇q p d 1 4 0 5 1 3 2 4 1 8 3 0 1 5 8 2 3 1 2 7 1 1 3 3 4 6 9 2 1 0 0 9 4 8 6 7 1 1 t 0 9 1 0 6 1 2 4 7 2 1 1 1 1 2 6 3 7 5 1 2 1 6 5 4 1 1 8 9 7 3 9 5 1 1 1 3 1 2 8 1 0 2 1 2 1 1 3 5 1 0 4 o 墙 9 1 1 6 0 8 7 l o 河北师范大学硕士学位论文 肛 1 3 2 5 4 1 3 6 t 3 7 1 3 8 1 3 1 3 o 1 2 o 1 1 o 9 1 2 1 0 1 2 m i n c 8 一c d 1 4 3 1 2 0 6 2 8 1 1 0 5 1 4 1 3 1 2 1 1 0 8 7 2 1 9 5 1 3 3 t o 7 0 3 l 1 3 2 5 4 4 1 2 6 5 3 9 0 2 0 1 6 3 2 9 4 1 3 2 1 0 0 4 3 7 1 x 2 7 8 3 1 1 1 0 1 2 9 t 3 6 1 3 7 1 1 2 1 2 5 1 0 5 0 1 1 6 1 0 4 8 1 2 1 1 5 7 9 8 1 0 1 3 1 1 2 7 6 8 1 0 9 1 1 x 3 1 0 1 3 8 1 1 4 6 9 1 2 船 0 t a 1 1 3 4 1 3 7 1 3 3 1 0 6 1 0 8 1 0 2 1 2 5 1 2 9 t 2 1 0 1 2 1 3 三1 9 o p d 4 1 0 6 1 2 3 0 1 1 6 1 8 l o 1 1 2 8 1 3 7 3 1 4 1 0 5 7 1 2 1 6 8 1 8 6 3 5 2 1 1 7 0 1 8 9 5 1 4 8 6 2 1 7 1 3 9 0 4 6 1 1 5 1 7 2 1 3 4 5 8 1 0 1 5 9 i 0 l x 3 1 2 3 4 7 9 1 4 8 0 i 1 1 5 o c d 将第一个区组替换为 4 i o 6 1 2 3 o 1 1 1 6 再添加一个区组 1 l 1 5 0 1 1 6 7 8 9 即得到一个e 8 一o c d 1 9 其重边图r 1 l 1 6 7 8 9 女三2 l m n z 瓯一p o 2 1 1 5 2 1 1 5 1 o 8 1 6 1 1 1 0 9 8 7 o 4 1 4 0 2 0 1 2 3 4 5 1 9 1 8 5 1 3 1 2 3 1 1 6 1 9 1 0 5 6 1 4 1 9 4 1 3 1 2 2 0 1 3 1 4 1 5 7 2 0 1 3 7 1 2 1 5 5 1 4 8 o 0 i s1 7 1 6 3 1 3 7 6 1 2 9 1 7 二 1 9 2 0 6 2 1 0 1 8 1 7 4 1 2 1 1 o c d 于其中再添加两个区组 1 9 2 0 7 1 5 1 4 1 3 1 2 1 1 2 0 6 2 1 0 1 8 1 7 4 1 2 即得到一个岛一0 c d 2 1 其重边图r 2 0 7 1 5 1 4 1 3 1 2 女三2 3 o p d 1 5 1 2 4 9 1 4 1 6 1 3 1 8 2 1 2 2 1 0 0 9 1 2 4 2 2 2 4 8 1 0 3 x 1 6 1 2 1 3 5 1 2 7 1 1 1 2 3 6 1 0 8 1 1 4 t 4 1 4 3 8 1 3 1 5 1 0 1 2 1 7 0 2 0 1 8 1 6 1 1 1 4 1 9 2 1 7 2 3 1 3 5 8 6 9 1 7 2 2 1 7 5 0 2 2 0 1 1 9 1 2 8 2 5 1 0 1 3 1 8 2 1 l6 1 9 1 4 6 o 1 3 1 0 7 4 1 3 2 1 2 3 4 1 5 5 1 4 6 1 3 9 t 0s ts1 7 2 2 0 1 1 1 1 0 2 9 5 l 2 0 1 5 1 7 1 9 2 2 o c d 将第一个区组替换为 0 2 0 1 8 1 6 l l 1 4 1 9 2 2 再添加一个区组 5 2 2 2 0 1 5 1 7 1 9 2 1 o 即得到一个岛一d e d 2 3 其重边困r 2 2 5 o 女三2 o p d 1 5 3 0 7 6 2 8 1 2 3 4 6 0 5 7 1 3 6 8 4 5 2 0 1 4 2 7 3 8 5 6 l 4 0 8 7 o c d 将第一个区组替换为 1 5 4 9 7 6 2 8 再添加一个区组 3 0 8 7 4 1 2 5 一些八边图的填充与覆盖 即得到一个c 8 o c o 9 其重边图r 4 5 2 1 女三l l o p d 9 0 6 7 3 4 l 5 5 1 0 0 4 9 2 8 3 6 8 9 7 l 2 3 t o 8 4 7 2 6 l 0 5 1 1 0 2 5 4 6 3 9 1 8 7 1 0 4 2 0 3 厶 8 1 0 9 6 5 7 0 r a i n q c d 1 1 于其中再添加两个区组 8 1 0 9 6 5 7 1 o 0 7 4 5 6 1 3 2 即得到一个r a i nc 8 c d 1 1 其重边图r 0 1 7 4 5 6 8 3 2 g 三i 3 o p d 1 1 5 i 3 0 4 2 6 1 0 1 4 5 8 3 9 2 1 1 4 7 3 5 2 8 1 7 8 4 3 1 2 6 1 0 5 2 1 1 3 1 0 4 9 1 o 1 1 1 2 4 6 3 2 1 7 8 9 1 0 0 7 1 2 5 6 7 9 5 0 6 1 1 2 2 0 1 2 8 1 0 7 6 9 1 1 工 o 9 1 2 1 0 1 1 8 r a i n c 8 一c d 1 3 于其中再添加两个区组 0 9 1 2 1 0 1 l 4 5 8 1 1 8 2 1 0 3 7 6 即得到一个r a i n 凸一c d 1 3 其重边图r 8 5 4 1 1 6 7 3 0 l 2 女三 乳m n z 岛一p d 1 5 历x 磊 2 0 0 1 1 2 2 3 0 4 1 1 1 3 0 0 1 l 0 3 o o 1 2 1 4 2 3 0 2 0 1 2 0 2 4 2 3 2 2 o l 0 4 l o 1 2 1 0 1 1 2 4 0 2 1 4 0 0 2 1 0 z r o o d 3 一 l 0 2 1 2 2 2 0 3 1 3 2 3 0 4 1 4 2 4 o c d 于其中再添加两个区组 0 2 2 2 1 2 2 3 0 3 1 3 2 4 0 4 0 3 1 3 2 3 0 2 1 2 2 4 1 4 0 4 即得到一个c 一o c d 1 5 其重边图r 0 3 0 4 0 2 2 3 1 2 2 4 1 3 3 4 最大图填充与最小图覆盖 定理3 4 当 三0 r o o d 2 时 存在m 岛一尸d 口 证明 分如下两种情形叙述 1 已知存在 m z 魄 p d 1 0 由引理3 3 可知对任意 兰0 2 8 1 0 m o d l 6 且 1 6 存在伽o p d v 其余边图为甄的一个1 因子 2 已知存在m n z 岛一p