發(fā)布時間：2020-07-09 12:59

【摘要】：圖G的厚度θ(G)是指圖G可分解為平面生成子圖的最小數(shù).圖的厚度是度量圖的可平面性的重要指標(biāo)之一,它在超大規(guī)模集成電路和網(wǎng)絡(luò)設(shè)計中有著重要的應(yīng)用.然而,由于圖的厚度問題已經(jīng)被證明是NP 難問題,所以目前已知厚度的圖類很少.本論文主要研究了一些完全多部圖,笛卡爾積圖,聯(lián)圖和直積圖的厚度以及一類完全三部圖的4-圍長厚度.論文第一章介紹了厚度的相關(guān)概念、研究背景以及本文研究的主要內(nèi)容.第二章在完全二部圖K_(n,n)的平面分解的基礎(chǔ)上,構(gòu)造了完全三部圖K_(1,n,n)和K_(2,n,n)的平面分解,進而確定了完全三部圖K_(1,n,n)和K_(2,n,n)的厚度.進一步地,基于完全三部圖K_(2,n,n)的平面分解,構(gòu)造了完全四部圖K_(1,1,n,n)的平面分解,并得到了完全四部圖K_(1,1,n,n)的厚度.圖G和H的笛卡爾積圖記為G H,其中頂點集V(G H)=V(G)×V(H),邊集E(G H)={(g,h)(g~′,h~′)|gg~′∈E(G),h=h~′或hh~′∈E(H),g=g~′}.第三章研究了一些笛卡爾積圖的厚度.對于大部分n值,得到了完全圖K_n與圈C_m(m≥3)以及完全二部圖K_(n,n)與圈C_m(m≥3)的笛卡爾積圖的厚度,而且通過構(gòu)造完全二部圖K_(n,m)與路徑P_k(k≥2)的笛卡爾積圖的平面分解,確定了其厚度的上界和下界以及部分完全二部圖K_(n,m)與路徑P_2的笛卡爾積圖的厚度的精確值,隨后得到了完全二部圖K_(n,n)與路徑P_k(k≥2)的笛卡爾積圖的厚度.圖G和H的聯(lián)圖記為G+H,其中頂點集V(G+H)=V(G)∪V(H),邊集E(G+H)={(v_i,u_j)|v_i∈E(G),u_j∈E(H)}∪E(G)∪E(H).第四章研究了圈與圈、路徑與路徑以及圈與路徑的聯(lián)圖的厚度,進而研究了任意圖與圈的聯(lián)圖的厚度.圖G和H的直積圖記為G×H,其中頂點集為V(G×H)=V(G)×V(H),邊集E(G×H)={(g,h)(g~′,h~′)|gg~′∈E(G),hh~′∈E(H)}.第五章主要研究了完全圖與路徑的直積圖的厚度.圖G的g-圍長厚度θ(g,G)是指圖G分解為平面子圖的最小數(shù),其中,每個平面子圖的圍長至少是g.它是厚度的推廣,3-圍長厚度θ(3,G)就是圖G的厚度θ(G).在第六章,我們得到了所有完全三部圖K_(n,n,n)的4-圍長厚度,并確定了完全圖K_(10)的4-圍長厚度.
【學(xué)位授予單位】：天津大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【相似文獻】

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

1 郭美美;;從廣義笛卡爾積解關(guān)系代數(shù)除法[J];現(xiàn)代計算機(專業(yè)版);2016年17期

2 斯欽;阿勇嘎;;圖的笛卡爾積圖的結(jié)構(gòu)及其完美性(英文)[J];寶雞文理學(xué)院學(xué)報(自然科學(xué)版);2011年04期

3 黃瓊湘;廣義笛卡爾積圖的連通度[J];新疆大學(xué)學(xué)報(自然科學(xué)版);1991年02期

4 尤玲;葉永升;;圈與路笛卡爾積的邊連通測地數(shù)[J];淮北師范大學(xué)學(xué)報(自然科學(xué)版);2018年01期

5 孫秀玲;;笛卡爾積在配件替互換關(guān)系中的研究與應(yīng)用[J];科技創(chuàng)新導(dǎo)報;2010年13期

6 董新芳;田雙亮;董新菊;;路的三類積圖的無圈全染色[J];蘭州文理學(xué)院學(xué)報(自然科學(xué)版);2017年05期

7 王倩;田雙亮;;圈與偶圖的笛卡爾積圖的鄰點可區(qū)別全染色[J];魯東大學(xué)學(xué)報(自然科學(xué)版);2011年01期

8 張莉茜;黃元秋;;G_7×S_n的交叉數(shù)[J];湖南文理學(xué)院學(xué)報(自然科學(xué)版);2011年04期

9 呂勝祥;黃元秋;;幾個六階圖與路的笛卡爾積的交叉數(shù)(英文)[J];湖南文理學(xué)院學(xué)報(自然科學(xué)版);2007年02期

10 馬慶媛;田雙亮;;若干笛卡爾積圖的星全染色[J];云南民族大學(xué)學(xué)報(自然科學(xué)版);2011年03期

相關(guān)會議論文 前2條

1 蔡慶生;李凡長;徐金輝;;Fuzzy數(shù)學(xué)在知識量化形式化推理中的幾點應(yīng)用[A];復(fù)雜巨系統(tǒng)理論·方法·應(yīng)用——中國系統(tǒng)工程學(xué)會第八屆學(xué)術(shù)年會論文集[C];1994年

2 張振東;耿昕;杜朝暉;;模糊PID控制[A];1995年中國智能自動化學(xué)術(shù)會議暨智能自動化專業(yè)委員會成立大會論文集（上冊）[C];1995年

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

1 唐玲;關(guān)于一些特殊圖類的交叉數(shù)研究[D];湖南師范大學(xué);2007年

2 周志東;圖的交叉數(shù)有關(guān)問題研究[D];湖南師范大學(xué);2013年

3 袁梓瀚;關(guān)于循環(huán)圖及一些特殊圖與路、星、樹和圈的笛卡爾積的交叉數(shù)研究[D];湖南師范大學(xué);2009年

4 王晶;若干圖類交叉數(shù)的研究[D];湖南師范大學(xué);2009年

5 郭婷;圖嵌入分布及相關(guān)性質(zhì)[D];湖南師范大學(xué);2013年

6 陳衛(wèi)東;數(shù)據(jù)質(zhì)量模型及關(guān)系代數(shù)運算下質(zhì)量傳遞理論與方法研究[D];國防科學(xué)技術(shù)大學(xué);2007年

7 張國珍;圖的容錯參數(shù)[D];山西大學(xué);2014年

8 葛鐵錚;圖像搜索中的緊湊表達(dá)[D];中國科學(xué)技術(shù)大學(xué);2014年

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

1 郭霞;一些多部圖及笛卡爾積圖的厚度[D];天津大學(xué);2018年

2 趙曉曉;關(guān)于兩類特殊圖的交叉數(shù)的下界[D];湖南師范大學(xué);2018年

3 李慧靜;幾類圖的笛卡爾積的拓?fù)渲笜?biāo)[D];天津大學(xué);2017年

4 古媛媛;聯(lián)圖與笛卡爾積圖類的交叉數(shù)研究[D];湖南師范大學(xué);2017年

5 丁奇;n條路的笛卡爾積圖的匹配排除和條件匹配排除[D];蘭州大學(xué);2014年

6 趙琳;關(guān)于圖的交叉數(shù)[D];北京交通大學(xué);2007年

7 呂勝祥;五階圖與星圖的笛卡爾積的交叉數(shù)[D];湖南師范大學(xué);2007年

8 張玉紅;一些圖的點鄰點可區(qū)別全染色[D];蘭州交通大學(xué);2010年

9 劉永平;一些特殊圖類的笛卡爾積和倍圖的鄰點可區(qū)別的全染色問題[D];蘭州大學(xué);2006年

10 戴慶華;關(guān)于圖的交叉數(shù)研究[D];湖南師范大學(xué);2009年

本文編號：2747492