二維環(huán)面的匹配排除.pdf

1、二維環(huán)面是一類重要網(wǎng)絡(luò)拓撲結(jié)構(gòu)，被廣泛應(yīng)用于實際中.m×n二維環(huán)面，記為Torus(m，n)（m，n≥2是正整數(shù)），是包含mn個頂點的圖，頂點集為{va，b:0≤a≤m-1，0≤b≤n-1}，任意兩個不同的頂點va，b和va'，b'相鄰當且僅當a=a'，b=b'±1(modn)或b=b'，a=a'±1(mod m).
　　設(shè)F是圖G的邊子集，若G-F既不包含完美匹配，也不包含準完美匹配，稱F為G的匹配排除集.最小匹配排除集所包含的

2、邊數(shù)稱為匹配排除數(shù).如果一個邊集中的所有邊都與同一頂點相關(guān)聯(lián)，則稱該邊集為平凡的.對許多互聯(lián)網(wǎng)絡(luò)來說，最小匹配排除集恰好是平凡的.設(shè)F是圖G的邊子集，若G-F既不包含完美匹配和準完美匹配也不包含孤立頂點，則稱F為G的條件匹配排除集.圖G的最小條件匹配排除集所包含的邊數(shù)稱為G的條件匹配排除數(shù).本文對二維環(huán)面的匹配排除和條件匹配進行研究，主要內(nèi)容分為三章.
　　在第一章，我們介紹了一些本文所要用到的有關(guān)圖論方面的基本概念和性質(zhì).在第二

3、章，我們主要研究二維環(huán)面Torus(k1，k2)的匹配排除集（數(shù)）和條件匹配排除集（數(shù)），其中k1≥2是偶數(shù)，k2≥3是奇數(shù).主要結(jié)果如下:
　　(1)長度至少為3的奇圈的匹配排除數(shù)是3.
　　(2)當k2≥3時，Torus(2，k2)的匹配排除數(shù)和條件匹配排除數(shù)均為3.
　　(3)當k1≥4，k2≥3時，Torus(k1，k2)的匹配排除數(shù)為4.進一步，Torus(k1，k2)的最小匹配排除集是平凡的.
　　(

4、4)當k1≥4，k2=3時，Torus(k1，3)的條件匹配排除數(shù)為5.
　　(5)當k1≥4，k2≥5時，Torus(k1，k2)的條件匹配排除數(shù)為6.
　　k元n立方體，記為Qkn（k≥2，n≥1），是包含kn個頂點的圖，其頂點集為{vn-1vn-2…v0:0≤vi≤k-1，0≤i≤n-1}.Qkn中兩個頂點u=un-1un-2…u0和v=vn-1vn-2…v0相鄰當且僅當存在一個整數(shù)j∈{0，1，…，n-1}滿足uj=