学位论文 > 优秀研究生学位论文题录展示

广义Petersen图和循环图的罗马支配研究

作　者: 吉春年
导　师: 林晓惠
学　校: 大连理工大学
专　业: 计算机软件与理论
关键词: 罗马支配支配数支配集广义Petersen图循环图
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 40次
引　用: 0次
阅　读: 论文下载

内容摘要

罗马问题始于康斯坦丁大帝四世时期的军事驻扎问题。公元三世纪，当罗马统治欧洲的时候，通过部署帝国的军队，他们能防御50个地区包括最边远的地区。随后一个世纪，罗马帝国军事力量下降，这时如何驻扎尽可能少的军队来防止罗马军队同时受到多处攻击成了一个主要问题。1997年ReVelle提出了罗马问题，1999年及2000年Stewart和Revelle发起了罗马支配的研究，并用图论的理论构造了罗马支配数。对于图G=（V，E），设f：V→{0，1，2}且（V₀，V₁，V₂）是由f诱导出的点集V的有序集，其中当i=0,1,2时，V_i={v∈V|f（v）=i}且|V_i|=n_i。函数f=（V₀，V₁，V₂）是罗马支配函数（RDF）当V₂（?）V₀，其中（?）指集合V₂支配V₀，即V₀∈N[V₂]。f的权重是f（V）=∑_v∈Vf（v）=2n₂+n₁。罗马支配数用γ_R（G）表示，它等于图G的RDF的最小的权重。当f=（V₀，V₁，V₂）是一个RDF且f（V）=γ_R（G）我们称它是一个γ_R-function。鉴于广义Petersen图和循环图的重要性，本文根据前人的研究成果，针对广义Petersen图P（n，k）、循环图C（n；{1，k}），使用罗马支配算法求得罗马支配集中通用的规律，然后研究了它们的关系，以及一些情况下的精确值。主要得出以下结论：（1）γ_R（P（n,2））=（?）8n/7（?）（n≥5）.（2）（?） t=0,7或者n=6,12,13,19,26,30,32，其它情况.同时给出了广义Petersen图P（n，k）以及循环图C（n；{1，k}）的罗马支配数的上界。

全文目录

摘要  4-5
Abstract  5-7
1 绪论  7-26
  1.1 前言  7-8
  1.2 基本概念  8-12
  1.3 支配集和支配数  12-16
    1.3.1 起源与发展  12-13
    1.3.2 支配数的基本概念  13-15
    1.3.3 支配数的计算复杂性  15-16
    1.3.4 支配集的应用  16
  1.4 罗马支配的起源与发展  16-23
  1.5 Petersen图和循环图C(n;{1,k})  23-24
  1.6 本文的工作  24-26
2 广义Petersen图P(n,2)的罗马支配数  26-38
  2.1 广义Petersen图P(n,2)的罗马支配数上界  26-28
  2.2 广义Petersen图P(n,2)的罗马支配数下界  28-38
3 循环图C(n;{1,4})的罗马支配数  38-43
  3.1 循环图C(n;{1,4})的罗马支配数上界  38-40
  3.2 循环图C(n;{1,4})的罗马支配数下界  40-43
4 广义Petersen图P(n,k)和循环图C(n;{1,k})的罗马支配数上界  43-48
  4.1 广义Petersen图P(n,k)的罗马支配数上界  43-45
  4.2 循环图C(n;{1,k})的罗马支配数上界  45-48
5 图的罗马支配数算法  48-51
结论  51-52
参考文献  52-55
攻读硕士学位期间发表学术论文情况  55-56
致谢  56-57

广义Petersen图和循环图的罗马支配研究

内容摘要

全文目录

相似论文