本文主要研究了莫比烏斯網(wǎng)格圖P_m×C_n^′（m=2,3,4,6,7）的消圈數(shù)問題以及循環(huán)圖C（n,2,3）的消圈數(shù),最大不可分獨(dú)立集問題.第一章首先介紹了圖論的起源與發(fā)展,圖的消圈數(shù)以及最大不可分獨(dú)立集問題的研究現(xiàn)狀和部分重要成果.接著介紹了文中需要用到的一些基本定義定理以及本文的研究成果.第二章考慮了影響莫比烏斯網(wǎng)格圖P_m×C_n^′（m=2,3,4,6,7）消圈數(shù)的三個(gè)因素:度數(shù),獨(dú)立性,余圖的連通分支數(shù),得到消圈數(shù)的下界.之后根據(jù)圖的結(jié)構(gòu)特征采用分析法,列舉法提高下界值并在圖中找到對(duì)應(yīng)的消圈點(diǎn)從而證明了取等條件成立.第三章第一節(jié)考慮了影響循環(huán)圖C（n,2,3）消圈數(shù)的兩個(gè)因素:獨(dú)立性,余圖的連通分支數(shù),得到消圈數(shù)下界.之后根據(jù)消圈點(diǎn)的獨(dú)立性和圈的存在性,采用反證法提高下界值并在圖中找到對(duì)應(yīng)的消圈點(diǎn)從而證明了取等條件成立.第二節(jié)在前一節(jié)已證明循環(huán)圖C（n,2,3）消圈數(shù)的情況下,結(jié)合四正則圖獨(dú)立集的上界,用列舉法證明了當(dāng)n=6k+1,6k+3,6k+4,6k... 

【文章來源】：華東師范大學(xué)上海市 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：58 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

P4×C′nS,n為奇數(shù)

華東師范大學(xué)碩士學(xué)位論文當(dāng)n為奇數(shù)時(shí),取S={v1,1,v2,1,v2,3,v2,5,v2,7...v2,n,v3,2,v3,4,v3,6...v3,n1}.此時(shí)|S|=n+1且GS無圈,如下圖2.26所示.當(dāng)n為偶數(shù)時(shí),取S={v4,1,v2,1,v2,3,v2,5,v2,7...v2,n1,v3,2,v3,4,v3,6...v3,n}.此時(shí)|S|=n+1且GS無圈,如下圖2.27所示.圖2.26P4×C′nS,n為奇數(shù)圖2.27P4×C′nS,n為偶數(shù)從而,(P4×C′n)=n+1.□2.4P6×C′n的消圈數(shù)定理2.9(P6×C′n)=5n+23,n=3k,3k+1,3k+2(k為奇數(shù)),k≥1;5n+23+1,n=3k+2(k為偶數(shù)),k≥2.證明由推論2.6知：(P6×C′n)≥6nn+23=5n+23.當(dāng)n=3k(k≥1),5n+23=5×3k+23=5k+1.當(dāng)n=3k+1(k≥1),5n+23=5×(3k+1)+23=5k+3.當(dāng)n=3k+2(k≥1),5n+23=5×(3k+2)+23=5k+4.情形1:當(dāng)n=3k(k≥1),(P6×C′3k)≥5k+1.1.當(dāng)k為奇數(shù)時(shí),取S={v6,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...v2,3k2,v3,3k1,v5,3k1,v2,3k,v4,3k},其中0≤m<k321.此時(shí)|S|=5k+1且余圖P6×C′3kS無圈,如下圖2.28所示.2.當(dāng)k為偶數(shù)時(shí),取S={v6,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...},17

華東師范大學(xué)碩士學(xué)位論文其中0≤m<k22.此時(shí)|S|=5k+1且余圖P6×C′3kS無圈,如下圖2.29所示.圖2.28P6×C′3kS,k為奇數(shù)圖2.29P6×C′3kS,k為偶數(shù)從而,(P6×C′3k)=5k+1.下面舉例說明.例2.1(P6×C′9)=16.(P6×C′6)=11.在圖P6×C′9中取消圈集：S={v6,1,v2,1,v3,2,v5,2,v2,3,v4,3,v5,4,v2,5,v4,5,v3,6,v5,6,v2,7,v3,8,v5,8,v2,9,v4,9}.則|S|=16且余圖P6×C′9S無圈,如下圖2.30所示.在圖P6×C′6中取消圈集：S={v6,1,v2,1,v3,2,v5,2,v2,3,v4,3,v5,4,v2,5,v4,5,v3,6,v5,6}.則|S|=11且余圖P6×C′6S無圈,如下圖2.31所示.圖2.30P6×C′9S圖2.31P6×C′6S情形2.當(dāng)n=3k+1(k≥0),(P6×C′3k+1)≥5k+3.1.當(dāng)k為奇數(shù)時(shí),取S={v5,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...v1,3k+1,v4,3k+1},其中0≤m<k321.此時(shí)|S|=5k+3且余圖P6×C′3k+1S無圈,如下圖2.32所示.18

【參考文獻(xiàn)】：
期刊論文
[1]路與圈的笛卡爾乘積圖的消圈數(shù)[J]. 沈傳錦.  山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 2010(04)
[2]完全圖與樹、圈、完全圖、完全二部圖的笛卡爾乘積圖的消圈數(shù)[J]. 沈傳錦.  海南大學(xué)學(xué)報(bào)(自然科學(xué)版). 2009(04)
[3]蛇形圖的消圈公式[J]. 侯劍萍.  福州大學(xué)學(xué)報(bào)(自然科學(xué)版). 2009(05)

碩士論文
[1]Halin圖消圈數(shù)及點(diǎn)染色問題的研究[D]. 王永強(qiáng).華東師范大學(xué) 2015
[2]幾類圖的消圈數(shù)問題[D]. 莊翠花.華東師范大學(xué) 2014



本文編號(hào)：3335336