Pn×Cm的符號(hào)圈控制數(shù)及具有給定2-彩虹控制數(shù)的樹(shù)的研究的任務(wù)書

Pn×Cm的符號(hào)圈控制數(shù)及具有給定2-彩虹控制數(shù)的樹(shù)的研究的任務(wù)書任務(wù)書一、任務(wù)背景符號(hào)圈是圖論中重要的概念之一，是指在平面圖上用封閉的圓圈把某些互不相交的邊所構(gòu)成的每一段路徑包住的一種方法。符號(hào)圈控制數(shù)是指把整個(gè)圖中的邊都用符號(hào)圈圈起來(lái)所需的最小符號(hào)圈數(shù)量，是衡量一個(gè)圖中普遍性的指標(biāo)之一。彩虹連接是指一個(gè)無(wú)向圖中，從一個(gè)點(diǎn)到另一個(gè)點(diǎn)經(jīng)過(guò)的路徑的顏色各不相同，則該路徑為彩虹連接。而具有給定2-彩虹控制數(shù)的樹(shù)是指，在給定的樹(shù)中添加權(quán)值后，從根節(jié)點(diǎn)出發(fā)并且在抵達(dá)葉子節(jié)點(diǎn)時(shí)滿足2-彩虹控制數(shù)的樹(shù)。本次研究的任務(wù)是對(duì)于符號(hào)圈控制數(shù)及具有給定2-彩虹控制數(shù)的樹(shù)進(jìn)行研究，探究其在實(shí)際應(yīng)用中的意義及應(yīng)用方法。二、研究?jī)?nèi)容1.符號(hào)圈控制數(shù)的研究（1）探究符號(hào)圈控制數(shù)的定義及性質(zhì)；（2）調(diào)研符號(hào)圈控制數(shù)在實(shí)際應(yīng)用中的意義，如網(wǎng)絡(luò)通信、電路設(shè)計(jì)等；（3）設(shè)計(jì)符號(hào)圈控制數(shù)的計(jì)算方法，并比較不同算法的復(fù)雜度及準(zhǔn)確度；（4）對(duì)比不同類型的圖的符號(hào)圈控制數(shù)，如樹(shù)、平面圖、一般圖等，探究其差異性及原因。2.具有給定2-彩虹控制數(shù)的樹(shù)的研究（1）研究2-彩虹連接的定義及性質(zhì)；（2）調(diào)查具有給定2-彩虹控制數(shù)的樹(shù)在實(shí)際應(yīng)用中的應(yīng)用場(chǎng)景；（3）設(shè)計(jì)具有給定2-彩虹控制數(shù)的樹(shù)的生成算法；（4）對(duì)比不同類型的樹(shù)及不同權(quán)值下的2-彩虹控制數(shù)，分析其特點(diǎn)及優(yōu)缺點(diǎn)。三、研究目的1.探究符號(hào)圈控制數(shù)在實(shí)際應(yīng)用中的意義及應(yīng)用方法，為相關(guān)領(lǐng)域提供參考依據(jù)。2.研究具有給定2-彩虹控制數(shù)的樹(shù)的生成算法，以拓展該領(lǐng)域的研究廣度。3.通過(guò)對(duì)兩個(gè)研究領(lǐng)域的分析與比較，加深對(duì)于圖論領(lǐng)域的理解與掌握。四、研究方法1.文獻(xiàn)調(diào)研法：通過(guò)閱讀相關(guān)文獻(xiàn)，了解符號(hào)圈控制數(shù)及具有給定2-彩虹控制數(shù)的樹(shù)的定義、性質(zhì)、應(yīng)用及研究進(jìn)展，以確定研究?jī)?nèi)容及方向。2.算法設(shè)計(jì)法：設(shè)計(jì)符號(hào)圈控制數(shù)的計(jì)算方法以及具有給定2-彩虹控制數(shù)的樹(shù)的生成算法。3.數(shù)據(jù)分析法：利用圖論中相關(guān)的算法和數(shù)據(jù)結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行處理，以掌握相關(guān)數(shù)據(jù)的特點(diǎn)及變化規(guī)律。五、參考文獻(xiàn)[1]GaoWeiying,WuBaoguo.Onrainbowconnectionnumberofgraphs.DiscreteApplMath,2011,159(18):2161-2167.[2]郝金明,張鳳賢.符號(hào)圈控制數(shù)及其計(jì)算[J].計(jì)算機(jī)工程與科學(xué),2008,30(11):123-126.[3]CharalamposTsourakakis,PengZhang.Rainbowconnectivityandgraphseparability[C]//Proceedingsofthe24thannualACM-SIAMsymposiumonDiscretealgorithms.SIAM,2013:1537-1546.[4]SurongYou.Ontherainbowconnectionnumberofgraphs[C]//InternationalConferenceonCombinatorialOptimizationandApplications.Springer,Berlin,Heidelberg,2011:45-54.[5]郭文秀,費(fèi)志勇.具有2-彩虹控制數(shù)的樹(shù)的構(gòu)造[J].山西大學(xué)學(xué)報(bào),2017,40(6):