【摘要】：圖論作為離散數(shù)學(xué)的一個(gè)重要分支,綜合了群論、矩陣論、概率論、拓?fù)鋵W(xué)等其他學(xué)科的知識(shí),在化學(xué)、物理、天文、地理、生物、計(jì)算機(jī)科學(xué)等領(lǐng)域有著廣泛的應(yīng)用.圖的反魔幻標(biāo)號(hào)問(wèn)題起源于1990年Hartsfield和Ringel在文獻(xiàn)[1]中提出的兩個(gè)猜想:1、所有連通圖除K2外都是反魔幻的;2、所有樹(shù)除K2外都是反魔幻的.圖G =(V,E)的邊標(biāo)號(hào)是圖的邊集到整數(shù)集的一個(gè)雙射,即φ:E→{1,2,…,|E|}.對(duì)G的任意頂點(diǎn)u,其標(biāo)號(hào)和定義為fφ(u)=∑e∈E(u)φ(e),這里E(u)是指與頂點(diǎn)u關(guān)聯(lián)的所有邊的集合.一個(gè)圖被稱(chēng)為是反魔幻的,如果存在圖G的一個(gè)標(biāo)號(hào)φ,使得V(G)中任意兩個(gè)不同的頂點(diǎn)u,v有不同的標(biāo)號(hào)和,即fφ(u)≠fφ(v).以上兩個(gè)猜想一經(jīng)提出,立即引起了國(guó)內(nèi)外眾多學(xué)者的重視并得到了許多結(jié)果.許多特殊的圖已經(jīng)被證實(shí)其反魔幻性,例如,簡(jiǎn)單的圖類(lèi)有路、圈、輪圖、星圖、雙星圖、扇圖、聯(lián)圖、完全圖、三正則圖等,復(fù)雜的圖類(lèi)有稠密圖、正則圖、奇正則圖、正則二部圖、樹(shù)、網(wǎng)格圖和棱柱圖、笛卡爾乘積圖、平面圖、推廣的錐形圖、有向圖等.這一猜想目前還沒(méi)有得到完全解決,仍然具有高度的開(kāi)放性.圖的反魔幻標(biāo)號(hào)在計(jì)算機(jī)網(wǎng)絡(luò)理論中得到了很好的應(yīng)用,例如,網(wǎng)絡(luò)需求負(fù)載不平衡問(wèn)題:當(dāng)我們用不同容量的路由器建立網(wǎng)絡(luò)時(shí),就可以考慮用邊的反魔幻標(biāo)號(hào)表示路由器之間的寬帶容量.本文主要研究?jī)煞N圖——字典乘積圖、融合圖的反魔幻標(biāo)號(hào)問(wèn)題.利用矩陣對(duì)圖的完全二部子圖進(jìn)行標(biāo)號(hào),并采用調(diào)換的方法解決標(biāo)號(hào)和沖突(即兩個(gè)不同的頂點(diǎn)有相同的標(biāo)號(hào)和)的問(wèn)題,最后得出兩條路的字典乘積圖、兩個(gè)完全圖的融合圖是反魔幻圖的結(jié)論.本文所得到的結(jié)果是對(duì)圖的反魔幻性研究領(lǐng)域的一個(gè)補(bǔ)充,同時(shí)改進(jìn)、推廣和統(tǒng)一了許多學(xué)者的最新研究成果.全文一共分為四個(gè)部分:第一部分是緒論.這里主要介紹了圖論的歷史、選題的背景、研究現(xiàn)狀以及圖論中的一些基本概念.第二部分研究了兩條路的字典乘積圖的反魔幻性.首先介紹了字典乘積圖的概念以及兩條路的字典乘積圖的標(biāo)號(hào)技巧,其次展示了在標(biāo)號(hào)過(guò)程中得到的六個(gè)聲明,然后提出解決頂點(diǎn)標(biāo)號(hào)和沖突的方法——調(diào)換,最后分類(lèi)證明了兩條路的字典乘積圖是反魔幻的.第三部分研究了兩個(gè)完全圖的融合圖的反魔幻性.首先是介紹融合圖的概念,然后用構(gòu)造出來(lái)的主對(duì)角線(xiàn)為0的特殊分塊矩陣對(duì)其邊進(jìn)行標(biāo)號(hào),最后證明兩個(gè)完全圖的融合圖是反魔幻的.第四部分是總結(jié)與展望,總結(jié)本文得出的兩個(gè)結(jié)論——兩條路的字典乘積圖、兩個(gè)完全圖的融合圖是反魔幻的,同時(shí)展望了在以后的工作中將要研究的問(wèn)題——探究Spider圖、Halin圖、雙正則二部圖、雙正則圖的反魔幻性以及圖的反魔幻性在實(shí)際中的應(yīng)用.
【學(xué)位授予單位】：天津工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 姚明;姚兵;趙振學(xué);;關(guān)于太陽(yáng)圖魔幻標(biāo)號(hào)的若干結(jié)果[J];甘肅科學(xué)學(xué)報(bào);2015年04期

2 姚明;姚兵;謝建民;;關(guān)于圖k-魔幻標(biāo)號(hào)的若干結(jié)果[J];甘肅科學(xué)學(xué)報(bào);2010年01期

3 姚明;姚兵;趙振學(xué);;一類(lèi)串圖的1-維魔幻標(biāo)號(hào)[J];西安石油大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年03期

4 姚明;任太明;姚兵;;關(guān)于圖魔幻標(biāo)號(hào)的運(yùn)算關(guān)系[J];甘肅科學(xué)學(xué)報(bào);2017年01期

5 姚明;趙振學(xué);姚兵;;一類(lèi)龍圖的廣義邊魔幻標(biāo)號(hào)[J];甘肅科學(xué)學(xué)報(bào);2016年03期

6 趙振學(xué);姚明;;圖的魔幻變換[J];蘭州石化職業(yè)技術(shù)學(xué)院學(xué)報(bào);2017年03期

7 蔣玲芳;姚兵;謝建民;;廣義d_m-齊對(duì)蝦樹(shù)的(λ,μ)-魔幻標(biāo)號(hào)[J];甘肅高師學(xué)報(bào);2010年05期

8 梁志和;;關(guān)于圖的G-超幻覆蓋[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2014年05期

9 趙振學(xué);姚明;;一類(lèi)二部圖的魔幻標(biāo)號(hào)[J];蘭州石化職業(yè)技術(shù)學(xué)院學(xué)報(bào);2017年01期

10 姚明;趙振學(xué);;V_k~m-圖的魔幻標(biāo)號(hào)[J];甘肅科學(xué)學(xué)報(bào);2014年01期

相關(guān)碩士學(xué)位論文 前4條

1 馬文慧;圖的反魔幻性猜想的研究[D];天津工業(yè)大學(xué);2018年

2 宋貝貝;關(guān)于兩類(lèi)圖的H-超幻覆蓋[D];河北師范大學(xué);2012年

3 張保生;廣義Petersen圖的（a，，d）-反邊幻標(biāo)號(hào)和圖P_2□P_n的廣播標(biāo)號(hào)[D];大連理工大學(xué);2009年

4 李華龍;平面圖的鄰和可區(qū)別全染色[D];山東大學(xué);2014年

本文編號(hào)：2607452