幾類圖（排斥，排斥整，下整）和數(shù)

《幾類圖（排斥，排斥整，下整）和數(shù)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、獨(dú)創(chuàng)聲明Y1012480本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果，也不包含為獲得(注：如沒(méi)有其他需要特別聲明的，本欄可空)或其他教育機(jī)構(gòu)的學(xué)位或證書(shū)使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示謝意。學(xué)位論文作者簽名：南秀壹導(dǎo)師簽字：學(xué)位論文版權(quán)使用授權(quán)書(shū)南黝狻一本學(xué)位論文作者完全了解堂撞有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)

2、印件和磁盤，允許論文被查閱和借閱。本人授權(quán)』越可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。(保密的學(xué)位論文在解密后適用本授權(quán)書(shū))學(xué)位論文作者簽名：譚攜蓮導(dǎo)師簽字高蚓釓簽字日期：200年月日簽字日期：200‘年f『月糾伯山東師范人學(xué)碩士學(xué)位論文幾類圖的(排斥，排斥整，下整)和數(shù)高秀蓮(山東師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，濟(jì)南，山東，250014)中文摘要本文僅考慮有限無(wú)向簡(jiǎn)單圖，所用圖論基本術(shù)語(yǔ)與符號(hào)遵循文獻(xiàn)‘”．1990年Harary[21提出和圖的概念．1994年H

3、arary_『31提出整和圖的概念．令N(z)表示正整數(shù)(整數(shù))集，N(z)的非空有限子集s的和(整和)圖G十(s)是圖(s，E)，其中uvEE當(dāng)且僅當(dāng)u+vES．一個(gè)圖G稱為和(整和)圖，若它同構(gòu)于某個(gè)ScN(Z)的和(整和)圖．此時(shí)我們說(shuō)S給出了G的一個(gè)和(整和)標(biāo)號(hào)，并且將頂點(diǎn)與其標(biāo)號(hào)不加區(qū)分．G的和數(shù)(整和數(shù))O-(G)(f(G))是使得GUnKl是和圖(整和圖)的非負(fù)整數(shù)n的最小值．2003年Miller[41等人提出排斥圖的概念．圖GUnKl的(整)和標(biāo)號(hào)s稱為排斥的(exclusive)，若對(duì)每條邊uvEE

4、(G)，u+v∈s＼V(G)．圖G的排斥和(整和)數(shù)占(G)(f’(G))是使得GUnKl有排斥和(整和)標(biāo)號(hào)的非負(fù)整數(shù)n的最小值．2004年李敏‘51提出下整和圖的概念．令Q+表示正有理數(shù)集．O+的非空有限子集s的下整和圖G十(S)是圖(s，E)，其中UVEE當(dāng)且僅當(dāng)bu+VJES．一個(gè)圖G稱為下整和圖，若它同構(gòu)于某個(gè)ScO+的下整和圖．我們說(shuō)S給出G的一個(gè)下整和標(biāo)號(hào)，并且頂點(diǎn)與標(biāo)號(hào)不加區(qū)分．下整和數(shù)?！?G)是使得GUnKl是下整和圖的非負(fù)整數(shù)U的最小值．圖GUnKl的下整和標(biāo)號(hào)s稱為排斥的(exclusive)，若

5、對(duì)每條邊uvEE(G)當(dāng)且僅當(dāng)bu+vjeS＼V(G)．圖G的排斥下整和數(shù)占7(G)是使得GUnKi有排斥下整和標(biāo)號(hào)的非負(fù)整數(shù)n的最小值．從實(shí)用的觀點(diǎn)來(lái)看，各種和圖標(biāo)號(hào)都可被計(jì)算機(jī)用作圖的壓縮表示．當(dāng)利用它們來(lái)工作時(shí)，不僅可以節(jié)省內(nèi)存，還可以加快某些圖算法的運(yùn)算速度．在本文的第一章中，我們主要介紹了一些文章中所涉及的概念，術(shù)語(yǔ)，符號(hào)；第二章介紹了棱柱EIl(n≥3)、殘棱柱E：(il≥3)、殘皇冠C：。Kl(n≥3)、梯子山東帥范大學(xué)碩十學(xué)位論文L。(n≥2)、梯子細(xì)分圖L：(n≥2)的概念，并給出了1邑們的排斥(整，下

6、整)和數(shù)：第三章給出了三毛蟲(chóng)樹(shù)，星毛蟲(chóng)樹(shù)，廣義雙星，廣義毛蟲(chóng)的概念，并證明了這幾類特殊的樹(shù)是整和圖．我們主要得到如下結(jié)果．定理2．1設(shè)n為大于等于3的自然數(shù)，則s(E)25．定理2．2設(shè)n為大于等于3的自然數(shù)，則f7(E：)=4．定理2．3設(shè)n為大于等于3的自然數(shù)，則s(qoKl)23．定理2．4Ln(n≥2)是下整和圖．定理2．5設(shè)n為大于1的自然數(shù)，則占’(匕)=1．定理2．6設(shè)n為大于1的自然數(shù)，則s(‘)23．定理2．7設(shè)n為大于1的自然數(shù)，則￡7(t)=2．定理3．1三毛蟲(chóng)樹(shù)是整和圖．定理3．2偶星毛蟲(chóng)樹(shù)是整和

7、圖．定理3．3廣義雙星是整和圖．定理3．4廣義毛蟲(chóng)是整和圖．關(guān)鍵詞：(排斥，下整，整)和圖：(排斥，下整，整)和數(shù)：(排斥，下整，整)和標(biāo)號(hào)；(殘)棱柱；殘皇冠；梯子；整和樹(shù)．分類號(hào)：0157．5山東師范大學(xué)碩士學(xué)位論文The(exclusive，exclusiveintegral，lowerintegral)sumnumbersofseveralkindsofgraphXiulianGaoShandongNormalUniversity,Jinan，Shandong，250014People’sRepublicofCh

8、inaABSTRACTAllgraphconsideredinthispaperarefinite，simpleandundirected．Wefollowingeneralthegraph-theoreticnotationandterminologyof[1】Hararyt21presentedtheconcep