路径交图的罗马{2}-控制数研究

发布时间：2022-01-16 04:19

　　图的控制理论起源于运筹与优化中的实际问题,是图论的一个重要研究方向。随着网络和大数据技术的发展,人们面临的图都是规模较大、结构超级复杂的图。笛卡尔乘积图（交图）是一种很重要的图类,其规模大、结构也复杂。研究交图的控制数具有理论意义和应用价值。罗马{2}-控制（也叫意大利控制或弱2控制）是一种新型的控制。罗马{2}-控制可以描述成这样的一个防御问题:在古罗马帝国（图G）,每个城市（顶点）最多能安置两支部队防守,有部队防守的城市是安全的。如果没有部队防守的城市都至少与两个有一支部队的城市相邻或至少与一个有两支部队的城市相邻,那么这个城市也是安全的。如果罗马帝国的所有城市都是安全的,那么这种安置部队的方式就是罗马{2}-控制函数。在保证所有城市都是安全的情况下,所需的最少部队数量就是图G的罗马{2}-控制数。本文研究的是路径与路径笛卡尔乘积图（路径交图）Pn□Pm的罗马{2}-控制数。确定图的罗马{2}-控制数是NP困难的。本文根据Pn□Pm的特点,研制了有效的分支限界条件,根据这些条件,设计计算机算法,构造了可递推的罗马{2}-控制函数。利用这些函数可以计算出Pn□Pm的罗马{2}-控制数... 

【文章来源】：大连海事大学辽宁省 211工程院校

【文章页数】：66 页

【学位级别】：硕士

【部分图文】：

图６口怂??Ｆｉｇ．?２．２?Ｇｒａｐｈ?ＰｎＵＰｍ??

?大连海事大学硕士学位论文???０?１?０??Ｈ??１?０?１??／］?０?１?０??／２?０?０?１??ｈ?２?０?０??／ｉ?０?０?１??Ｒ??／．－＞?０?１?０??ｋ?１?０?０??ｈ?〇?０?２??／Ｋ?１?０?〇??ｈ?０?１?０??／２?〇?０?１??／；Ｊ?２?０?０??Ｔ??／１?０?０?１??０?１?０??ｉ?ｎ?ｌ??／ｍ，３??图４．２?／＾ＱＰ；对应的罗马｛以－控制数．／；ｆＵ??Ｆｉｇ．?４．２?ｃｏｒｒｅｓｐｏｎｄｉｎｇ?ｔｏ／ｉ??定理４．３当／ｊ２?７并且《?＝?ｌ（ｍｏｄ８）时，??证明：当《２７并且＂Ｅｌ（ｍｏｄ８）时，构造的函数人３如下，其中－１，??〇＜７＜２．??２，／?ｅ?４（ｍｏｄ?８）八丨＝０，?１?＜／＜／？?—?２，??／?三?０（ｍｏｄ?８）八）＝２，?＼＜ｉ＜ｎ?—?２，??１，?ｉ?—?０ｉ?ｎ?—?ｌＡｊ?—?＼，??？?／?＝?１，ｗ?—?２?八户２，??人＇３（Ｖ，ｖ）—?／?＝?ｌ，７（ｍｏｄ８）Ａ?ｙ?＝?０，?ｌ＜／＜？－ｌ，?（４３＞??三?２（ｍｏｄ４）八?／?＝?１，?１?＜?／?＜?／？?１，??／?＝?３，５（ｍｏｄ?８）?Ａ?ｊ?—?２，?１?＜／＜／？?—?１，??０，其他．??图４．３是根据（４．３）式给出的心口／Ｖ匕的函数．／；７，３。可以验证，这样构造的人３满足??罗马｛２卜控制函数的定义。实际上，对于任意的点ｖ＾．ｅＧ，有??或者｛Ｖ，．卜丨，ｖＷＪ｝或者｛ｖ，＿ｌ；而＋丨｝或者｛Ｖ，ｖ＿丨，??－１５?－??

?大连海事大学硕士学位论文???２，ｚ？三?４（ｍｏｄ８）八ｙ?＝?０，?ｌ＜ｉ＜ｎ?—?２，??ｚ．三?０（ｍｏｄ?８）八?ｙ．?＝?２，?１?＜／＜／？?—?２，??１，?ｉ?＝?〇Ａ?ｊ?＝?ｌ??ｉ?＝?ｌＡ?ｊ?＝?２，??乂，．３?（Ｖ，ｖ）?＝?ｉ?＝?ｎ－＼Ａｊ?＝?０，?（４．４）??ｚ．三?１，７（ｍｏｄ?８）八?ｙ?＝?０，?＼＜ｉ?＜ｎ?—?ｈ??ｆ?三?２（ｍｏｄ?４）八）＝１，?＼＜ｉ＜ｎ?—?＼，??ｚ？三?３，５（ｍｏｄ８）八）＝２，＼?＜ｉ?＜ｎ?—?ｈ??０，其他．??〇?１?ｏ??／／??１?０?１??／ｉ?０?１?０??ｌ２?０?０?１??／３?２?０?０??／４?０?０?１??Ｒ??ｋ?〇?１?０??／６?１?０?０??／７?０?０?２??Ｉｎ?１?０?０??／ｉ?０?１?０??ｌ２?０?０?１??／３?２?０?０??／４?０?０?１??Ｔ??ｋ?〇?１?〇??ｋ?１?〇?０??０?０?２??１?１?０??／ｌＳ．３??图４．４?对应的罗马｛２卜控制数／ｊｙ??Ｆｉｇ．?４．４?／ＪｇＤＰ，?ｃｏｒｒｅｓｐｏｎｄｉｎｇ?ｔｏ／］８＞３??图４．４是根据（４．４）式给出的匕口／＾上的函数／ｊ８，３。可以验证，这样构造的人３满足罗??马｛２｝－控制函数的定义。实际上，对于任意的点ｖ，ｖｅＫ，有??者ｖ，＋１Ｊ或者｛Ｖ，—ｌ７．，ｖ，；＋ｌ｝或者｛ｖ，，?ｐｖ，—ｌｙ．｝或ｂ??－１７?－??

【参考文献】：
期刊论文
[1]两类图的符号控制数[J]. 闫云娟,徐保根,冯大一.  华东交通大学学报. 2017(06)
[2]关于图的两类符号控制数的下界[J]. 尚华辉,苗连英.  数学的实践与认识. 2017(21)
[3]网格图的2-彩虹控制数[J]. 邵泽辉.  成都大学学报(自然科学版). 2013(01)
[4]图的弱罗马控制[J]. 陈越奋,杨剑.  信阳师范学院学报(自然科学版). 2012(01)
[5]图的全符号控制数[J]. 吕新忠.  中国科学（A辑:数学）. 2007(05)

硕士论文
[1]图的双罗马控制[D]. 陈优.郑州大学 2018
[2]循环图的两类控制数研究[D]. 段伟.大连海事大学 2018
[3]若干图类的全符号控制数的研究[D]. 曹惠萍.大连海事大学 2016
[4]图的笛卡尔乘积的控制数与罗马控制数[D]. 裴利丹.安徽大学 2014
[5]图的弱罗马控制[D]. 杨剑.河南大学 2007



本文编号：3591923