發(fā)布時(shí)間：2022-01-16 04:19

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

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

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

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

【部分圖文】：

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

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

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

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

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



本文編號(hào)：3591923