4元n方體完善匹配的若干性質(zhì).pdf

1、具有許多優(yōu)良特性的k元n方體是應(yīng)用非常廣泛的互連網(wǎng)絡(luò)之一.k元n方體Qkn（k≥2，n≥1）的頂點集V(Qkn)={u0u1…un-1:0≤ui≤k-1，0≤i≤n-1}，兩個不同的頂點u=u0u1…un-1和v=v0v1…vn-1相鄰當且僅當存在一個整數(shù)j∈{0，1，…，n-1}，滿足uj=vj±1(mod k)且ui=vi，i∈{0，1，…，n-1}\{j}.此時稱(u，v)為一條j維邊.若刪去Q4n的所有j維邊，其中，j∈{0，1

2、，2，…，n-1}，得到四個4元n-1立方體，分別設(shè)為Q[0]、Q[1]、Q[2]和Q[3].
　　設(shè)M是E的一個子集，它的元素是G中的邊，并且這些邊中的任意兩個在G中均不相鄰，則稱M為G的匹配.若匹配M的某條邊與頂點v關(guān)聯(lián)，則稱M飽和頂點v，并且稱v是M飽和的，否則稱v是M非飽和的.若G的每個頂點均為M飽和的，則稱M為G的完美匹配.
　　圖G的匹配圖記為M(G)，它的頂點集是G的所有完美匹配的集合，兩個頂點相鄰當且僅當兩個

3、頂點對應(yīng)的完美匹配的并構(gòu)成G的一個Hamilton圈.因此，M(G)的頂點與G的完美匹配是一一對應(yīng)的.
　　在網(wǎng)絡(luò)暴露攻擊中會用到完美匹配，當通過一個混合閾值追蹤一個信息時，完美匹配暴露攻擊會起很大的作用.在一些網(wǎng)絡(luò)連通問題中，匹配排除也起著關(guān)鍵作用.在本文中，我們主要研究4元n方體的完美匹配的一些問題.本文共分三章:
　　第一章中，介紹一些本文將會用到的有關(guān)圖論的基本概念.
　　第二章中，研究4元n方體的一個匹配擴展

4、成完美匹配的問題.主要結(jié)果如下:
　　(1)設(shè)M是Q4n的任意一個匹配，且M中所含邊的數(shù)目不多于2n-1，則M可擴成Q4n的一個完美匹配，且該結(jié)論是最優(yōu)的.
　　(2)設(shè)M是Q4n的任意一個匹配，M中所含邊的數(shù)目不多于2n-2，則存在d∈{0，1，…，n-1}，使得M中至多有一條d維邊.刪去Q4n中所有d維邊得到4個4元n-1方體，記為Q[0]，Q[1]，Q[2],Q[3].若x，y是某個Q[i]中兩個未被飽和的頂點，i∈{

5、0，1，2，3}，滿足x，y之間的距離為奇數(shù)，則M可以擴成Q4n\{x，y}的一個完美匹配.
　　第三章中，研究4元n方體的匹配圖的一些性質(zhì).主要結(jié)果如下:記[n]={0，1，…，n-1}.對任意α∈[n]，記Iα1n={(u0u1…uα-11uα+1…un-1，u0u1…uα-12uα+1…un-1)|ui∈[4]，i∈[n]\{α}∪{(u0u1… uα-10uα+1…un-1,u0u1…uα-13uα+1…un-1)|ui∈

6、[4]，i∈[n]\{α}}，Iα2n={(u0u1…uα-12uα+1…un-1,u0u1…uα-13uα+1…un-1)|ui∈[4],i∈[n]\{α}}∪{(u0u1…uα-10uα+1…un-1,u0u1…uα-11uα+1…un-1)|ui∈[4]，i∈[n]\{α}}，則Iα1n和Iα2n都是Q4n的完美匹配.設(shè)Iαin，Iβjn是Q4n的兩個完美匹配，i，j∈{1，2}，α，β∈[n]，則在M(Q4n)中存在Iαin和I