禁用子圖與圖的Hamilton問(wèn)題.pdf

1、【單位代碼10445r學(xué)號(hào)200213211分類(lèi)號(hào)0157厶蓀街缸大學(xué)r‘764工69碩士學(xué)位論文論文題目禁用子圖與圖的Hamilton問(wèn)題學(xué)科專(zhuān)業(yè)名稱應(yīng)用數(shù)學(xué)申請(qǐng)人姓名趙海霞指導(dǎo)教師論文提交時(shí)間一u_授心教月副年年二秀時(shí)江A已禁用子圖與圖的HamiIton問(wèn)題趙海霞(山東師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，濟(jì)南，山東，250014)摘要路和圈是圖的兩個(gè)基本結(jié)構(gòu)，是分析、刻畫(huà)圖的結(jié)構(gòu)的有力工具，有大量的實(shí)際問(wèn)題可蹦歸結(jié)為圖的路和圈的問(wèn)題圖論中三大著名

2、難題之一的Hamilton問(wèn)題本質(zhì)上也是圖的路和圈問(wèn)題圖的路和圈的研究一直是圖論中的熱點(diǎn)研究領(lǐng)域最近若干年，這方面的研究主要集中在圖的Hamilton性、泛圈、點(diǎn)泛圈、圈可擴(kuò)、Hamilton連通、泛連通、路可擴(kuò)、最長(zhǎng)路、最長(zhǎng)圈等性質(zhì)的研究上，而且已經(jīng)取得了長(zhǎng)足的發(fā)展由于直接研究任一圖類(lèi)Hamilton問(wèn)題往往比較困難，于是人們轉(zhuǎn)而研究不含有某些禁用子圖的圖類(lèi)，如無(wú)爪圖，幾乎無(wú)爪圖，擬無(wú)爪圖等1997年，ZdenEkRyjdSek在【4

3、1中提出了一種新的閉包概念并證明了無(wú)爪圖的Hamilton性是閉包下的穩(wěn)定性質(zhì)1999年，BdlaBollods，zdendkR“a洗^etal在【6]中提出了＆，閉包的概念，并證明了無(wú)爪圖的一些Hamilton問(wèn)題的穩(wěn)定性和不穩(wěn)定性至今，關(guān)于無(wú)爪圖的閉包和Hamilton問(wèn)題已經(jīng)有很多很好的結(jié)果本篇論文中定義了一種新的圖類(lèi)(Klp；g)一圖主要目的是把無(wú)爪圖的一些性質(zhì)結(jié)論推廣到(K：q)一圖本文中主要研究(K14；2)圖的一些Hami

4、lton問(wèn)題在第一章中，主要介紹了文章中所涉及的一些概念、術(shù)語(yǔ)符號(hào)和本文的研究背景以及已有的結(jié)果在第二章中，給出了(K切；q)一圖的簡(jiǎn)單卻十分重要的性質(zhì)及推論，即定理21(K1，p；g)一圖必為(Kl卅l；q41)圖推論22設(shè)t是不小于l的整數(shù)，則(KL，，；口)圖必為(Klpt；qt)一圖在第三章中，弓I入了＆一閉包的概念及相關(guān)結(jié)論對(duì)于無(wú)爪圖G，clk(G)是唯一確定的并且保持了圖的許多Hamilton性質(zhì)，成為研究無(wú)爪圖的強(qiáng)而有力的

5、工具令口是一個(gè)圖類(lèi)，如果對(duì)于口中任意的圖G，clk(G)∈口，則稱口是k一閉包下的穩(wěn)定圖類(lèi)令穢是k閉包下的穩(wěn)定圖類(lèi)，對(duì)于毋中任一圖G，若G有性質(zhì)∈當(dāng)且僅當(dāng)cl女(G)有性質(zhì)∈，則稱性質(zhì)∈為k閉包下的穩(wěn)定性質(zhì)對(duì)m一連通無(wú)爪圖，RyjdSek等人提出了閉包的概念并證明了以下的結(jié)論：定理31[4】若G為無(wú)爪圖，則(1)cf(G)是唯一確定的；(2)c(G)=c(cj(G))推論3214]若G為無(wú)爪圖，則G為Hamilton圖當(dāng)且僅當(dāng)cl(a)