【摘要】：超歐拉問(wèn)題是圖論研究中的一個(gè)非常經(jīng)典的問(wèn)題,許多實(shí)際問(wèn)題以及理論上的知名問(wèn)題都可以轉(zhuǎn)化為超歐拉圖來(lái)解決.一個(gè)圖是超歐拉圖,是指它包含一個(gè)生成歐拉子圖.相比于歐拉圖已經(jīng)有了較為簡(jiǎn)單的特征刻畫(huà),超歐拉圖的判定問(wèn)題則是NP-完全的.在圖論中,由一個(gè)圖或者兩個(gè)圖出發(fā)去構(gòu)造新的圖,并研究該圖的性質(zhì),是一個(gè)很有趣的研究領(lǐng)域.本文主要研究圖G的廣義棱柱α(G),補(bǔ)棱柱GG以及有向圖D對(duì)H的α-廣義棱柱中的(有向)超歐拉問(wèn)題.全文共分為四章.第一章概述與超歐拉問(wèn)題密切相關(guān)的Catlin的約化方法,與本論文相關(guān)的研究背景,以及文中常用的定義、符號(hào)和術(shù)語(yǔ).第二章首先介紹李霄民等人在研究廣義棱柱的超歐拉性質(zhì)方面的研究結(jié)果,然后我們刻畫(huà)了完全二部圖、長(zhǎng)度不超過(guò)6的圈,以及樹(shù)的廣義棱柱是超歐拉圖的充要條件.Haynes等人引入了兩個(gè)圖的補(bǔ)直積作為笛卡爾積的推廣.補(bǔ)棱柱是補(bǔ)直積的一個(gè)有趣特例.第三章研究完全二部圖、路、圈的補(bǔ)棱柱是超歐拉圖的充要條件.最后研究?jī)蓷l有向路的字典式積的有向可跡性.作為廣義棱柱概念的推廣,我們?cè)诘谒恼率紫冉o出兩個(gè)有向圖D對(duì)H的α-廣義棱柱αH(D)的概念,然后研究αH(D)的超歐拉性質(zhì).
【學(xué)位授予單位】：山西大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 桂起權(quán);;邏輯圓論(一種由歐拉圖導(dǎo)出的三段論系統(tǒng))[J];武漢大學(xué)學(xué)報(bào)(哲學(xué)社會(huì)科學(xué)版);1981年02期

2 安明強(qiáng);熊黎明;;超歐拉圖、可折疊圖及匹配[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2016年06期

3 李霄民;;判定超歐拉圖的一個(gè)新方法[J];西南大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

4 李登信,王斌,李宵民;關(guān)于判定超歐拉圖的收縮法[J];重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年01期

5 路浩;;關(guān)于賦權(quán)歐拉圖的均勻初級(jí)圈覆蓋[J];西安交通大學(xué)學(xué)報(bào);1988年06期

6 潘洪;劉楓;;推廣循環(huán)序列的計(jì)算機(jī)解[J];上海建材學(xué)院學(xué)報(bào);1989年01期

7 張建州;一類(lèi)歐拉圖的全著色[J];電子科技大學(xué)學(xué)報(bào);1989年03期

8 李曉璞;劉娟;;關(guān)于l-路和圖的超歐拉性[J];西華師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2018年03期

9 李霄民;李登信;;超歐拉圖判定方法的一個(gè)注記[J];湖北大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年03期

10 PaulA．Catlin,李相文;最小次數(shù)至少為4的超歐拉圖(英文)[J];數(shù)學(xué)進(jìn)展;1999年01期

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

1 李赤松;訪問(wèn)控制中授權(quán)一致性問(wèn)題的研究[D];華中科技大學(xué);2012年

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

1 王劉巖;廣義棱柱和補(bǔ)棱柱中的超歐拉圖[D];山西大學(xué);2018年

2 余三平;邊連通度與超歐拉圖的研究[D];中北大學(xué);2010年

3 熊鳴;3-邊連通基本5-邊連通圖的超歐拉圖[D];華中師范大學(xué);2012年

4 司沛;超歐拉圖及相關(guān)問(wèn)題性質(zhì)研究[D];重慶大學(xué);2008年

5 陳慧敏;在C_k(l，，m)中的k-超歐拉圖[D];華中師范大學(xué);2015年

6 王斌;超歐拉圖的判定及Catlin-猜想的研究[D];西南師范大學(xué);2003年

7 李良辰;超歐拉圖和帶約束條件的頻率分配的近似算法[D];華中師范大學(xué);2009年

8 趙紅艷;歐拉圖與矩陣環(huán)的多項(xiàng)式恒等式[D];湖北大學(xué);2013年

9 薄祥智;中間P_2-圖的邊連通性[D];新疆大學(xué);2010年

10 關(guān)曉溪;從邏輯圖到圖示邏輯[D];華東師范大學(xué);2009年

本文編號(hào)：2644048