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

图的弱罗马控制

作　者: 杨剑
导　师: 宋晓新
学　校: 河南大学
专　业: 运筹学与控制论
关键词: 控制数树弱罗马控制数
分类号: O231
类　型: 硕士论文
年　份: 2007年
下　载: 54次
引　用: 1次
阅　读: 论文下载

内容摘要

基于Ian Stewart[11]发表的一篇论文（Defend the Roman Empirel，scientific Amer-ican，Dec．1999，pp．136-138）的意图，M．A．Henning和S．T．Hedetniemi[1]提出了防御罗马帝国的新策略使最高统治者既节约了给养军团的基本花费又能防御罗马帝国．用图论的术语，设G=（V，E）是一个图，f∶V（?）{0，1，2}是一个定义在图G的顶点集V上的函数．对f来说一个f（u）=0的顶点u被称为未防御点，如果它不与任何带有正权的顶点相邻．函数f被称为弱罗马控制函数（简称WRDF），如果对每一个f（u）=0的顶点u，都与一个f（v）＞0的顶点v相邻，并且函数f′∶V（?）{0，1，2}，使得f′（u）=1，f′（v）=f（v）－1且f′（w）=f（w），（?）w∈V－{u，v}，没有未防御点．函数f的权记为w（f）=∑_v∈Vf（v）．图G的弱罗马控制函数的最小权称为弱罗马控制数，记为γ_r（G）．在本文中，研究了图的不同控制数的一些理论性质，并且刻画了树T满足γ_r（T）=γ（T）的特征和图G满足γ_r（G）=γ（G）+1的特征，以及满足γ_r（G）=2_γ（G）的图G的一些性质．

全文目录

中文摘要  3-4
英文摘要  4-6
第一章引言  6-8
第二章记号  8-10
第三章相关的已知结果  10-13
  §3.1 图的罗马控制  10-12
  §3.2 图的弱罗马控制  12-13
第四章主要结果与证明  13-41
  §4.1 弱罗马控制数的一些特殊值  13-21
  §4.2 弱罗马控制数的上下界  21-25
  §4.3 树T满足γ_Υ(T)=γ(T)  25-32
  §4.4 图G满足γ_Υ(G)=γ(G)+1  32-39
  §4.5 图G满足γ_Υ(G)=2_γ(G)  39-41
参考文献  41-42
致谢  42

图的弱罗马控制

内容摘要

全文目录

相似论文