廣義de Bruijn和Kautz有向圖的雙向控制和k元雙向控制數(shù).pdf

1、上海大學(xué)碩士學(xué)位論文廣義deBruijn和Kautz有向圖的雙向控制和k元雙向控制數(shù)姓名：董艷俠申請學(xué)位級別：碩士專業(yè)：系統(tǒng)分析與集成指導(dǎo)教師：單而芳20090401ABSTRACTIIWithinthepastnearfortyyears，concurrentwiththegrowthofcomputerscienceandcommunicationnetworks，graphtheoryhasseenexplosivegrowthT

2、hestudyofdominationingraphsisoneofthefastestgrowingareaswithinitAsanimportantresearchfieldingraphtheorydominationtheoryhasmanyandvariedapplicationsinrelatedfields，suchascomputerscience，communicationnetworks，combinatorial

3、optimization，codingtheorymonitorsystemandoperationsresearchAsalmostalldecisionproblemsofdominatingfuntionsareNPcompleteforgeneralgraphs，SOitisinterestingtoinvestigateboundsofthoseandcharacterizethestructureofgraphsWeallk

4、nowthatdominationinundirectedgr印hshasbeenstudiedextensivelyandmanygoodresultshavebeengivenInrecentyearstheconceptofdominationinundirectedgraphsisnaturallyextendedtodigraphs，especiallysomedigraphswhichhaveveryniceproperti

5、essuchasdeBruijnandKautz；generalizeddeBruijnandKautzdigraphsInthispaper，wemainlyinvestigatetheboundsontwindominationnumberandktupletwindominationnumberingeneralizeddeBruijnandKautzdigraphsThecorrespondingresultsarethefol

6、lowingthreeparts：Inthefirstpart(chapter3)，weinvestigatethetwindominationnumberingeneralizeddeBruijndigraphsGB(n，d)ForthedigraphsGB(n，d)，wefirstestablishsharpboundsonthetwindominationnumberSecondlywegivetheexactvaluesofth

7、etwindominationnumberforseveraltypesofGB(n，d)byconstructingminimumtwindominatingsetsinthedigraphsFinallywepresentsharpupperboundsforsomespecialgeneralizeddeBruSndigraphsInthesecondpart(chapter4)，weinvestigatethetwindomin

8、ationnumberingeneralizedKautzdigraphsGK(n，d)Forthesedigraphs，weobtaintheboundsonthetwindominationnumberandgiveasufficientconditionforthetwindominationnumberat—tainingthelowerboundWegivetheexactvaluesofthetwindominationnu

9、mbersbyconstructingminimumtwindominatingsetsforsomespecialgeneralizedKautzdigraphsInthethirdpart(chapter5)，weconsiderthektupletwindominationnumberingeneralizeddeBruijndigraphsGB(n，d)andgeneralizedKautzdigraphsGK(n，d)Fort