高 红， 黄 佳 欢， 尹 亚 男， 杨 元 生

( 1.大连海事大学 理学院， 辽宁 大连 116026；2.大连理工大学 计算机科学与技术学院， 辽宁 大连 116024 )

0 引 言

图的罗马控制[1]起源于古罗马帝国的军事防御问题[2]．公元4世纪，君士坦丁大帝为了保障帝国的安全在军团数量十分有限的情况下制定了部署和调动军队的规则：(1)每个地区最多能部署两组军团．(2)一个地区如果没有驻军，在其受到外来侵略时，相邻地区必须能派出援军．(3)一个地区必须拥有两组军团才能派出一组军团去支援相邻地区．如果一个地区部署0/1/2组军团，那么可以看成是将该点赋值为0/1/2．如果古罗马帝国(图G)中每个地区(顶点)都对应着一个数字——0、1或者2，于是，军队的部署方案可以看成是从图G的顶点集合V到{0，1，2}的映射f，即f：V→{0，1，2}．根据部署规则，所有函数值为0的顶点其邻域中至少有一个函数值为2的顶点，函数f称为图G上的罗马控制函数．图G中所有顶点函数值的总和称为f的权重．罗马控制函数权重的最小值称为图G的罗马控制数，记为γR(G)．确定图的罗马控制数已成为学者们关注的热点问题．

意大利控制[3]是罗马控制的一种推广，其定义如下．

图的意大利控制也被称为罗马{2}-控制[4]或弱{2}-控制[5]．确定图的意大利控制数是NP困难的，吸引了国内外很多研究者的关注．文献[3]研究了树图T的意大利控制数与经典控制数之间的关系．文献[6]研究了树图的意大利控制数，证明了树图意大利控制数与其2-彩虹控制数相等．文献[5]确定了圈与圈的笛卡……