平面圖的z變換圖的連通性及對pm215;cn的強迫譜的應用

1、分類號： O157 密級： 公開研 究 生 學 位 論 文論文題目(中文) 平面圖的 𝑍-變換圖的連通性及對 𝑃𝑚 × 𝐶𝑛 的強迫譜的應用論文題目(外文) The Connectivity of 𝑍-transformation Graphof Plane Graphs with the Applications toForcin

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

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

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

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

6、#119899; ? 𝑚| = 1 時,𝑍(𝑃𝑚 × 𝐶𝑛) 有 𝑛 個一度點, 且恰好有兩個同構類, 其余情況沒有一度點; 當 𝑛 為偶數(shù)時, 有且僅有 2 個一度點, 它們所對應的 𝐺 的完美匹配的所有的匹配邊都是水平的. 與此同時, 我們簡化了全局 𝑍-變換圖 &

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