（计算机软件与理论专业论文）广义petersen图和循环图的罗马支配研究.pdf

大连理工大学硕士学位论文 摘要 罗马问题始于康斯坦丁大帝网世时期的军事驻扎问题 公元三世纪 当罗马统治欧 洲的时候 通过部署帝国的军队 他们能防御5 0 个地区包括最边远的地区 随后一个 世纪 罗马帝国军事力量下降 这时如何驻扎尽可能少的军队来防止罗马军队同时受到 多处攻击成了一个主要问题 1 9 9 7 年r e v e l l e 提出了罗马问题 1 9 9 9 年及2 0 0 0 年s t e w a r t 和r e v e l l e 发起了罗马 支配的研究 并用图论的理论构造了罗马支配数 对于图g v e 设f v 一 o 1 2 r v o k 是由f 诱导出的点集矿的有序集 其中当江o 1 2 时 形 v 矿i 厂 v f 且 i 杉i z 函数f v o k 是罗马支配函数 r d f 当圪 其中 指集合 支配 即v o n 畋 f 的权重是厂 y 删厂 v 2 n 罗马支配数用 g 表示 它 等于图g 的r d f 的最小的权重 当f k 砭 是一个r d f 且厂 矿 z r g 我们称它 是一个y r f u n c t i o n 鉴于广义p e t e r s e n 图和循环图的重要性 本文根据前人的研究成果 针对广义 p e t e r s e n 图p n k 循环图c 刀 l 后 使用罗马支配算法求得罗马支配集中通用的规 律 然后研究了它们的关系 以及一些情况下的精确值 主要得出以下结论 1 烁 地2 li 8 nk 5 c2 f二 三兰 二 三 f o 7 或者即 6 12 13 19 2 6 3 0 3 2 阱 鸵舰 同时给出了广义p e t e r s e n 图p n 尼 以及循环图c o 1 i j 的罗马支配数的上界 关键词 罗马支配 支配数 支配集 广义p e t e r s e n 图 循环图 1 i z一 一引降 大连理工大学硕士学位论文 r e s e a r c ho nr o m a nd o mi n a t i o ni ng e n e r a l i z e dp e t e r s e ng r a p ha n d c i r c u l a n tg r a p h a b s t r a c t r o m a n p r o b l e mi sal o c a t i o np r o b l e mw h i c ha p p r o a c h e db yt h ee m p e r o rc o n s t a n t i n ei n t h e4 t hc e n t u r y i nt h e3 r dc e n t u r y w h e nr o m ed o m i n a t e de u r o p e i tw a sa b l et od e p l o y5 0 l e g i o n st h r o u g h o u tt h ee m p i r e s e c u r i n ge v e nt h ef u r t h e r m o s ta r e a s b yt h ef o l l o w i n gc e n t u r y t h ee m p i r eh a dl o s tm u c ho fi t sm u s c l e h o w e v e r a n dr o m e sf o r c e sh a dd i m i n i s h e dt oj u s t2 5 l e g i o n s s o h o wt od e f e n dt h er o m a ne m p i r ef r o mm u l t i p l ea t t a c k sb ys t a t i o n i n ga sf e w l e g i o n sa sp o s s i b l ew i l lb et h em o s ti m p o r t a n tp r o b l e m r e v e l l es u g g e s t e dr o m a nd o m i n a t i o ni n19 9 7 af e wy e a r se a r l i e r s t e w a r ta n dr e v e l l e g i v et h ed e f i n i t i o no fr o m a nd o m i n a t i o nw i t hg r a p ht h e o r yi n19 9 9 f o rag r a p hg y e l e tf v 一 0 1 2 a n dl e t z 0 巧 砭 b et h eo r d e r e dp a r t i t i o no fvi n d u c e db yf w h e r e 杉 1 v l f v i a n df 杉l n f f o ri 0 1 2 af u n c t i o nf k 砭 i s ar o m a nd o m i n a t i n gf u n c t i o n r d f i f d o m i n a t e sv 0 i e 圪 v 0 a n dt h ew e i g h to ff i s f v 创厂 v 2 n 2 刀1 t h em i n i m u mw e i g h to fa l l r d fo fgi sc a l l e dt h er o m a n d o m i n a t i o nn u m b e ro fg d e n o t e db y g a n dw es a yt h a taf u n c t i o nf v 0 k i s a7 尺一f u n c t i o ni f i ti sa nr d f a n d 厂 矿 y 只 g i nt h i sp a p e r i t ht h ea l g o r i t h mo fc a l c u l a t i n gt h er o m a nd o m i n a t i o nn u m b e ro fg r a p h s w es t u d yt h er o m a nd o m i n a t i o nn u m b e ro fg e n e r a l i z e dp e t e r s e ng r a p h sp n 后 a n dc i r c u l a n t g r a p h sc 咒 1 后 a n dt h e ng e tt h ef o l l o w i n gc o n c l u s i o n s 1 烁 2 l 等b 5 m 卜 槲 q m 嘶 1 4 憎z 4 ni i胁4nl i ii j k c o 1 4 iiiii ll l i f 0 7 o r n 6 1 2 1 3 1 9 2 6 3 0 3 2 f o rg e n e r a l i z e dp e t e r s e ng r a p h sp n k a n dc i r c u l a n tg r a p h sc z l 尼 t h eu p p e r b o u n d so ft h e i rr o m a nd o m i n a t i o nn u m b e r sa r eg i v e n k e yw o r d s r o m a nd o m i n a t i o n d o m i n a t i o nn u m b e r d o m i n a t i n gs e t i i i 大连理工大学学位论文独创性声明 作者郑重声明 所呈交的学位论文 是本人在导师的指导下进行研究 工作所取得的成果 尽我所知 除文中已经注明引用内容和致谢的地方外 本论文不包含其他个人或集体已经发表的研究成果 也不包含其他已申请 学位或其他用途使用过的成果 与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意 若有不实之处 本人愿意承担相关法律责任 学位论文题目 差垫臣塑丝 蛰至竺压兰 茎立整墨垄翌塑篁 储鲐弓粥l 魄坦年上月旦日 大连理工大学硕士研究生学位论文 大连理工大学硕士研究生学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定 在校攻读学位期间 论文工作的知识产权属于大连理工大学 允许论文被查阅和借阅 学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版 可以将 本学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印 或扫描等复制手段保存和汇编本学位论文 学位论文题 作者签名 导师签名 大连理工大学硕士学位论文 1绪论 1 1前言 图论是组合数学的一个重要分支 也是离散数学的一个重要组成部分 它是研究某 些事物及它们之间关系的学科 现实世界中的许多事物 或对象 能用图表示其拓扑结构 把实际问题的研究转化为图的研究 利用图论的相关结论对这些问题作出分析和判断 因此 图论在自然科学和社会科学的许多领域有着广泛的应用 同时也是计算机科学的 重要基础 1 7 3 6 年 e u l e r 解决了k 6 n i g s b e r g 七桥问题 这是有文字记载的最早的图论研究文 献 因此 这一事件被大家认为是图论作为 f j 独立的学科出现的标志 1 8 4 7 年 k i r c h h o f f 为了解一类线性联立方程组而发展了树的理论 1 8 5 7 年 c a y l e y 在研究有机化学 领域的问题时 也研究了树的理论 在e u l e r 之后的二百年中 许多数学家各自独立地 研究了图论中的一些问题 但是其研究结果并没有形成一个较为完善的体系 由于图论 长期以来不是数学研究的主流领域 图论一直在缓慢地发展着 1 9 3 6 年 k 6 n i g 编写了 第一本图论专著 总结了图论二百年发展的主要成果 自二十世纪中期以来 现实世界的需要使得图论领域的研究呈现出蓬勃发展的趋 势 随着计算机技术的广泛应用 图论的研究也注入了新的活力 利用计算机技术解决 图论问题成为一个令人感兴趣的研究方向 1 9 7 6 年 美国的h a n k e r 等人利用计算机用 了1 2 0 0 小时的计算时间 解决了数学家们一百多年来所未能解决的一个著名的图论难 题一四色问题 这一事件表明计算机技术的应用促进了图论的研究与发展 因此 它在 图论的发展历史中占有一个重要的位置 图论最吸引人的特色是它蕴含着大量强有力的思想 漂亮的图形和巧妙的论证 同 时 图论又是最接近群众生活 最易于向科学水准低的人们阐述的一门学科 即使是非 常困难的尚未解决的问题也易于表达 问题外表的简单朴素和本质上的难以解决 使每 个搞图论的人在图论问题面前都必须谨慎严肃的思考问题 常常是一个貌似简单的问 题 即使是幸运的得出证明 证明中包含的细节也十分繁琐 并且往往需要极艰苦的计 算 图论发展至今 已经积累了许多难题 至今仍找不到有效的算法去解决 如求图中 h a m i l t o m 回路 r a m s e y 问题 笼问题以及计算任意图的支配数问题等等 这些问题均 属于n p 一完全问题 图的支配问题是近年来图论中一个比较活跃的研究领域 图的支配数是在实际问题中提出的 因此 在现实生活的许多领域都有广泛的应用 广义p e t e r s e n 图和循环图的罗马支配研究 例如 在一个通讯网络的一些节点上放置发射器 要求每个发射器的节点一定和某个发 射器的节点有一个直接的通讯线路 如何选择节点 使得放置的发射器的数目最小 对支配数的研究 目前国内外的研究集中在以下几个方面 1 支配数 2 完全支配数 3 罗马支配数 4 p a c k i n gn u m b e r 5 边支配数 1 2 基本概念 本文中未定义的术语请参见徐俊明的 图论及其应用 1 b o n d y 和m u r t y 的 g r a p h t h e o r yw i t ha p p l i c a t i o n 2 h a y n e s h e d e t n i 和s l a t e r 的 f u n d a m e n t a l so fd o m i n a t i o ni n g r a p h s 3 和 d o m i n a t i o ni ng r a p h s a d v a n c e dt o p i c s 4 我们称数学结构g y g e g 尼 为一个图 g r a p h 其中v v g 是一个非空 集 厶是从集合e g 到v g 矿 g 的一个映射 则称g 是一个以v g 为顶点集 以 e g 为边集的有向图 d i r e c t e dg r a p h v g 中的元素称为图g 的顶点 v e r t e x e g 中 的元素称为图g 的边 e d g e 尼称为g 的关联函数 若尼0 似v p e 耳g 1 9 1 坎g z 6 3 则简写成e u v 称材是有向边e 的尾 为有向边e 的头 在图中用箭头从 指向v 来表示一条有向边 如果把有向图中的箭 头取消 则得到无向图 u n d i r e c t e dg r a p h 一个图g 中项点的数目 称为图g 的阶 o r d e r 用i 坎o l 来表示 图g 中边的数目 即图g 的边数 s i z e 称为图g 的大小 用 以回l 来表示 若l 坎g i i 以g i 也称为u 的开邻域 而顶点集合n u 材 u n u 则称作顶点u 的闭邻接点 集合 c l o s e dn e i g h b o r h o o d 也称为u 的闭邻域 如果有两条或两条以上的边连接同一对顶点 则称这些边为多重边 两个端点重合 为一点的边称环 l o o p 不包含多重边和环的图称为简单图 s i m p l eg r a p h 大连理工大学硕士学位论文 本文所考虑的图均为无环 无重边的简单有限无向图 由图的定义可知 一个集合v 和v 上的一个二元关系就是一个图 因此图的最本质 的内容就是一个二元关系 也就是顶点和边的关联关系 一个系统或一个结构若具有二 元关系便可用图作为数学模型 设v v g g 中与v 关联的边的个数称为v 的度 d e g r e e 记作d v 其中每个环 在计算度数时被算作两条边 若d v 0 则称1 为孤立点 i s o l a t e dv e r t e x 若d v 1 则称v 为悬挂点 p e n d a n t v e r t e x 与悬挂点关联的边则称为悬挂边 p e n d a n te d g e 若图g 的各顶点的度数相同 则称图g 为 贝l j r e g u l a rg r a p h 若对任意的v v g d v 则称图g 为 正则 图 设g 是一个力阶 3 缸正则图 若对任意的u 1 y g u v 满足 1 若u 与v 相邻 则i n u n v i 力 2 若u 与v 不相邻 则i n v l 则称g 为具有参数 k 名 的强正则图 简称0 k 兄 a 强正则图 而且 w v o e v 一1 e k v k 为首尾相连的边的顺序排列 v 一 v 为e t 的端点 若w 中的顶点均不 相同 则w 称为路径 p a t h 含甩个顶点的路径记作 起点与终点重合的道路叫做回 路 c i r c u i t 或圈 c y c l e 含 个顶点的回路记作g 设 v v g 若在g 中存在一条 材 v 路径 则称顶点u 和v 是连通的 c o n n e c t e d 若g 中每一对不同的顶点都连通 则称g 为连通图 c o n n e c t e dg r a p h 否则称为非连通 图 d i s c o n n e c t e dg r a p h 我们称没有回路的简单连通图为树 t r e e 设 1 矿 g 若 v 连通 则称最短的 材 v 路径为测地线 g e o d e s i c 测地线的 长度称为u 与v 之间的距离 d i s t a n c e 记作d u y 若 v 不连通 则d u v 0 0 连通图g 中最长的测地线的长叫做g 的直径 d i a m e t e r 记作坊口聊 g 即 d i a m g m a x d u v u v y g 每对不同项点之间均有一条边相连的简单图称为完全图 c o m p l e t eg r a p h 玎个顶点 的完全图记作k 对于任意连通图g 朋 顶点v 矿 g 如果g v 不连通 则v 是g 的割点 对于g 的连通子图b 称为一块 b l o c k 当且仅当满足 任意子图b g bsb b b 至少有一个割点 一个块b 称为最后块 e n db l o c k 当且仅当满足 召至多包含一个割 广义p e t e r s e n 图和循环图的罗马支配研究 点 图g 称为块图 b l o c kg r a p h 当且仅当满足 g 的任何块 b l o c k 都是一个完全图 如果图g 包含唯一一个圈 则g 是个单循环图 如果每条边都至多在一个圈上 则g 成 为仙人掌图 c a c t u sg r a p h 一个图的顶点集矿若能分成两个非空子集x 和 使x uy v xn y a 且g 的每条边的两个端点分居在x 和 中 则称此图为二分图 b i p a r t i t eg r a p h 记作 g x y 有时记作 x y e x y 称为y 的一个二分戈u b i p a r t i t i o n 对于简单二分图g x y e 若x j x 咒 y 有 t 咒 e 则g 称为完全二 分l 至l c o m p l e t eb i p a r t i t eg r a p h 若i x m l y n 则记为e 墨 称为星 s t a r 设g 日是两个任意的图 若存在v g 到v h 上的一个一一对应函数厂 使得 v v g 刎 e g 当且仅当f u f v e 忉 则称g 日是同构的 i s o m o r p h i c 记为g 兰h 同构图具有相同的性质 一个无标号的图可被看作是所有与之同构的图的 代表 设简单图g v e 互 材 v u 1 甜 v v 则称图h v 巨 e 为g 的补图 c o m p l e m e n tg r a p h 记作h g 图g 和日 如果v h cv g e h e g 则称日为g 的子i 蛩 s u b g r a p h 记 为日 g 如果v h v g 或e h e g 称日为g 的真子图 t r u es u b g r a p h 记为 hcg 令集合scv g 若图g 的一个子图日满足如下关系 v h s 且 e h u v 甜 1 s 圳 e g 则称子图日是从集合s 导出的子图 简称为图g 的导 出子图 i n d u c e ds u b g r a p h 记作g s 若图g 的一个子图日满足v h v g 则称子 图日是图g 的生成子图 s p a n n i n gs u b g r a p h 在图g 中 如果顶点托 v 是相邻的 通常称 是u 的一个邻接点 顶点 的邻域集 合是图g 中所有与u 相邻的顶点的集合 记作 yiu v e g n u 似 un u 称作顶点u 的闭邻域 设u v g 称d u ln u i 为u 的度 图g 的顶点的最大度和最小度分别用a g 和a g 表示 若图g 的各项点的度相同 则称图g 为正则图 若任取u y g d k 则称 图g 为k 一正则图 称它的正则度为k 此时 n u vlu g e g 如图1 1 所示的图 为3 正则图 完全二分图k 是满足以下条件所构成的图类 大连理工大学硕士学位论文 1 顶点分为二个集合k 圪 其中lk m i i 刀 2 对于任意材 k v 巧 若f j 则 v 相邻 f 1 2 如图1 2 所示的图为k 2 4 完全二分图 图1 13 正则图 f i g 1 13 r e g u l a rg r a p h 我们把聊 1 时的完全二分图k 称为星图 已知图g v e 和h y e 如果v 日 y g e h e g 并且日中边 的重数不能超过g 中对应边的重数 则称日是g 的 s u b g r a p h 记作 g 图1 2 k 2 4 完全二分图 f i g 1 2 k 2 4c o m p l e t eb i p a r t i t eg r a p h 如果h 是g 的子图 并且h g 则称日是g 的真子图 p r o p e rs u b g r a p h 记作 hcg 已知图日是g 的子图 并且v h v g 则称日是g 的生成子图 s p a n n i n g s u b g r a p h 如图1 3 所示 其中 2 3 分别是图g 的子图 4 是图g 的生成子图 已知图g v e 和h 矿 e 如果v h sy g e 日 e g 并且日中边 的重数不能超过g 中对应边的重数 则称日是g 的予图 s u b g r a p h 记作日冬g 如果日是g 的子图 并且h g 则称日是g 的真子图 p r o p e rs u b g r a p h 记作 hcg 已知图g y e s 是矿的一个非空子集 以s 为顶点集 以两端点均在s 中的边 的全体为边集所组成的子图 称为由s 导出的g 的子图 记作g s 或简称g s 是g 的 广义p e t e r s e n 图和循环图的罗马支配研究 导出 子 i n d u c e ds u b g r a p h 图g 的一个顶点和边相继交替出现的有限非空序列w r o e l v l e 2 l i i e t v t 其中e 的端点是v h 和1 1 i k 叫做从v 到1 的一条途径 1 2 3 图1 3 子图与生成子图 f i g 1 3s u b g r a p ha n ds p a n n i n gs u b g r a p h 4 若途径w r o e l l l e 2 v t 1 e t 咋的顶点和边均不相同 则称形为通路 p a t h 起点和终点重合的通路叫做回路 c i r c u i t 或称为圈 c y c l e 设 v g 如果甜和v 连通 则称最短的 1 一通路为测地线 g e o d e s i c 测地 线的长称为u 与v 之间的距离 记作d u 1 一个连通图g 中任何一条最长的测地线的长叫做g 的直径 d i a m e t e r 记作d g 即 d g m a x d u v iu v y g 1 3 支配集和支配数 1 3 1 起源与发展 虽然图的支配集的相关研究开始于1 9 6 0 年 但这个问题的相关领域的研究最早可 以追溯一百多年前 18 6 2 年 j a e n i s c h t 5 研究了如下一个问题 问题1 1 确定覆盖 或支配 个n 聆国际象棋棋盘所需王后的最小个数 在18 9 2 年出版的 m a t h e m a t i c a lr e c r e a t i o na n dp r o b l e m so fp a s ta n dp r e s e n tt i m e s 中 r o u s eb a l l t 6 1 总结了1 9 世纪末关于国际象棋棋盘上的组合问题的研究分为如下三个 基本类型的问题 1 覆盖问题 覆盖 攻击或支配 一个刀 刀棋盘上所有格子所需的某种棋子 王 王后 马 相 车和卒 的最小个数 这个问题实质是在以棋盘格子为顶点 以棋子的某种走法为边所 产生的图 在该图上求其元素个数最小的支配集 大连理工大学硕士学位论文 2 独立覆盖问题 支配一个n r 棋盘上所有格子所需的彼此互不攻击的某种棋子的最小个数 这个 问题实质是在以棋盘格子为顶点 以棋予的某种走法为边所产生的图 在该图上求其 元素个数最小的独立支配集 3 最大独立集问题 在棋盘上的格子中放入某种棋子 要求任意两个棋子之间彼此互不攻击 支配 按 这种方法 最多能放多少个棋子 这个问题实质是在以棋盘格子为顶点 以棋子的某种 走法为边所产生的图 在该图上求其元素个数最大的独立集 当我们选用的棋子为王后 这个问题就是著名的 皇后问题 1 9 6 4 年左右 y a g l o m l 7 兄弟研究了这三类问题 对于棋子王 马 相和车的情形 他们对上述问题给出了一个很优美地结果 表1 1 1 9 9 8 2 0 0 7 美国数学评论收录的有关支配数的文章统计结果 t a b 1 1 d o m i n a t i o np a p e r sf r o mm r i n19 9 8 2 0 0 7 b e r g e 8 在他于1 9 6 2 年出版的图论书中 第一次提出了图的支配数的定义 当时他称 之为c o e f f i c i e n to fe x t e r n a l s t a b i l i t y 同一年 在o r e 9 1 出版的图论书中第一次使用了图 的支配集和图的支配数的概念 他用d g 表示一个图g 的支配数 到了1 9 7 7 年的时候 c o c k a y n e 和h e d e t n i e m i 为到当时为止在支配问题领域的所有结果写了一篇综述 在这 篇综述中 c o c k a y n e 和h e d e t n i e 觚 l o 第一次使用y g 表示一个图g 的支配数 从此以 后 支配数的概念和表示符号就固定下来 被人们接受了 c o c k a y n e 和h e d e t n i e m i 的这篇文献综述开启了支配理论现代研究的序幕 到1 9 9 8 年为止 在这二十年中 有关支配理论的义献超过了1 2 0 0 多篇 并且还在不断地稳步 增长中 利用美国数学评论的搜索引擎 我们检索了1 9 9 8 年 2 0 0 6 年间美国数学评论 收录的文献中 分类号为0 5 c 图论问题 并且题目中带有支配数的文献 得到的结果如 表1 1 所示 这说明支配问题的研究在现代图论研究中占有一个重要的地位 1 3 2 支配数的基本概念 文献 3 的附录中给出了7 0 多种支配数及相关类型的集合的定义和简单说明 在本 文中给出基本支配数 连通支配数和树支配数的定义及它们相关集合的定义 广义p e t e r s e n 图和循环图的罗马支配研究 定义1 1 令集合s 是一个任意图g 的顶点集的子集 即 5 sy g 如果对任意顶 点v 坎g 有w n s 则称s 是图g 的一个支配集 d o m i n a t i o ns e t 如果它的任何真 子集都不是图g 的支配集 我们称s 为图g 的一个极小支配集 m i n i m a ld o m i n a t i n gs e t 如果对任意一个图g 的极小支配集s 他们满足l s f f s f 则我们就称极小支配集s 为 图g 的一个最小支配集 m i n i m u md o m i n a t i n gs e t 则把集合s 的元素个数称为图g 的支 配数 d o m i n a t i o nn u m b e r 记作 g 定义1 2 令集合s 是一个图g 的顶点集的子集 即s y g 如果集合s 是图g 的一个支配集 且其导出子图g 嘲是连通的 那么称集合s 是图g 的一个连通支配集 c o n n e c t e dd o m i n a t i o ns e t 如果对任意一个图g 的连通支配集s 满足i s l l s i 称连 通支配集s 为图g 的一个最小连通支配集 m i n i m u mc o n n e c t e dd o m i n a t i n gs e t 则把集 合s 的元素个数称为图g 的连通支配数 c o n n e c t e dd o m i n a t i o nn u m b e r 记作r a g 定义1 3 设图g 含有的顶点数i g i 如果删除任何一个至多含有r 一1 个点的集合 s 后 g 坎回 翻是连通的 则称g 是r 连通的 定义1 4 设图g 如果g 是 连通的 则g 有一个支配集s 且g 嘲是个厂连通的 子图 那么这个支配集s 就称为一个 连通支配集 图g 的最小 连通支配集的大小记 作 g 图1 4 图g 和其补图g f i g 1 4 t h eg r a p hga n di t sc o m p l e m e n tg r a p hg 定义1 5 令集合s 是一个图g 的顶点集的子集 即s 矿 g 如果集合s 是图g 的一个支配集 且其导出子图g 阎是树 那么我们称集合s 为图g 的一个树支配集 t r e e d o m i n a t i n gs e t 如果对任意一个图g 的树支配集f 满足i s i i s l 称该树支配集s 为 图g 的 个最小的树支配集 m i n i m u mt r e ed o m i n a t i n gs e t 则把集合s 的元素个数称为 图g 的树支配数 t r e ed o m i n a t i o nn u m b e r 记作o g 定义1 6 一个集合s v g 叫做一个g 的p a c k i n g 集当且仅当任意两个点 1 s 时 都有d u y 3 也就是说s 是一个p a c k i n g 集当且仅当任意1 y g 有 大连理工大学硕士学位论文 in v f q si 1 p a c k i n gn u m b e r 就是所有p a c k i n g 集当中所含顶点数最少的集合s 的元素 个数 记为p a 定义1 7 对于图g 定义函数f e g 一 1 一1 为边支配函数其中对于e e g 有 厂 p l 图g 的边支配数为y g m i n 叫g 厂 p i 俜一个边支配函数 定义1 8 设简单图g v e e l 材 v iu v u v 则称图h y 巨 e 为 g 的补图 c o m p l e m e n tg r a p h 记作h g 或g 如图1 4 所示 定义1 9 我们称图g h e 为图的连接运算 其中图g 是通过将顶点u y 日 与顶点v v f 合并成一个顶点u 图中其它的边和顶点保持不变 如图1 5 所示 一 一1 图1 5 两个图的连接运算 f i g 1 5 t h ea s s o c i a t i v eo p e r a t o rb e t w e e nt w og r a p h s 定义1 1 0 对于图g v e 设f v 一 0 1 2 且 k 圪 是由厂诱导出的点集y 的有序集 其中当f o 1 2 时 杉 v v l f v 且i l 刀 由于厂 y 专 o 1 2 和矿的 有序集 k 之间存在1 1 的映射关系 所以我们可以写成f 圪 k 砭 函数厂 v o v l 圪 是罗马支配函数 r d f 当 其中 指集合 支配 如 v o 畋 f 的权重是厂 y 删 v 2 n 以 罗马支配数用厂 g 表示 它等于图g 的r d f 的最小的权重 当f v o k 圪 是 一个r d f 且f v g 我们称它是一个y r f u n c t i o n 定义1 1 1 对于每个顶点v v g 都被支配了iu v n s1 次 我们定义个函数以用 来记录一个顶点v 被重复支配的次数 r d v in v n si 1 对于一个顶点集合v 互v g 令r d v r d v 万 1 3 3 支配数的计算复杂性 计算任意一个图的支配数是一个很复杂的问题 即使是我们把问题减小到只针对一 类具体的图来计算支配数 也不一定能够得到一个多项式时间的有效算法 广义p e t e r s e n 图和循环图的罗马支配研究 表1 2 给出了上面介绍的两种支配数的对若干类图的计算复杂性 其中n p 表示问 题是n p 问题 p 表示问题存在多项式时间的有效算法 表1 2 支配数的计算复杂性 t a b 1 2 c o m p u t i n gc o m p l e x i t yo fd o m i n a t i o nn u m b e r 从表中可以看出除了一些简单图我们可以找到一个多项式算法以外 别的图都是 n p 困难问题 所以就目前为止我们只能对某一类图进行研究 1 3 4 支配集的应用 在 f u n d a m e n t a l so f d o m i n a t i o ni ng r a p h s 的引言和第一章中 h a y n e s h e d e t n i e m i 和s l a t e r 等人给出了几类支配集的应用例子 支配集和网络设计有很大关系 近年来 传感器网络和移动自组网络的应用中 连 通支酉己集占有一个很重要的地位 因为这两类网络的拓扑结构是随机的 不断发生变化 的 因此在网络通讯中需要构建一个虚拟的骨干网 而这个问题实质上是在一个图中寻 找连通支配集 这方面的主要讨论见文献 1 1 1 6 1 4罗马支配的起源与发展 据可查的文献记载 军事驻扎问题始于康斯坦丁大帝四世时期 他所遇到的问题就 是为了避免受到别国入侵 如何部署罗马军队 公元三世纪 当罗马统治欧洲的时候 他们能通过部署帝国的军队来保护5 0 个地区即使是最远的地区 随后一个世纪 罗马 帝国军事力量下降 削减到只能部署2 5 个地区 康斯坦丁大帝提出这样一个问题 在 不放弃核心 罗马 的情况下如何驻扎军队使其有更强的力量来保护帝国前方的领土 他设计了一下防御策略来处理下降的罗马政权 首先 它把军队集中划分成若干个 军团 p e b b l e 保证每个军团都有能力防御罗马的任何一个地区 一个地区被认为是 安全的当他本身有这样的军团驻扎或者在他邻近的地区有两个以上的这样的军团驻扎 如图1 6 1 7 可以用四支军队来保护罗马 1 9 9 7 年r e v e l l e 在 1 7 8 中提出了罗马阀题 1 9 9 9 年及2 0 0 0 年s t e w a r t 和r e v e l l e 大连理工大学硕士学位论文 在 1 9 2 0 q h 发起了罗马支配的研究 2 0 0 0 年7 月e r n i ej c o c k a y n e 和p a u la d r e y e rj r 等人在 2 1 q h 给出了罗马支配数的一些结论 1 对于任意图g r g y r g 2 y g 2 对于任意n 个点的图g y g g 当且仅当g k 3 对于任意的 一f u n c t i o nf 厂 k 则 k 的导出子图g 阮 的度最大为1 k 和吒中的点不会有连边 中的点最多跟两个与k 相邻的点 以是图g v ou 一个7 一s e t 一 设日 g v ou 则每一个点1 最少有两个日一p n n 一 如果v 是g 畋 中的孤立点且只有一个外部的h p n 称为w v o 则 n w nk 矽 设g 眈 中的非孤立点的个数为后 使c 1 v o l v n l 2 1 rc i c i 则 n o n 2 k t c f i g 1 6s i m p l eg r a p h1o fr o m a n 4 对于刀个顶点且其最大度数为 的图g 五2 石n g 5 对于聆个顶点的图g g z 墨旦号宰铲 6 对于完全 z 分图g k 其中朋l m 2 m 则 广义p e t e r s e n 图和循环图的罗马支配研究 如果m 1 3 则y r g 4 如果m 1 2 则y r g 3 如果m 1 1 则y 月 g 2 7 如果g 是有以个结点的连通图且 g 厂 g 1 当且仅当有一个点v v 其度 为n r g 8 如果g 是有n 个结点的连通图且 g f g 2 当且仅当 不存在点v v 其度为刀一y g 存在一个点v v 其度为n r g 一1 或者g 有两个点v 和w 能够使得 i v u w n y g 2 9 如果g 是r o m a n 当且仅当它有一个y r f u n c t i o nf f v o k v 2 有 n l 吲 0 f i g 1 7s i m p l eg r a p h2o fr o m a n 2 0 0 1 年7 月m i c h a e la h e n n i n g 和s t e p h e nt h e d e t n i e m i 在 2 2 中探索出一种新的 策略在仍然保护罗马帝国的情况下 使得军事消耗尽可能少 并得出以下结论 1 对于任意图g 的罗马支配函数r d f 也是该图的弱罗马支配函数形胜洒 2 对于任意图g g y g g 2 y g 3 当n 3 时 只 c l 2 n 3i 4 如果一个图g 有7 个顶点的路径p 路径内的第一个点的度至少为2 则对于 图g 的任意一个w r d f 厂有 厂 矿 尸 3 5 对于任意图g 的任意点甜 通过从点 增加一个长为7 的路径所得的图日满足 大连理工大学硕士学位论文 以 日 以 g 3 6 凯 1 时 从驴引 7 如果图h 是图g 的生成子图 则 以 g 以 日 8 如果图g 有一个以 g 一f u n c t i o n 存在两个相邻的点u 和v 其值为0 则 以 g 以 g u v 1 1 9 当刀 4 时 以 g 7 j 等i l l 1 0 对于任意图g z g 以 g 当且仅当存在一个y g 一s e ts 满足 对于任意的点1 s p n v s 导出一个团 对于任意的非s 的私有邻域的点u v g 一s 存在一个点v s 使得 p n v s u u 导出一个团 1 1 如果图g 满足2 y g 以 g 则对于每一个z g 一s e ts 和每一个点v s 集 合e p n v s 包括两个不相邻的点 1 2 弱罗马支配w r d f 属于 p c o m p l e t e 问题 即使是二部图或者弦图 2 0 0 1 年1 2 月m i c h a e la h e n n i n g 在 2 3 中用图论的理论给出了通过驻扎尽可能少的 军队来防止罗马军队同时受到多处攻击的一些定义和概念 并得出以下结论 1 对于任意的连通图g 并且k l 显然有r g y g 2 对于任意的连通图g v e k 1j ty g y g 如果s 是一个y g s e t 则 对于任意的v s e p n v s u v 是一个团 对于任意的非s 中点的私有邻域的点甜 v s 存在一个点v s 使得 u 卜e p n v s u v 3 当k 1 时 一个树丁满z y zz t 7 丁 当且仅当k 1 而且丁 f 或者尼 1 而且 丁是一个树的冠 4 对于任意的连通图g 并且k 1 有蝶 g k 1 g 5 对于任意的连通图g v e k 1 且y g k 1 r g 对于每一个 y g 一s e ts 和每一个点v s e p n v s 包括一个k 1 个点的独立集 6 对于一个度最少为3 的树r 丁只有唯一的一个y 丁 一s e t 当且仅当丁有一个 r t 一s e ts 使得对于任意一个点v s 有ie p n v s i 2 广义p e t e r s e n 图和循环图的罗马支配研究 7 如果k 1 且树丁满足蝶 z 七 1 厂叮 则7 有唯一的一个r t s e t 8 如果k 1 且树丁有唯一的一个y t s e ts 则瓯 1 t 量s 9 如果七 l 且树丁有唯一的一个7 丁 一s e ts 且s 的每一个点都是 七 1 一s u p p o r t 则7 t k 1 r t 1 0 如果k 1 且树丁有唯一的一个y 丁 一s e ts 且s 的每一个点都不是 尼 1 一s u p p o r t 则y 丁 后 1 y 丁 1 1 如果森林f 有唯一的一个y f 一s e ts 且f 有一部没有 k 1 一s u p p o r t 的点 贝0 y f 1 1 1 v l v o 2 v 2 v 2 v o u 3 l 3 v 3 v o f i l 矿 e 1 e f 1 1 l 1 l 1 2 v o u 2 u 3 甜1 1 l v l v 2 v 2 v o v o l 9 2 v o u 3 2 0 0 6 年h e n n i n gf e m a u 在 2 8 中给出了一种用参数化的方法来计算图的罗马支配 数 并得出对于任意的图罗马支配的计算时间复杂度是r v 2 卜c o m p l e t e 2 0 0 6 年7 月李书超和朱忠熏在 2 9 中利用图论的方法研究了图g 以及同其补图g 的 r o m a n 控制数 得到了完全图和完全多部图的补图的r o m a n 控制数及图g 同其补图g 的r o m a n 控制数的关系 还研究了图g 的生成子图日同g 的r o m a n 控制数的关系和极 大无完美匹配的简单图g 的r o m a n 控制数 2 0 0 6 年10 月f ux u e l i a n g 和y a n gy u a n s h e n g 在 30 中针对e m i ej c o c k a y n e 和p a u l 广义p e t e r s e n 图和循环图的罗马支配研究 a d r e y e rj r 等人在2 0 0 0 年提出的公开问题 给出了一些属于罗马图的正则图并得出以 下结论 1 当刀 7 且 2 4 m o d 5 循环图c n 1 3 是罗马图 2 当 z 4 n 2 k f 1 2 k b 2 且 2 l m o d 2 k 1 循环图c n 1 2 后 是罗 马图 l 盟 1 3 当胛 0 m d 4 e i o k 毕时 广义p e t e r s e n 图尸 殇2 七 1 是罗马图 4 当n 3rn 2 m o d 4 时 广义p e t e r s e n 图p n 1 是罗马图 5 当刀 11 或者1 7 gn 3 模4 时 广义p e t e r s e n 图p n 3 是罗马图 6 当n 1rm 1 时 笛卡尔积g m c 5 是罗马图 2 0 0 6 年1 2 月r u b a l c a b a 和s l a t e r 在 3 1 q b 给出了罗马支配数的影响参数的定义 并 得出以下结论 1 对于任意1 1 个点的图g 有只 g 刀 r 露 g 2 对于任意的图g 有疋 g f g 3 对于任意刀 z 3 个点的图g 且疋 g n 则对于任意的有效的罗马支配函数 厂有k 4 f r g 眇 g j 表示r 霄 g 陟 g i 但是反过来却不成立 5 对于任意的图g 有r 尺 g r g 6 对于任意有刀个点的树丁 有r 尺 t 胛 2 0 0 7 年12 月f a v a r o n 和k a r a m i 等人在 3 2 中针对e m i ej c o c k a y n