圖的控制理論起源于運籌與優(yōu)化中的實際問題,是圖論的一個重要研究方向。隨著網(wǎng)絡(luò)和大數(shù)據(jù)技術(shù)的發(fā)展,人們面臨的圖都是規(guī)模較大、結(jié)構(gòu)超級復(fù)雜的圖。笛卡爾乘積圖（交圖）是一種很重要的圖類,其規(guī)模大、結(jié)構(gòu)也復(fù)雜。研究交圖的控制數(shù)具有理論意義和應(yīng)用價值。羅馬{2}-控制（也叫意大利控制或弱2控制）是一種新型的控制。羅馬{2}-控制可以描述成這樣的一個防御問題:在古羅馬帝國（圖G）,每個城市（頂點）最多能安置兩支部隊防守,有部隊防守的城市是安全的。如果沒有部隊防守的城市都至少與兩個有一支部隊的城市相鄰或至少與一個有兩支部隊的城市相鄰,那么這個城市也是安全的。如果羅馬帝國的所有城市都是安全的,那么這種安置部隊的方式就是羅馬{2}-控制函數(shù)。在保證所有城市都是安全的情況下,所需的最少部隊數(shù)量就是圖G的羅馬{2}-控制數(shù)。本文研究的是路徑與路徑笛卡爾乘積圖（路徑交圖）Pn□Pm的羅馬{2}-控制數(shù)。確定圖的羅馬{2}-控制數(shù)是NP困難的。本文根據(jù)Pn□Pm的特點,研制了有效的分支限界條件,根據(jù)這些條件,設(shè)計計算機算法,構(gòu)造了可遞推的羅馬{2}-控制函數(shù)。利用這些函數(shù)可以計算出Pn□Pm的羅馬{2}-控制數(shù)... 

【文章來源】：大連海事大學(xué)遼寧省 211工程院校

【文章頁數(shù)】：66 頁

【學(xué)位級別】：碩士

【部分圖文】：

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

?大連海事大學(xué)碩士學(xué)位論文???０?１?０??Ｈ??１?０?１??／］?０?１?０??／２?０?０?１??ｈ?２?０?０??／ｉ?０?０?１??Ｒ??／．－＞?０?１?０??ｋ?１?０?０??ｈ?〇?０?２??／Ｋ?１?０?〇??ｈ?０?１?０??／２?〇?０?１??／；Ｊ?２?０?０??Ｔ??／１?０?０?１??０?１?０??ｉ?ｎ?ｌ??／ｍ，３??圖４．２?／＾ＱＰ；對應(yīng)的羅馬｛以－控制數(shù)．／；ｆＵ??Ｆｉｇ．?４．２?ｃｏｒｒｅｓｐｏｎｄｉｎｇ?ｔｏ／ｉ??定理４．３當／ｊ２?７并且《?＝?ｌ（ｍｏｄ８）時，??證明：當《２７并且＂Ｅｌ（ｍｏｄ８）時，構(gòu)造的函數(shù)人３如下，其中－１，??〇＜７＜２．??２，／?ｅ?４（ｍｏｄ?８）八丨＝０，?１?＜／＜／？?—?２，??／?三?０（ｍｏｄ?８）八）＝２，?＼＜ｉ＜ｎ?—?２，??１，?ｉ?—?０ｉ?ｎ?—?ｌＡｊ?—?＼，??？?／?＝?１，ｗ?—?２?八戶２，??人＇３（Ｖ，ｖ）—?／?＝?ｌ，７（ｍｏｄ８）Ａ?ｙ?＝?０，?ｌ＜／＜？－ｌ，?（４３＞??三?２（ｍｏｄ４）八?／?＝?１，?１?＜?／?＜?／？?１，??／?＝?３，５（ｍｏｄ?８）?Ａ?ｊ?—?２，?１?＜／＜／？?—?１，??０，其他．??圖４．３是根據(jù)（４．３）式給出的心口／Ｖ匕的函數(shù)．／；７，３�？梢则炞C，這樣構(gòu)造的人３滿足??羅馬｛２卜控制函數(shù)的定義。實際上，對于任意的點ｖ＾．ｅＧ，有??或者｛Ｖ，．卜丨，ｖＷＪ｝或者｛ｖ，＿ｌ；而＋丨｝或者｛Ｖ，ｖ＿丨，??－１５?－??

?大連海事大學(xué)碩士學(xué)位論文???２，ｚ？三?４（ｍｏｄ８）八ｙ?＝?０，?ｌ＜ｉ＜ｎ?—?２，??ｚ．三?０（ｍｏｄ?８）八?ｙ．?＝?２，?１?＜／＜／？?—?２，??１，?ｉ?＝?〇Ａ?ｊ?＝?ｌ??ｉ?＝?ｌＡ?ｊ?＝?２，??乂，．３?（Ｖ，ｖ）?＝?ｉ?＝?ｎ－＼Ａｊ?＝?０，?（４．４）??ｚ．三?１，７（ｍｏｄ?８）八?ｙ?＝?０，?＼＜ｉ?＜ｎ?—?ｈ??ｆ?三?２（ｍｏｄ?４）八）＝１，?＼＜ｉ＜ｎ?—?＼，??ｚ？三?３，５（ｍｏｄ８）八）＝２，＼?＜ｉ?＜ｎ?—?ｈ??０，其他．??〇?１?ｏ??／／??１?０?１??／ｉ?０?１?０??ｌ２?０?０?１??／３?２?０?０??／４?０?０?１??Ｒ??ｋ?〇?１?０??／６?１?０?０??／７?０?０?２??Ｉｎ?１?０?０??／ｉ?０?１?０??ｌ２?０?０?１??／３?２?０?０??／４?０?０?１??Ｔ??ｋ?〇?１?〇??ｋ?１?〇?０??０?０?２??１?１?０??／ｌＳ．３??圖４．４?對應(yīng)的羅馬｛２卜控制數(shù)／ｊｙ??Ｆｉｇ．?４．４?／ＪｇＤＰ，?ｃｏｒｒｅｓｐｏｎｄｉｎｇ?ｔｏ／］８＞３??圖４．４是根據(jù)（４．４）式給出的匕口／＾上的函數(shù)／ｊ８，３�？梢则炞C，這樣構(gòu)造的人３滿足羅??馬｛２｝－控制函數(shù)的定義。實際上，對于任意的點ｖ，ｖｅＫ，有??者ｖ，＋１Ｊ或者｛Ｖ，—ｌ７．，ｖ，；＋ｌ｝或者｛ｖ，，?ｐｖ，—ｌｙ．｝或ｂ??－１７?－??

【參考文獻】：
期刊論文
[1]兩類圖的符號控制數(shù)[J]. 閆云娟,徐保根,馮大一.  華東交通大學(xué)學(xué)報. 2017(06)
[2]關(guān)于圖的兩類符號控制數(shù)的下界[J]. 尚華輝,苗連英.  數(shù)學(xué)的實踐與認識. 2017(21)
[3]網(wǎng)格圖的2-彩虹控制數(shù)[J]. 邵澤輝.  成都大學(xué)學(xué)報(自然科學(xué)版). 2013(01)
[4]圖的弱羅馬控制[J]. 陳越奮,楊劍.  信陽師范學(xué)院學(xué)報(自然科學(xué)版). 2012(01)
[5]圖的全符號控制數(shù)[J]. 呂新忠.  中國科學(xué)（A輯:數(shù)學(xué)）. 2007(05)

碩士論文
[1]圖的雙羅馬控制[D]. 陳優(yōu).鄭州大學(xué) 2018
[2]循環(huán)圖的兩類控制數(shù)研究[D]. 段偉.大連海事大學(xué) 2018
[3]若干圖類的全符號控制數(shù)的研究[D]. 曹惠萍.大連海事大學(xué) 2016
[4]圖的笛卡爾乘積的控制數(shù)與羅馬控制數(shù)[D]. 裴利丹.安徽大學(xué) 2014
[5]圖的弱羅馬控制[D]. 楊劍.河南大學(xué) 2007



本文編號：3591923