關(guān)于幾類特殊圖的群連通度的研究.pdf

1、1950年,Tutte為了研究圖染色問題而引出了處處非零流的概念,并提出了很多猜想,得到了一些基本的結(jié)論。1992年Jaeger等人把這類問題進(jìn)行了歸納,并進(jìn)一步提出了群連通度的概念。對(duì)非零流和群連通度問題的研究有助于染色問題中四色猜想的解決;另外,在實(shí)際網(wǎng)絡(luò)中,研究此問題有利于更深入的了解網(wǎng)絡(luò)結(jié)構(gòu)。本文主要研究?jī)蓚€(gè)問題:正則圖的處處非零流;晶體圖,圈和路形成的笛卡爾積圖的群連通度。而本文針對(duì)這兩個(gè)問題做了如下工作:
　　首先,通

2、過應(yīng)用編程思想來對(duì)圖中的點(diǎn)進(jìn)行賦值并根據(jù)群連通度的定義進(jìn)行運(yùn)算,依靠循環(huán)算法得到奇數(shù)階正則圖存在Z2m?NZF的一個(gè)條件,并且對(duì)含有奇圈,圈上點(diǎn)的度數(shù)都為3的圖不含Z3處處非零流做出了證明。
　　其次,通過對(duì)晶體圖中三度點(diǎn)相鄰兩條邊的去掉和收縮操作,得到了晶體圖的群連通度為4。
　　最后,通過分割圖形得到子圖,先部分后整體,多次運(yùn)用反證法以及對(duì)點(diǎn)進(jìn)行合理的賦值證明了奇數(shù)階的圈和路形成的的笛卡爾積圖的群連通度為4,偶數(shù)階的圈和