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

1、二維環(huán)面是一類重要網絡拓撲結構，被廣泛應用于實際中.m×n二維環(huán)面，記為Torus(m，n)（m，n≥2是正整數），是包含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).
　　設F是圖G的邊子集，若G-F既不包含完美匹配，也不包含準完美匹配，稱F為G的匹配排除集.最小匹配排除集所包含的

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

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

4、4)當k1≥4，k2=3時，Torus(k1，3)的條件匹配排除數為5.
　　(5)當k1≥4，k2≥5時，Torus(k1，k2)的條件匹配排除數為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相鄰當且僅當存在一個整數j∈{0，1，…，n-1}滿足uj=