平面圖的z變換圖的連通性及對(duì)pm215;cn的強(qiáng)迫譜的應(yīng)用

1、分類號(hào)： O157 密級(jí)： 公開(kāi)研 究 生 學(xué) 位 論 文論文題目(中文) 平面圖的 𝑍-變換圖的連通性及對(duì) 𝑃𝑚 × 𝐶𝑛 的強(qiáng)迫譜的應(yīng)用論文題目(外文) The Connectivity of 𝑍-transformation Graphof Plane Graphs with the Applications toForcin

2、g Spectrum of 𝑃𝑚 × 𝐶𝑛研 究 生 姓 名 王 景 峰學(xué) 科、 專業(yè) 數(shù)學(xué) 、應(yīng)用數(shù)學(xué)研 究 方 向 圖論及其應(yīng)用學(xué) 位 級(jí) 別 碩 士導(dǎo)師姓名、 職稱 張和平 教授論 文 工 作 起 止 年 月 2015 年 9 月 至 2017 年 3 月論文提交日期 2017 年 4 月論文答辯日期 2017 年 5 月學(xué)位授予日期校 址： 甘 肅 省 蘭

3、 州 市平面圖的 𝑍-變換圖的連通性及對(duì) 𝑃𝑚 × 𝐶𝑛 的強(qiáng)迫譜的應(yīng)用中文摘要設(shè) 𝐺 是一個(gè)平面圖. 𝐺 的 𝑍-變換圖 𝑍(𝐺) 的頂點(diǎn)集為 𝐺 的所有完美匹配的集合, 兩個(gè)頂點(diǎn) 𝑀1, 𝑀2 之間連邊當(dāng)且僅當(dāng)它們的對(duì)

4、稱差恰好是 𝐺 的某個(gè)內(nèi)面圈.本文首先證明了對(duì)于簡(jiǎn)單平面圖 𝐺, 其 𝑍-變換圖是二部圖, 并且證明了 𝑍(𝐺) 連通的充要條件是, 對(duì)于 𝐺 的任意一個(gè)好圈 𝐶 , 𝐶 包括它的內(nèi)部一起構(gòu)成了一個(gè)平面基本二部圖. 由此推廣了平面二部圖的𝑍-變換圖的相應(yīng)的結(jié)論.對(duì)于圓柱圖, 利用上述充要條件我們

5、得到 𝑍(𝑃𝑚 × 𝐶𝑛)(𝑛 ?= 4) 去掉一度點(diǎn)是 2-連通的, 類似的結(jié)論在六角系統(tǒng)[16, 17]上已經(jīng)得到證明. 進(jìn)一步, 我們也刻畫(huà)出了 𝑍(𝑃𝑚 × 𝐶𝑛) 的所有一度點(diǎn). 具體講, 當(dāng) 𝑛 為奇數(shù), 并且 |&

6、#119899; ? 𝑚| = 1 時(shí),𝑍(𝑃𝑚 × 𝐶𝑛) 有 𝑛 個(gè)一度點(diǎn), 且恰好有兩個(gè)同構(gòu)類, 其余情況沒(méi)有一度點(diǎn); 當(dāng) 𝑛 為偶數(shù)時(shí), 有且僅有 2 個(gè)一度點(diǎn), 它們所對(duì)應(yīng)的 𝐺 的完美匹配的所有的匹配邊都是水平的. 與此同時(shí), 我們簡(jiǎn)化了全局 𝑍-變換圖 &

7、#119885;𝑡(𝑃𝑚 × 𝐶2𝑛)(𝑛 ?= 2) 是 2-連通的證明.圖 𝐺 的所有完美匹配的強(qiáng)迫數(shù)所構(gòu)成的集合叫做 𝐺 的強(qiáng)迫譜. 最后, 利用平面圖的 𝑍-變換圖連通的充要條件證明了 𝑃2𝑚 × 𝐶2𝑛