【摘要】：圖G=(V,E)的媒體圖就是頂點(diǎn)集為E,邊集為{ef|e,f是G中兩條相鄰的邊且在同一面內(nèi)}的圖,用M(G)表示.鏈環(huán)L是將一維平面S1上的圖嵌入到三維空間E3上形成的圈的不交并.鏈環(huán)圖D(G)是鏈環(huán)L的平面表示.對(duì)于平面圖G,可以通過它的媒體圖M(G)來構(gòu)造鏈環(huán)圖D(G).基于無向的交錯(cuò)鏈環(huán)的虧格理論,Jin在[9]中引進(jìn)了平面圖的最大狀態(tài)圈的數(shù)目.對(duì)鏈環(huán)圖D(G)的每個(gè)交點(diǎn)選擇A-分裂或B-分裂,使得圈的數(shù)目最大時(shí)的狀態(tài)稱為最大狀態(tài),該狀態(tài)下的圈數(shù)記為S_(max)(G),并得出其中H跑遍G的所有生成子圖,c(H)是H的連通分支數(shù).在這篇文章中,我們利用Jin的結(jié)論,證明了對(duì)于任何圖G(不需要平面),S_(max)(G)當(dāng)G的生成子圖H的每個(gè)連通分支都是G的有兩個(gè)邊不交生成樹的極大子圖時(shí)取得,并證明了這個(gè)生成子圖是唯一的.在第三章,給出了一個(gè)多項(xiàng)式時(shí)間算法,來找出滿足S_(max)(G)的生成子圖H,以便快速算出圖G的最大狀態(tài)圈的數(shù)目S_(max)(G)。
【學(xué)位授予單位】：新疆大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5
，

本文編號(hào)：2544287