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

【相似文獻】

相關期刊論文 前10條

1 姚明;姚兵;趙振學;;關于太陽圖魔幻標號的若干結果[J];甘肅科學學報;2015年04期

2 姚明;姚兵;謝建民;;關于圖k-魔幻標號的若干結果[J];甘肅科學學報;2010年01期

3 姚明;姚兵;趙振學;;一類串圖的1-維魔幻標號[J];西安石油大學學報(自然科學版);2016年03期

4 姚明;任太明;姚兵;;關于圖魔幻標號的運算關系[J];甘肅科學學報;2017年01期

5 姚明;趙振學;姚兵;;一類龍圖的廣義邊魔幻標號[J];甘肅科學學報;2016年03期

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

7 蔣玲芳;姚兵;謝建民;;廣義d_m-齊對蝦樹的(λ,μ)-魔幻標號[J];甘肅高師學報;2010年05期

8 梁志和;;關于圖的G-超幻覆蓋[J];應用數(shù)學學報;2014年05期

9 趙振學;姚明;;一類二部圖的魔幻標號[J];蘭州石化職業(yè)技術學院學報;2017年01期

10 姚明;趙振學;;V_k~m-圖的魔幻標號[J];甘肅科學學報;2014年01期

相關碩士學位論文 前4條

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

2 宋貝貝;關于兩類圖的H-超幻覆蓋[D];河北師范大學;2012年

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

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

本文編號：2607452